content: {-|
  Module      : Crypto.Lol.Cyclotomic.Cyc
  Description : An implementation of cyclotomic rings that hides and
                automatically manages the internal representations of
                ring elements.
  Copyright   : (c) Eric Crockett, 2011-2018
                    Chris Peikert, 2011-2018
  License     : GPL-3
  Maintainer  : ecrockett0@gmail.com
  Stability   : experimental
  Portability : POSIX
  
    \( \def\Z{\mathbb{Z}} \)
    \( \def\F{\mathbb{F}} \)
    \( \def\Q{\mathbb{Q}} \)
    \( \def\Tw{\text{Tw}} \)
    \( \def\Tr{\text{Tr}} \)
    \( \def\O{\mathcal{O}} \)
  
  An implementation of cyclotomic rings that hides the
  internal representations of ring elements (e.g., the choice of
  basis), and also offers more efficient storage and operations on
  subring elements (including elements from the base ring itself).
  
  For an implementation that allows (and requires) the programmer to
  control the underlying representation, see
  "Crypto.Lol.Cyclotomic.CycRep".
  
  __WARNING:__ as with all fixed-point arithmetic, the functions
  associated with 'Cyc' may result in overflow (and thereby
  incorrect answers and potential security flaws) if the input
  arguments are too close to the bounds imposed by the base type.
  The acceptable range of inputs for each function is determined by
  the internal linear transforms and other operations it performs.
  -}
  
  {-# LANGUAGE AllowAmbiguousTypes        #-}
  {-# LANGUAGE ConstraintKinds            #-}
  {-# LANGUAGE DataKinds                  #-}
  {-# LANGUAGE FlexibleContexts           #-}
  {-# LANGUAGE FlexibleInstances          #-}
  {-# LANGUAGE GADTs                      #-}
  {-# LANGUAGE GeneralizedNewtypeDeriving #-}
  {-# LANGUAGE InstanceSigs               #-}
  {-# LANGUAGE MultiParamTypeClasses      #-}
  {-# LANGUAGE NoImplicitPrelude          #-}
  {-# LANGUAGE PartialTypeSignatures      #-}
  {-# LANGUAGE PolyKinds                  #-}
  {-# LANGUAGE QuantifiedConstraints      #-}
  {-# LANGUAGE RankNTypes                 #-}
  {-# LANGUAGE ScopedTypeVariables        #-}
  {-# LANGUAGE StandaloneDeriving         #-}
  {-# LANGUAGE TemplateHaskell            #-}
  {-# LANGUAGE TypeApplications           #-}
  {-# LANGUAGE TypeFamilies               #-}
  {-# LANGUAGE TypeOperators              #-}
  {-# LANGUAGE UndecidableInstances       #-}
  
  module Crypto.Lol.Cyclotomic.Cyc
  (
  -- * Data type
    Cyc
  -- * Constructors/deconstructors
  , UnCyc(..)
  ) where
  
  import qualified Algebra.Additive     as Additive (C)
  import qualified Algebra.Module       as Module (C)
  import qualified Algebra.Ring         as Ring (C)
  import qualified Algebra.ZeroTestable as ZeroTestable (C)
  
  import           Crypto.Lol.CRTrans
  import           Crypto.Lol.Cyclotomic.CycRep   hiding (coeffsDec,
                                                   coeffsPow, crtSet,
                                                   powBasis)
  import qualified Crypto.Lol.Cyclotomic.CycRep   as R
  import           Crypto.Lol.Cyclotomic.Language hiding (Dec, Pow)
  import qualified Crypto.Lol.Cyclotomic.Language as L
  import           Crypto.Lol.Cyclotomic.Tensor   (TensorCRT, TensorCRTSet,
                                                   TensorGSqNorm,
                                                   TensorGaussian,
                                                   TensorPowDec)
  import           Crypto.Lol.Gadget
  import           Crypto.Lol.Prelude             as LP
  import           Crypto.Lol.Reflects
  import           Crypto.Lol.Types               (RRq, ZqBasic)
  import           Crypto.Lol.Types.FiniteField
  import           Crypto.Lol.Types.IFunctor
  import           Crypto.Lol.Types.Proto
  
  import Control.Applicative  hiding ((*>))
  import Control.Arrow
  import Control.DeepSeq
  import Control.Monad.Random hiding (lift)
  import Data.Constraint      ((\\))
  import Data.Foldable        (Foldable)
  import Data.Traversable
  import Language.Haskell.TH
  
  -- | Underlying GADT for a cyclotomic ring in one of several
  -- representations.
  data CycG t m r where
    Pow :: !(CycRep t P m r) -> CycG t m r
    Dec :: !(CycRep t D m r) -> CycG t m r
    CRT :: !(CycRepEC t m r) -> CycG t m r
    -- super-optimized storage of scalars
    Scalar :: !r -> CycG t m r
    -- optimized storage of subring elements
    Sub :: (l `Divides` m) => !(CycG t l r) -> CycG t m r
    -- CJP: someday try to merge the above two?
  
  -- | A cyclotomic ring such as \( \Z[\zeta_m] \), \( \Z_q[\zeta_m] \),
  -- or \( \Q[\zeta_m] \): @t@ is the 'Tensor' type for storing
  -- coefficient tensors; @m@ is the cyclotomic index; @r@ is the base
  -- ring of the coefficients (e.g., \(\ \Q \), \( \Z \), \( \Z_q \)).
  data family Cyc (t :: Factored -> * -> *) (m :: Factored) r
  
  type instance LiftOf (CycG t m r) = CycG t m (LiftOf r)
  type instance LiftOf (Cyc  t m r) = Cyc  t m (LiftOf r)
  
  -- could also do an Int instance
  newtype instance Cyc t m Double        = CycDbl { unCycDbl :: CycG t m Double }
  newtype instance Cyc t m Int64         = CycI64 { unCycI64 :: CycG t m Int64 }
  newtype instance Cyc t m (ZqBasic q z) = CycZqB { unCycZqB :: CycG t m (ZqBasic q z) }
  
  -- | cyclotomic over a product base ring, represented as a product of
  -- cyclotomics over the individual rings
  data    instance Cyc t m (a,b)         = CycPair !(Cyc t m a) !(Cyc t m b)
  
  -- | cyclotomic ring of integers with unbounded precision, limited to
  -- powerful- or decoding-basis representation.
  data instance Cyc t m Integer
    = PowIgr !(CycRep t P m Integer)
    | DecIgr !(CycRep t D m Integer)
  
  -- | additive group \( K/qR \), limited to powerful- or decoding-basis
  -- representation
  data instance Cyc t m (RRq q r)
    = PowRRq !(CycRep t P m (RRq q r))
    | DecRRq !(CycRep t D m (RRq q r))
  
  ---------- Constructors / destructors ----------
  
  -- | Convenience wrapper.
  cycPC :: Either (CycRep t P m r) (CycRep t C m r) -> CycG t m r
  cycPC = either Pow (CRT . Right)
  {-# INLINABLE cycPC #-}
  
  -- | Convenience wrapper.
  cycPE :: Either (CycRep t P m r) (CycRep t E m r) -> CycG t m r
  cycPE = either Pow (CRT . Left)
  {-# INLINABLE cycPE #-}
  
  -- | Unwrap a 'CycG' as a 'CycRep' in powerful-basis representation.
  unCycGPow :: (Fact m, CRTElt t r) => CycG t m r -> CycRep t P m r
  {-# INLINABLE unCycGPow #-}
  unCycGPow c = let (Pow u) = toPow' c in u
  
  -- | Unwrap a 'CycG' as a 'CycRep' in decoding-basis representation.
  unCycGDec :: (Fact m, CRTElt t r) => CycG t m r -> CycRep t D m r
  {-# INLINABLE unCycGDec #-}
  unCycGDec c = let (Dec u) = toDec' c in u
  
  {-
  -- | Unwrap a 'CycG' as a 'CycRep' in a CRT-basis representation.
  uncycCRT :: (Fact m, CRTElt t r) => CycG t m r -> CycRepEC t m r
  {-# INLINABLE uncycCRT #-}
  uncycCRT c = let (CRT u) = toCRT' c in u
  -}
  
  -- | Go between 'Cyc' and 'CycRep', in a desired representation.
  class UnCyc t r where
    cycPow   :: (Fact m) => CycRep t P m r -> Cyc t m r
    cycDec   :: (Fact m) => CycRep t D m r -> Cyc t m r
    unCycPow :: (Fact m) => Cyc t m r -> CycRep t P m r
    unCycDec :: (Fact m) => Cyc t m r -> CycRep t D m r
  
  instance CRTElt t Double => UnCyc t Double where
    cycPow   = CycDbl . Pow
    cycDec   = CycDbl . Dec
    unCycPow = unCycGPow . unCycDbl
    unCycDec = unCycGDec . unCycDbl
  
  instance CRTElt t Int64 => UnCyc t Int64 where
    cycPow   = CycI64 . Pow
    cycDec   = CycI64 . Dec
    unCycPow = unCycGPow . unCycI64
    unCycDec = unCycGDec . unCycI64
  
  instance CRTElt t (ZqBasic q z) => UnCyc t (ZqBasic q z) where
    cycPow   = CycZqB . Pow
    cycDec   = CycZqB . Dec
    unCycPow = unCycGPow . unCycZqB
    unCycDec = unCycGDec . unCycZqB
  
  -- CJP TODO: one for Integer?; would require converting between Pow and
  -- Dec reps in pure Haskell
  
  instance TensorPowDec t (RRq q r) => UnCyc t (RRq q r) where
    cycPow = PowRRq
    cycDec = DecRRq
    unCycPow (PowRRq v) = v
    unCycPow (DecRRq v) = toPow v
    unCycDec (DecRRq v) = v
    unCycDec (PowRRq v) = toDec v
  
  instance (UnCyc t a, UnCyc t b, IFunctor t, IFElt t a, IFElt t b, IFElt t (a,b))
    => UnCyc t (a,b) where
    cycPow = uncurry CycPair . ((cycPow . fmapI fst) &&& (cycPow . fmapI snd))
    cycDec = uncurry CycPair . ((cycDec . fmapI fst) &&& (cycDec . fmapI snd))
  
    unCycPow (CycPair a b) = zipWithI (,) (unCycPow a) (unCycPow b)
    unCycDec (CycPair a b) = zipWithI (,) (unCycDec a) (unCycDec b)
  
  ---------- Category-theoretic instances ----------
  
  instance (Fact m, CRTElt t r, Foldable (t m))
      => FoldableCyc (CycG t m) r where
    foldrCyc (Just L.Pow)   f acc (Pow u) = foldr f acc u
    foldrCyc (Just L.Dec)   f acc (Dec u) = foldr f acc u
    foldrCyc Nothing        f acc (Pow u) = foldr f acc u
    foldrCyc Nothing        f acc (Dec u) = foldr f acc u
  
    foldrCyc b@(Just L.Pow) f acc c       = foldrCyc b f acc $ toPow' c
    foldrCyc b@(Just L.Dec) f acc c       = foldrCyc b f acc $ toDec' c
    foldrCyc Nothing        f acc c       = foldrCyc Nothing f acc $ toPow' c
  
  instance (FoldableCyc (CycG t m) Double) => FoldableCyc (Cyc t m) Double where
    foldrCyc bas f acc = foldrCyc bas f acc . unCycDbl
  
  instance (FoldableCyc (CycG t m) Int64) => FoldableCyc (Cyc t m) Int64 where
    foldrCyc bas f acc = foldrCyc bas f acc . unCycI64
  
  instance (FoldableCyc (CycG t m) (ZqBasic q z))
    => FoldableCyc (Cyc t m) (ZqBasic q z) where
    foldrCyc bas f acc = foldrCyc bas f acc . unCycZqB
  
  -- No instance for CycPair -- is one possible?
  
  instance (Foldable (t m)) => FoldableCyc (Cyc t m) Integer where
    foldrCyc (Just L.Pow) f acc (PowIgr u) = foldr f acc u
    foldrCyc (Just L.Dec) f acc (DecIgr u) = foldr f acc u
    foldrCyc Nothing      f acc (PowIgr u) = foldr f acc u
    foldrCyc Nothing      f acc (DecIgr u) = foldr f acc u
    foldrCyc _            _ _   _          =
      error "Cyc.foldrCyc over Integer: mismatched bases, implementation TODO."
  
  instance (Fact m, TensorPowDec t (RRq q r), Foldable (t m))
      => FoldableCyc (Cyc t m) (RRq q r) where
    foldrCyc (Just L.Pow) f acc = foldr f acc . unCycPow
    foldrCyc (Just L.Dec) f acc = foldr f acc . unCycDec
    foldrCyc Nothing      f acc = foldrCyc (Just L.Pow) f acc
  
  --- FunctorCyc
  
  instance (Fact m, CRTElt t a, IFunctor t, IFElt t a, IFElt t b)
    => FunctorCyc (CycG t m) a b where
    fmapCyc (Just L.Pow) f = Pow . fmapI f . unCycGPow
    fmapCyc (Just L.Dec) f = Dec . fmapI f . unCycGDec
    fmapCyc Nothing      f = fmapCyc (Just L.Pow) f
  
  instance (Functor (t m)) => FunctorCyc (Cyc t m) Integer Integer where
    fmapCyc (Just L.Pow) f (PowIgr u) = PowIgr $ fmap f u
    fmapCyc (Just L.Dec) f (DecIgr u) = DecIgr $ fmap f u
    fmapCyc Nothing      f (PowIgr u) = PowIgr $ fmap f u
    fmapCyc Nothing      f (DecIgr u) = DecIgr $ fmap f u
    fmapCyc _            _ _          =
      error "Cyc.fmapCyc Integer->Integer: mismatched bases, implementation TODO"
  
  -- CJP: the rest of the FunctorCyc instances are autogen'd at end of
  -- file, to avoid scoping problems
  
  ---------- Algebraic instances ----------
  
  instance (Fact m, ZeroTestable r, CRTElt t r,
            forall m' . Fact m' => ZeroTestable.C (t m' r))
    => ZeroTestable.C (CycG t m r) where
    isZero x = case x of
      (Pow u)         -> isZero u
      (Dec u)         -> isZero u
      (CRT (Right u)) -> isZero u
      c@(CRT _)       -> isZero $ toPow' c
      (Scalar c)      -> isZero c
      (Sub c)         -> isZero c
  
  deriving instance ZeroTestable (CycG t m Double) => ZeroTestable.C (Cyc t m Double)
  deriving instance ZeroTestable (CycG t m Int64) => ZeroTestable.C (Cyc t m Int64)
  deriving instance ZeroTestable (CycG t m (ZqBasic q z)) => ZeroTestable.C (Cyc t m (ZqBasic q z))
  
  instance (ZeroTestable (Cyc t m a), ZeroTestable (Cyc t m b))
    => ZeroTestable.C (Cyc t m (a,b)) where
    isZero (CycPair a b) = isZero a && isZero b
  
  instance ZeroTestable (t m Integer) => ZeroTestable.C (Cyc t m Integer) where
    isZero (PowIgr v) = isZero v
    isZero (DecIgr v) = isZero v
  
  instance ZeroTestable (t m (RRq q r)) => ZeroTestable.C (Cyc t m (RRq q r)) where
    isZero (PowRRq c) = isZero c
    isZero (DecRRq c) = isZero c
  
  -----
  
  instance (Eq r, Fact m, CRTElt t r,
            forall m' . Fact m' => Eq (t m' r)) => Eq (CycG t m r) where
    {-# INLINABLE (==) #-}
    -- same representations
    (Scalar c1) == (Scalar c2) = c1 == c2
    (Pow u1) == (Pow u2) = u1 == u2
    (Dec u1) == (Dec u2) = u1 == u2
    (CRT (Right u1)) == (CRT (Right u2)) = u1 == u2
  
    -- compare Subs in compositum
    -- EAC: would like to convert c2 to basis of c1 *before* embedding
    (Sub (c1 :: CycG t l1 r)) == (Sub (c2 :: CycG t l2 r)) =
      (embed' c1 :: CycG t (FLCM l1 l2) r) == embed' c2
      \\ lcmDivides @l1 @l2
  
    -- some other relatively efficient comparisons
    (Scalar c1) == (Pow u2) = scalarPow c1 == u2
    (Pow u1) == (Scalar c2) = u1 == scalarPow c2
  
    -- otherwise: compare in powerful basis
    c1 == c2 = toPow' c1 == toPow' c2
  
  deriving instance Eq (CycG t m Int64)         => Eq (Cyc t m Int64)
  deriving instance Eq (CycG t m (ZqBasic q z)) => Eq (Cyc t m (ZqBasic q z))
  
  instance (Eq (Cyc t m a), Eq (Cyc t m b)) => Eq (Cyc t m (a,b)) where
    (CycPair a b) == (CycPair a' b') = a == a' && b == b'
  
  -- no Eq for Double or RRq due to precision, nor for Integer because
  -- we can't change representations
  
  -----
  
  instance (Fact m, CRTElt t r, ZeroTestable r) => Additive.C (CycG t m r) where
    {-# INLINABLE zero #-}
    zero = Scalar zero
  
    {-# INLINABLE (+) #-}
    -- optimized addition of zero
    (Scalar c1) + c2 | isZero c1 = c2
    c1 + (Scalar c2) | isZero c2 = c1
  
    -- SAME CONSTRUCTORS
    (Scalar c1) + (Scalar c2) = Scalar (c1+c2)
    (Pow u1) + (Pow u2) = Pow $ u1 + u2
    (Dec u1) + (Dec u2) = Dec $ u1 + u2
    (CRT u1) + (CRT u2) = CRT $ u1 + u2
    -- Sub plus Sub: work in compositum
    -- EAC: would like to convert c2 to basis of c1 before embedding
    (Sub (c1 :: CycG t m1 r)) + (Sub (c2 :: CycG t m2 r)) =
      Sub ((embed' c1 :: CycG t (FLCM m1 m2) r) + embed' c2)
      \\ lcm2Divides @m1 @m2 @m
  
    -- SCALAR PLUS SOMETHING ELSE
  
    (Scalar c)  + (Pow u)  = Pow $ scalarPow c + u
    (Scalar c)  + (Dec u)  = Pow $ scalarPow c + toPow u -- workaround scalarDec
    (Scalar c)  + (CRT u)  = CRT $ scalarCRT c + u
    (Scalar c1) + (Sub c2) = Sub $ Scalar c1 + c2 -- must re-wrap Scalar!
  
    (Pow u)  + (Scalar c)  = Pow $ u + scalarPow c
    (Dec u)  + (Scalar c)  = Pow $ toPow u + scalarPow c -- workaround scalarDec
    (CRT u)  + (Scalar c)  = CRT $ u + scalarCRT c
    (Sub c1) + (Scalar c2) = Sub $ c1 + Scalar c2
  
    -- SUB PLUS NON-SUB, NON-SCALAR: work in full ring
    -- EAC: would like to convert sub to basis of other before embedding
    (Sub c1) + c2 = embed' c1 + c2
    c1 + (Sub c2) = c1 + embed' c2
  
    -- mixed Dec and Pow: use linear-time conversions
    (Dec u1) + (Pow u2) = Pow $ toPow u1 + u2
    (Pow u1) + (Dec u2) = Pow $ u1 + toPow u2
  
    -- one CRT: convert other to CRT
    (CRT u1) + (Pow u2) = CRT $ u1 + toCRT u2
    (CRT u1) + (Dec u2) = CRT $ u1 + toCRT u2
    (Pow u1) + (CRT u2) = CRT $ toCRT u1 + u2
    (Dec u1) + (CRT u2) = CRT $ toCRT u1 + u2
  
    {-# INLINABLE negate #-}
    negate (Pow u)    = Pow $ negate u
    negate (Dec u)    = Dec $ negate u
    negate (CRT u)    = CRT $ negate u
    negate (Scalar c) = Scalar (negate c)
    negate (Sub c)    = Sub $ negate c
  
  deriving instance Additive (CycG t m Double) => Additive.C (Cyc t m Double)
  deriving instance Additive (CycG t m Int64) => Additive.C (Cyc t m Int64)
  deriving instance Additive (CycG t m (ZqBasic q z)) => Additive.C (Cyc t m (ZqBasic q z))
  
  instance (Additive (Cyc t m a), Additive (Cyc t m b))
    => Additive.C (Cyc t m (a,b)) where
    zero = CycPair zero zero
    (CycPair a b) + (CycPair a' b') = CycPair (a+a') (b+b')
    negate (CycPair a b) = CycPair (negate a) (negate b)
  
  instance (Additive (RRq q r), TensorPowDec t (RRq q r), IFunctor t, Fact m)
    => Additive.C (Cyc t m (RRq q r)) where
    zero = PowRRq zero
  
    (PowRRq u1) + (PowRRq u2) = PowRRq $ u1 + u2
    (DecRRq u1) + (DecRRq u2) = DecRRq $ u1 + u2
    (PowRRq u1) + (DecRRq u2) = PowRRq $ u1 + toPow u2
    (DecRRq u1) + (PowRRq u2) = PowRRq $ toPow u1 + u2
  
    negate (PowRRq u) = PowRRq $ negate u
    negate (DecRRq u) = DecRRq $ negate u
  
  -----
  
  instance (Fact m, CRTElt t r, ZeroTestable r) => Ring.C (CycG t m r) where
    {-# INLINABLE one #-}
    one = Scalar one
  
    {-# INLINABLE fromInteger #-}
    fromInteger = Scalar . fromInteger
  
    {-# INLINABLE (*) #-}
  
    -- optimized mul-by-zero
    v1@(Scalar c1) * _ | isZero c1 = v1
    _ * v2@(Scalar c2) | isZero c2 = v2
  
    -- both CRT: if over C, then convert result to pow for precision reasons
    (CRT u1) * (CRT u2) = either (Pow . toPow) (CRT . Right) $ u1*u2
  
    -- at least one Scalar
    (Scalar c1) * (Scalar c2) = Scalar $ c1*c2
    (Scalar c) * (Pow u) = Pow $ c *> u
    (Scalar c) * (Dec u) = Dec $ c *> u
    (Scalar c) * (CRT u) = CRT $ c *> u
    (Scalar c1) * (Sub c2) = Sub $ Scalar c1 * c2
  
    (Pow u) * (Scalar c) = Pow $ c *> u
    (Dec u) * (Scalar c) = Dec $ c *> u
    (CRT u) * (Scalar c) = CRT $ c *> u
    (Sub c1) * (Scalar c2) = Sub $ c1 * Scalar c2
  
    -- TWO SUBS: work in a CRT rep for compositum
    (Sub (c1 :: CycG t m1 r)) * (Sub (c2 :: CycG t m2 r)) =
      -- re-wrap c1, c2 as Subs of the composition, and force them to CRT
      Sub ((toCRT' $ Sub c1 :: CycG t (FLCM m1 m2) r) * toCRT' (Sub c2))
      \\ lcm2Divides @m1 @m2 @m
  
    -- ELSE: work in appropriate CRT rep
    c1 * c2 = toCRT' c1 * toCRT' c2
  
  deriving instance Ring (CycG t m Double)        => Ring.C (Cyc t m Double)
  deriving instance Ring (CycG t m Int64)         => Ring.C (Cyc t m Int64)
  deriving instance Ring (CycG t m (ZqBasic q z)) => Ring.C (Cyc t m (ZqBasic q z))
  
  instance (Ring (Cyc t m a), Ring (Cyc t m b)) => Ring.C (Cyc t m (a,b)) where
    one = CycPair one one
    fromInteger z = CycPair (fromInteger z) (fromInteger z)
    (CycPair a b) * (CycPair a' b') = CycPair (a*a') (b*b')
  
  -- no instance for RRq because it's not a ring
  
  -----
  
  instance (Fact m, CRTElt t r, ZeroTestable r) => Module.C r (CycG t m r) where
    r *> (Scalar c) = Scalar $ r * c
    r *> (Pow v)    = Pow $ r *> v
    r *> (Dec v)    = Dec $ r *> v
    r *> (Sub c)    = Sub $ r *> c
    r *> x          = r *> toPow' x
  
  deriving instance Module Int64 (CycG t m Int64) => Module.C Int64 (Cyc t m Int64)
  deriving instance Module Double (CycG t m Double) => Module.C Double (Cyc t m Double)
  deriving instance (Module (ZqBasic q z) (CycG t m (ZqBasic q z)),
                     Ring (ZqBasic q z)) -- satisfy superclass
    => Module.C (ZqBasic q z) (Cyc t m (ZqBasic q z))
  
  instance (Module a (Cyc t m a), Module b (Cyc t m b))
    => Module.C (a,b) (Cyc t m (a,b)) where
    (a,b) *> (CycPair ca cb) = CycPair (a *> ca) (b *> cb)
  
  -- no instance for RRq because it's not, mathematically
  
  -- Module over finite field
  
  -- | \(R_p\) is an \(\F_{p^d}\)-module when \(d\) divides
  -- \(\varphi(m)\), by applying \(d\)-dimensional \(\F_p\)-linear
  -- transform on \(d\)-dim chunks of powerful basis coeffs.
  instance (GFCtx fp d, Fact m, CRTElt t fp, Module (GF fp d) (t m fp))
    => Module.C (GF fp d) (CycG t m fp) where
    -- CJP: optimize for Scalar if we can: r *> (Scalar c) is the tensor
    -- that has the coeffs of (r*c), followed by zeros.  (This assumes
    -- that the powerful basis has 1 as its first element, and that
    -- we're using pow to define the module mult.)
  
    -- Can use any r-basis to define module mult, but must be
    -- consistent. We use powerful basis.
    r *> (Pow v) = Pow $ r *> v
    r *> x       = r *> toPow' x
  
  deriving instance (Ring (GF (ZqBasic q z) d),
                     Module (GF (ZqBasic q z) d) (CycG t m (ZqBasic q z)))
    => Module.C (GF (ZqBasic q z) d) (Cyc t m (ZqBasic q z))
  
  ---------- Cyclotomic classes ----------
  
  instance (Fact m, CRTElt t r, ZeroTestable r, IntegralDomain r)
    => Cyclotomic (CycG t m r) where
    {-# SPECIALIZE instance (Fact m, CRTElt t Int64) => Cyclotomic (CycG t m Int64) #-}
    {-# SPECIALIZE instance (Fact m, CRTElt t Double) => Cyclotomic (CycG t m Double) #-}
    {-# SPECIALIZE instance (Fact m, CRTElt t (ZqBasic q Int64), Reflects q Int64) => Cyclotomic (CycG t m (ZqBasic q Int64)) #-}
  
    mulG (Pow u)         = Pow $ R.mulGPow u
    mulG (Dec u)         = Dec $ R.mulGDec u
    mulG (CRT (Left u))  = Pow $ R.mulGPow $ toPow u -- go to Pow for precision
    mulG (CRT (Right u)) = CRT $ Right $ R.mulGCRTC u
    mulG c@(Scalar _)    = mulG $ toCRT' c
    mulG (Sub c)         = mulG $ embed' c   -- must go to full ring
  
    divG (Pow u)         = Pow <$> R.divGPow u
    divG (Dec u)         = Dec <$> R.divGDec u
    divG (CRT (Left u))  = Pow <$> R.divGPow (toPow u) -- go to Pow for precision
    divG (CRT (Right u)) = Just $ (CRT . Right) $ R.divGCRTC u
    divG c@(Scalar _)    = divG $ toCRT' c
    divG (Sub c)         = divG $ embed' c  -- must go to full ring
  
    advisePow = toPow'
    adviseDec = toDec'
    adviseCRT = toCRT'
  
  deriving instance Cyclotomic (CycG t m Double) => Cyclotomic (Cyc t m Double)
  deriving instance Cyclotomic (CycG t m Int64)  => Cyclotomic (Cyc t m Int64)
  deriving instance Cyclotomic (CycG t m (ZqBasic q z)) => Cyclotomic (Cyc t m (ZqBasic q z))
  
  instance (Cyclotomic (Cyc t m a), Cyclotomic (Cyc t m b))
    => Cyclotomic (Cyc t m (a,b)) where
    {-# SPECIALIZE instance (Fact m, CRTElt t (ZqBasic q Int64), Reflects q Int64, Cyclotomic (Cyc t m b)) => Cyclotomic (Cyc t m (ZqBasic q Int64, b)) #-}
  
    mulG (CycPair a b) = CycPair (mulG a) (mulG b)
    divG (CycPair a b) = CycPair <$> divG a <*> divG b
    advisePow (CycPair a b) = CycPair (advisePow a) (advisePow b)
    adviseDec (CycPair a b) = CycPair (adviseDec a) (adviseDec b)
    adviseCRT (CycPair a b) = CycPair (adviseCRT a) (adviseCRT b)
  
  -----
  
  instance (Fact m, TensorGSqNorm t r, CRTElt t r)
    => GSqNormCyc (CycG t m) r where
    gSqNorm (Dec c) = gSqNormDec c
    gSqNorm c       = gSqNorm $ toDec' c
  
  instance (Fact m, TensorGSqNorm t Double, CRTElt t Double) -- copied
    => GSqNormCyc (Cyc t m) Double where
    gSqNorm = gSqNorm . unCycDbl
  
  instance (Fact m, TensorGSqNorm t Int64, CRTElt t Int64) -- copied
    => GSqNormCyc (Cyc t m) Int64 where
    gSqNorm = gSqNorm . unCycI64
  
  ----
  
  -- | uses 'Double' for the intermediate Gaussian sample
  instance (Fact m, TensorGaussian t Double, FunctorCyc (Cyc t m) Double Int64)
    => RoundedGaussianCyc (Cyc t m Int64) where
    roundedGaussian :: forall v rnd . (ToRational v, MonadRandom rnd)
                    => v -> rnd (Cyc t m Int64)
    {-# INLINABLE roundedGaussian #-}
    roundedGaussian svar =
      fmapCyc (Just L.Dec) (roundMult one) <$>
      (L.tweakedGaussian svar :: rnd (Cyc t m Double))
  
  -----
  
  instance (Lift' r, FunctorCyc (Cyc t m) r (LiftOf r)) => LiftCyc (Cyc t m r) where
    {-# SPECIALIZE instance (Fact m, Reflects q Int64, UnCyc t (ZqBasic q Int64), UnCyc t Int64, IFunctor t, IFElt t (ZqBasic q Int64), IFElt t Int64) => LiftCyc (Cyc t m (ZqBasic q Int64)) #-}
  
    {-# INLINABLE liftCyc #-}
    liftCyc = flip fmapCyc lift
  
  -----
  
  instance (Fact m, TensorGaussian t q) => GaussianCyc (CycG t m q) where
    tweakedGaussian = fmap Dec . R.tweakedGaussian
  
  instance (Fact m, TensorGaussian t Double) => GaussianCyc (Cyc t m Double) where
    tweakedGaussian = fmap CycDbl . L.tweakedGaussian
  
  -- CJP: no GaussianCyc for Int64, Integer, ZqBasic, pairs, or RRq
  
  -- | uses 'Double' precision for the intermediate Gaussian samples
  instance (TensorGaussian t Double, IFElt t Double, IFunctor t, Fact m, Mod zp,
            Lift zp (ModRep zp), CRTElt t zp, IFElt t (LiftOf zp))
    => CosetGaussianCyc (CycG t m zp) where
    {-# INLINABLE cosetGaussian #-}
    cosetGaussian v = (Dec <$>) . R.cosetGaussian v . unCycGDec
  
  -- | uses 'Double' for the intermediate Gaussian samples
  instance (CosetGaussianCyc (CycG t m (ZqBasic q Int64)))
    => CosetGaussianCyc (Cyc t m (ZqBasic q Int64)) where
    cosetGaussian v = fmap CycI64 . L.cosetGaussian v . unCycZqB
  
  -- CJP: no CosetGaussianCyc for Double, Int64, Integer, or pairs
  
  -----
  
  instance (CRTElt t r, ZeroTestable r, IntegralDomain r) -- ZT, ID for superclass
    => ExtensionCyc (CycG t) r where
    {-# SPECIALIZE instance (CRTElt t Int64)  => ExtensionCyc (CycG t) Int64  #-}
    {-# SPECIALIZE instance (CRTElt t Double) => ExtensionCyc (CycG t) Double #-}
    {-# SPECIALIZE instance (CRTElt t (ZqBasic q Int64), Reflects q Int64) => ExtensionCyc (CycG t) (ZqBasic q Int64) #-}
  
    -- lazily embed
    embed :: forall m m' . (m `Divides` m') => CycG t m r -> CycG t m' r
    embed (Scalar c) = Scalar c           -- keep as scalar
    embed (Sub (c :: CycG t l r)) = Sub c -- keep as subring element
      \\ transDivides @l @m @m'
    embed c = Sub c
  
    twace :: forall m m' . (m `Divides` m') => CycG t m' r -> CycG t m r
    twace (Pow u) = Pow $ twacePow u
    twace (Dec u) = Dec $ twaceDec u
    twace (CRT u) = either (cycPE . twaceCRTE) (cycPC . twaceCRTC) u
    twace (Scalar u) = Scalar u
    twace (Sub (c :: CycG t l r)) = Sub (twace c :: CycG t (FGCD l m) r)
                                    \\ gcdDivides @l @m
  
    powBasis :: forall m m' . (m `Divides` m') => Tagged m [CycG t m' r]
    powBasis = tag $ Pow <$> R.powBasis @m
  
    coeffsCyc L.Pow c' = Pow <$> R.coeffsPow (unCycGPow c')
    coeffsCyc L.Dec c' = Dec <$> R.coeffsDec (unCycGDec c')
  
  instance CRTElt t Double => ExtensionCyc (Cyc t) Double where
    embed = CycDbl . embed . unCycDbl
    twace = CycDbl . twace . unCycDbl
    powBasis = (CycDbl <$>) <$> powBasis
    coeffsCyc b = fmap CycDbl . coeffsCyc b . unCycDbl
  
  instance CRTElt t Int64 => ExtensionCyc (Cyc t) Int64 where
    embed = CycI64 . embed . unCycI64
    twace = CycI64 . twace . unCycI64
    powBasis = (CycI64 <$>) <$> powBasis
    coeffsCyc b = fmap CycI64 . coeffsCyc b . unCycI64
  
  instance (ExtensionCyc (CycG t) (ZqBasic q z))
    => ExtensionCyc (Cyc t) (ZqBasic q z) where
    embed = CycZqB . embed . unCycZqB
    twace = CycZqB . twace . unCycZqB
    powBasis = (CycZqB <$>) <$> powBasis
    coeffsCyc b = fmap CycZqB . coeffsCyc b . unCycZqB
  
  instance (ExtensionCyc (Cyc t) a, ExtensionCyc (Cyc t) b)
    => ExtensionCyc (Cyc t) (a,b) where
    {-# SPECIALIZE instance (ExtensionCyc (Cyc t) (ZqBasic q Int64), ExtensionCyc (Cyc t) b) => ExtensionCyc (Cyc t) (ZqBasic q Int64, b) #-}
  
    embed (CycPair a b) = CycPair (embed a) (embed b)
    twace (CycPair a b) = CycPair (twace a) (twace b)
    powBasis = zipWith CycPair <$> powBasis <*> powBasis
    coeffsCyc bas (CycPair a b) =
      zipWith CycPair (coeffsCyc bas a) (coeffsCyc bas b)
  
  instance (TensorPowDec t (RRq q r)) => ExtensionCyc (Cyc t) (RRq q r) where
    embed (PowRRq u) = PowRRq $ embedPow u
    embed (DecRRq u) = PowRRq $ embedPow $ toPow u
    twace (PowRRq u) = PowRRq $ twacePow u
    twace (DecRRq u) = DecRRq $ twaceDec u
    powBasis :: forall m m' . (m `Divides` m') => Tagged m [Cyc t m' (RRq q r)]
    powBasis = tag $ PowRRq <$> R.powBasis @m
    coeffsCyc L.Pow (PowRRq c) = PowRRq <$> R.coeffsPow c
    coeffsCyc L.Dec (DecRRq c) = DecRRq <$> R.coeffsDec c
    coeffsCyc L.Pow (DecRRq c) = PowRRq <$> R.coeffsPow (toPow c)
    coeffsCyc L.Dec (PowRRq c) = DecRRq <$> R.coeffsDec (toDec c)
  
  -- | Force to a non-'Sub' constructor (for internal use only).
  embed' :: forall t r l m . (l `Divides` m, CRTElt t r)
         => CycG t l r -> CycG t m r
  {-# INLINE embed' #-}
  embed' (Pow u) = Pow $ embedPow u
  embed' (Dec u) = Pow $ embedPow $ toPow u
  embed' (CRT u) = either (cycPE . embedCRTE) (cycPC . embedCRTC) u
  embed' (Scalar c) = Scalar c
  embed' (Sub (c :: CycG t k r)) = embed' c \\ transDivides @k @l @m
  
  -----
  
  instance (PPow pp, Prime (PrimePP pp), zpp ~ ZqBasic pp z, ToInteger z,
            CRTElt t zpp, TensorCRTSet t (ZqBasic (PrimePP pp) z),
            ExtensionCyc (CycG t) zpp)
    => CRTSetCyc (CycG t) (ZqBasic pp z) where
    crtSet :: forall m m' . (m `Divides` m') => Tagged m [CycG t m' zpp]
    crtSet = tag $ Pow <$> R.crtSet @m
    {-# INLINABLE crtSet #-}
  
  instance (CRTSetCyc (CycG t) (ZqBasic q z))
    => CRTSetCyc (Cyc t) (ZqBasic q z) where
    crtSet = (CycZqB <$>) <$> crtSet
    {-# INLINABLE crtSet #-}
  
  -- CJP TODO?: instance CRTSetCyc (Cyc t) (a,b)
  
  ---------- Promoted lattice operations ----------
  
  -- | Rescales relative to the powerful basis. This instance is
  -- provided for convenience, but usage of 'RescaleCyc' is preferred to
  -- explicitly specify which basis by which to rescale.
  instance (RescaleCyc (Cyc t m) a b, Fact m,
            Additive (Cyc t m a), Additive (Cyc t m b)) -- superclasses
   => Rescale (Cyc t m a) (Cyc t m b) where
    rescale = rescaleCyc L.Pow
    {-# INLINABLE rescale #-}
  
  -- CJP: can we avoid incoherent instances by changing instance heads
  -- and using overlapping instances with isomorphism constraints?
  
  instance (Fact m, Rescale a b, CRTElt t a, TensorPowDec t b)
    => RescaleCyc (CycG t m) a b where
    {-# SPECIALIZE instance (Fact m, Reflects q1 Int64, Reflects q2 Int64, CRTElt t (ZqBasic q1 Int64), TensorPowDec t (ZqBasic q2 Int64)) => RescaleCyc (CycG t m) (ZqBasic q1 Int64) (ZqBasic q2 Int64) #-}
  
    -- Optimized for subring constructors, for powerful basis.
    -- Analogs for decoding basis are not quite correct, because (* -1)
    -- doesn't commute with 'rescale' due to tiebreakers!
    rescaleCyc L.Pow (Scalar c) = Scalar $ rescale c
    rescaleCyc L.Pow (Sub c)    = Sub $ rescalePow c
  
    rescaleCyc L.Pow c          = Pow $ fmapI rescale $ unCycGPow c
    rescaleCyc L.Dec c          = Dec $ fmapI rescale $ unCycGDec c
    {-# INLINABLE rescaleCyc #-}
  
  -- | identity rescale (more specific)
  instance {-# OVERLAPPING #-} RescaleCyc (CycG t m) a a where
    -- No-op rescale
    rescaleCyc _ = id
    {-# INLINABLE rescaleCyc #-}
  
  -- | rescale from one modulus to another
  instance (RescaleCyc (CycG t m) (ZqBasic q z) (ZqBasic p z))
    => RescaleCyc (Cyc t m) (ZqBasic q z) (ZqBasic p z) where
    rescaleCyc b = CycZqB . rescaleCyc b . unCycZqB
    {-# INLINABLE rescaleCyc #-}
  
  -- | rescale from one modulus to another
  instance (Fact m, Rescale (RRq q r) (RRq p r),
            TensorPowDec t (RRq q r), TensorPowDec t (RRq p r))
    => RescaleCyc (Cyc t m) (RRq q r) (RRq p r) where
    rescaleCyc L.Pow (PowRRq u) = PowRRq $ rescale u
    rescaleCyc L.Pow (DecRRq u) = PowRRq $ rescale $ toPow u
    rescaleCyc L.Dec (DecRRq u) = DecRRq $ rescale u
    rescaleCyc L.Dec (PowRRq u) = DecRRq $ rescale $ toDec u
    {-# INLINABLE rescaleCyc #-}
  
  -- | no-op rescale for Cyc over pairs
  instance RescaleCyc (Cyc t m) (a,b) (a,b) where
    rescaleCyc = const id
    {-# INLINABLE rescaleCyc #-}
  
  -- | rescale up by one additional modulus
  instance (Fact m, Reflects q z, Reduce z b, ZeroTestable z,
            CRTElt t (ZqBasic q z), Module.C b (Cyc t m b))
    => RescaleCyc (Cyc t m) b (ZqBasic q z, b) where
  
    rescaleCyc = let q :: z = value @q
                 -- same method works for any basis
                 in \_ b -> CycPair zero $ (reduce q :: b) *> b
    {-# INLINABLE rescaleCyc #-}
  
  -- | specialized (faster) rescale-down by a single \(\Z_q\)
  instance (ToInteger z, Reflects q z, Reduce z b, Field b,
            FunctorCyc (Cyc t m) (ZqBasic q z) z,
            FunctorCyc (Cyc t m) z b,
            Additive (Cyc t m b), Module b (Cyc t m b))
    => RescaleCyc (Cyc t m) (ZqBasic q z, b) b where
  
    rescaleCyc bas (CycPair a b) =
      let q :: z = value @q
          x      = liftCyc (Just bas) a
      in recip (reduce q :: b) *> (b - reduceCyc x)
    {-# INLINABLE rescaleCyc #-}
  
  -- CJP: do we really need these? Just have client call rescaleCyc
  -- multiple times?
  
  -- | convenient rescale-down by multiple components at once
  instance (RescaleCyc (Cyc t m) (b,c) c, RescaleCyc (Cyc t m) (a,(b,c)) (b,c))
           => RescaleCyc (Cyc t m) (a,(b,c)) c where
  
    rescaleCyc bas a = rescaleCyc bas (rescaleCyc bas a :: Cyc t m (b,c))
    {-# INLINABLE rescaleCyc #-}
  
  -- | convenient rescale-down by multiple components at once
  instance (RescaleCyc (Cyc t m) (b,(c,d)) d,
            RescaleCyc (Cyc t m) (a,(b,(c,d))) (b,(c,d)))
           => RescaleCyc (Cyc t m) (a,(b,(c,d))) d where
  
    rescaleCyc bas a = rescaleCyc bas (rescaleCyc bas a :: Cyc t m (b,(c,d)))
    {-# INLINABLE rescaleCyc #-}
  
  -- | convenient rescale-down by multiple components at once
  instance (RescaleCyc (Cyc t m) (b,(c,(d,e))) e,
            RescaleCyc (Cyc t m) (a,(b,(c,(d,e)))) (b,(c,(d,e))))
           => RescaleCyc (Cyc t m) (a,(b,(c,(d,e)))) e where
  
    rescaleCyc bas a = rescaleCyc bas (rescaleCyc bas a :: Cyc t m (b,(c,(d,e))))
    {-# INLINABLE rescaleCyc #-}
  
  -----
  
  -- | promoted from base ring
  instance (Gadget gad (ZqBasic q z),
            -- satisfy Gadget's Ring superclass; remove if it goes away
            Fact m, CRTElt t (ZqBasic q z),
            ZeroTestable (ZqBasic q z), IntegralDomain (ZqBasic q z))
    => Gadget gad (CycG t m (ZqBasic q z)) where
    gadget = Scalar <$> gadget @gad
    {-# INLINABLE gadget #-}
    -- CJP: default 'encode' works because mul-by-Scalar is fast
  
  -- can't auto-derive because of ambiguity of gadget
  instance Gadget gad (CycG t m (ZqBasic q z))
    => Gadget gad (Cyc t m (ZqBasic q z)) where
    gadget = CycZqB <$> gadget @gad
    {-# INLINABLE gadget #-}
  
  instance (Gadget gad (Cyc t m a), Gadget gad (Cyc t m b))
    => Gadget gad (Cyc t m (a,b)) where
    gadget = (++) (flip CycPair zero <$> gadget @gad)
                  (     CycPair zero <$> gadget @gad)
    {-# INLINABLE gadget #-}
  
  -----
  
  instance (Fact m, Reduce a b, CRTElt t a, TensorPowDec t b)
    => Reduce (CycG t m a) (CycG t m b) where
    reduce (Pow u)                 = Pow    $ reduce u
    reduce (Dec u)                 = Dec    $ reduce u
    reduce (CRT u)                 = Pow    $ reduce $ either toPow toPow u
    reduce (Scalar c)              = Scalar $ reduce c
    reduce (Sub (c :: CycG t l a)) = Sub (reduce c :: CycG t l b)
    {-# INLINABLE reduce #-}
  
  instance (Reduce (CycG t m Int64) (CycG t m (ZqBasic q Int64)))
    => Reduce (Cyc t m Int64) (Cyc t m (ZqBasic q Int64)) where
    reduce = CycZqB . reduce . unCycI64
    {-# INLINABLE reduce #-}
  
  instance (Reflects q Int64, Functor (t m))
    => Reduce (Cyc t m Integer) (Cyc t m (ZqBasic q Int64)) where
    reduce (PowIgr u) = CycZqB $ Pow $ fmap reduce u
    reduce (DecIgr u) = CycZqB $ Dec $ fmap reduce u
    {-# INLINABLE reduce #-}
  
  instance (Reflects q Double, FunctorCyc (Cyc t m) Double (RRq q Double))
    => Reduce (Cyc t m Double) (Cyc t m (RRq q Double)) where
    reduce = fmapCyc Nothing reduce
    {-# INLINABLE reduce #-}
  
  instance (Reduce (Cyc t m z) (Cyc t m a), Reduce (Cyc t m z) (Cyc t m b))
    => Reduce (Cyc t m z) (Cyc t m (a,b)) where
    reduce z = CycPair (reduce z) (reduce z)
    {-# INLINABLE reduce #-}
  
  -- | promoted from base ring, using the powerful basis for best geometry
  instance (Decompose gad (ZqBasic q z), CRTElt t (ZqBasic q z), Fact m,
            -- for satisfying Decompose's Gadget superclass
            ZeroTestable (ZqBasic q z), IntegralDomain (ZqBasic q z),
            -- for satisfying Decompose's Reduce superclass w/o using m
            CRTElt t z, ZeroTestable z)
           => Decompose gad (CycG t m (ZqBasic q z)) where
  
    type DecompOf (CycG t m (ZqBasic q z)) = CycG t m z
  
    -- faster implementations: decompose directly in subring, which is
    -- correct because we decompose in powerful basis
    decompose (Scalar c) = Scalar <$> decompose @gad c
    decompose (Sub c) = Sub <$> decompose @gad c
    -- traverse: Traversable (CycRep t P m) and Applicative ZipList
    decompose (Pow u) = getZipList $ Pow <$> traverse (ZipList . decompose @gad) u
    decompose c = decompose @gad $ toPow' c
    {-# INLINABLE decompose #-}
  
  -- specific to Int64 because we need to know constructor for lift type
  instance (Decompose gad (CycG t m (ZqBasic q Int64)),
            -- for satisfying Decompose's Reduce superclass
            Reduce (Cyc t m Int64) (Cyc t m (ZqBasic q Int64)))
    => Decompose gad (Cyc t m (ZqBasic q Int64)) where
  
    type DecompOf (Cyc t m (ZqBasic q Int64)) = Cyc t m Int64
    decompose (CycZqB c) = CycI64 <$> decompose @gad c
    {-# INLINABLE decompose #-}
  
  instance (Decompose gad (Cyc t m a), Decompose gad (Cyc t m b),
           DecompOf (Cyc t m a) ~ DecompOf (Cyc t m b),
           -- for satisfying Decompose's Reduce superclass
           Reduce (DecompOf (Cyc t m a)) (Cyc t m (a, b)))
    => Decompose gad (Cyc t m (a,b)) where
    type DecompOf (Cyc t m (a,b)) = DecompOf (Cyc t m a)
    decompose (CycPair a b) = (++) (decompose @gad a) (decompose @gad b)
    {-# INLINABLE decompose #-}
  
  -----
  
  -- | promoted from base ring, using the decoding basis for best geometry
  instance (Correct gad (ZqBasic q z), CRTElt t (ZqBasic q z), Fact m,
            -- satisfy Gadget superclass
            ZeroTestable (ZqBasic q z), IntegralDomain (ZqBasic q z),
            Traversable (CycRep t D m))
    => Correct gad (CycG t m (ZqBasic q z)) where
    -- sequence: Monad [] and Traversable (CycRep t D m)
    -- sequenceA: Applicative (CycRep t D m) and Traversable (TaggedT gad [])
    correct bs = Dec *** (Dec <$>) $
                 second sequence $ fmap fst &&& fmap snd $ correct @gad <$>
                 sequenceA (unCycGDec <$> bs)
    {-# INLINABLE correct #-}
  
  -- specific to Int64 due to LiftOf. Can't auto-derive because of
  -- ambiguity of 'correct'
  instance Correct gad (CycG t m (ZqBasic q Int64))
    => Correct gad (Cyc t m (ZqBasic q Int64)) where
  
    correct = (CycZqB *** fmap CycI64) . correct @gad . fmap unCycZqB
    {-# INLINABLE correct #-}
    -- correct = coerce $
    --   (correct @gad :: [CycG t m (ZqBasic q Int64)]
    --                 -> (CycG t m (ZqBasic q Int64), [CycG t m Int64]))
  
  -- TODO: instance Correct gad (Cyc t m (a,b)) where
  -- seems hard; see Correct instance for pairs in Gadget.hs
  
  ---------- Change of representation (internal use only) ----------
  
  toPow', toDec', toCRT' :: (Fact m, CRTElt t r) => CycG t m r -> CycG t m r
  {-# INLINABLE toPow' #-}
  {-# INLINABLE toDec' #-}
  {-# INLINABLE toCRT' #-}
  
  -- | Force to powerful-basis representation (for internal use only).
  toPow' c@(Pow _)  = c
  toPow' (Dec u)    = Pow $ toPow u
  toPow' (CRT u)    = Pow $ either toPow toPow u
  toPow' (Scalar c) = Pow $ scalarPow c
  toPow' (Sub c)    = toPow' $ embed' c
  
  -- | Force to decoding-basis representation (for internal use only).
  toDec' (Pow u)    = Dec $ toDec u
  toDec' c@(Dec _)  = c
  toDec' (CRT u)    = Dec $ either toDec toDec u
  toDec' (Scalar c) = Dec $ toDec $ scalarPow c
  toDec' (Sub c)    = toDec' $ embed' c
  
  -- | Force to a CRT representation (for internal use only).
  toCRT' (Pow u)    = CRT $ toCRT u
  toCRT' (Dec u)    = CRT $ toCRT u
  toCRT' c@(CRT _)  = c
  toCRT' (Scalar c) = CRT $ scalarCRT c
  -- CJP: the following is the fastest algorithm for when both source
  -- and target have the same CRTr/CRTe choice.  It is not the fastest
  -- when the choices are different (it will do an unnecessary CRT if
  -- input is non-CRT), but this is an unusual case.  Note: both calls
  -- to toCRT' are necessary in general, because embed' may not preserve
  -- CRT representation!
  toCRT' (Sub c)    = toCRT' $ embed' $ toCRT' c
  
  ---------- Utility instances ----------
  
  instance (Random (t m r), Fact m, TensorCRT t Maybe r)
    => Random (CycG t m r) where
    random g = let (u,g') = random g
               in (either Pow (CRT . Right) u, g')
    {-# INLINABLE random #-}
  
    randomR _ = error "randomR non-sensical for CycG"
  
  deriving instance Random (CycG t m Double)        => Random (Cyc t m Double)
  deriving instance Random (CycG t m Int64)         => Random (Cyc t m Int64)
  deriving instance Random (CycG t m (ZqBasic q z)) => Random (Cyc t m (ZqBasic q z))
  
  instance (Random (Cyc t m a), Random (Cyc t m b)) => Random (Cyc t m (a,b)) where
    {-# SPECIALIZE instance (Fact m, Random (t m (ZqBasic q Int64)), TensorCRT t Maybe (ZqBasic q Int64), Random (Cyc t m b)) => Random (Cyc t m (ZqBasic q Int64, b)) #-}
    random g = let (a,g') = random g
                   (b,g'') = random g'
                   in (CycPair a b, g'')
    randomR _ = error "randomR non-sensical for Cyc"
    {-# INLINABLE random #-}
  
  instance (Random (t m Integer), Fact m) => Random (Cyc t m Integer) where
    random g = let (u,g') = random g in (PowIgr u, g')
    randomR = error "randomR nonsensical for Cyc over Integer"
    {-# INLINABLE random #-}
  
  instance (Random (t m (RRq q r)))
    => Random (Cyc t m (RRq q r)) where
    random g = let (u,g') = random g in (PowRRq u, g')
    randomR = error "randomR nonsensical for Cyc over (RRq q r)"
    {-# INLINABLE random #-}
  
  -----
  
  instance
    ( Show r
    , Fact m
    , r' ~ CRTExt r -- workaround TF in q'd constraint
    , forall m'. Fact m' => Show (t m' r)
    , forall m'. Fact m' => Show (t m' r')
    ) => Show (CycG t m r) where
    show (Pow x)         = "Cyc.Pow "    ++ show x
    show (Dec x)         = "Cyc.Dec "    ++ show x
    show (CRT (Left x))  = "Cyc.CRT "    ++ show x
    show (CRT (Right x)) = "Cyc.CRT "    ++ show x
    show (Scalar x)      = "Cyc.Scalar " ++ show x
    show (Sub x)         = "Cyc.Sub "    ++ show x
  
  deriving instance Show (CycG t m Double)        => Show (Cyc t m Double)
  deriving instance Show (CycG t m Int64)         => Show (Cyc t m Int64)
  deriving instance Show (CycG t m (ZqBasic q z)) => Show (Cyc t m (ZqBasic q z))
  deriving instance (Show (Cyc t m a), Show (Cyc t m b))
                    => Show (Cyc t m (a,b))
  
  deriving instance (Show (t m Integer))   => Show (Cyc t m Integer)
  deriving instance (Show (t m (RRq q r))) => Show (Cyc t m (RRq q r))
  
  -----
  
  instance
    ( NFData r
    , Fact m
    , r' ~ CRTExt r
    , forall m'. Fact m' => NFData (t m' r)
    , forall m'. Fact m' => NFData (t m' r')
    ) => NFData (CycG t m r) where
    rnf (Pow u)    = rnf u
    rnf (Dec u)    = rnf u
    rnf (CRT u)    = rnf u
    rnf (Scalar u) = rnf u
    rnf (Sub c)    = rnf c
  
  deriving instance NFData (CycG t m Double)        => NFData (Cyc t m Double)
  deriving instance NFData (CycG t m Int64)         => NFData (Cyc t m Int64)
  deriving instance NFData (CycG t m (ZqBasic q z)) => NFData (Cyc t m (ZqBasic q z))
  
  instance (NFData (Cyc t m a), NFData (Cyc t m b)) => NFData (Cyc t m (a,b)) where
    rnf (CycPair a b) = rnf a `seq` rnf b
  
  instance (Fact m, forall m' . Fact m' => NFData (t m' Integer))
    => NFData (Cyc t m Integer) where
    rnf (PowIgr u) = rnf u
    rnf (DecIgr u) = rnf u
  
  instance (Fact m, forall m' . Fact m' => NFData (t m' (RRq q r)))
    => NFData (Cyc t m (RRq q r)) where
    rnf (PowRRq u) = rnf u
    rnf (DecRRq u) = rnf u
  
  ---------- Protoable instances of Cyc/CycG ----------
  
  instance (Fact m, CRTElt t r, Protoable (CycRep t D m r))
      => Protoable (CycG t m r) where
    type ProtoType (CycG t m r) = ProtoType (CycRep t D m r)
    toProto (Dec uc) = toProto uc
    toProto x        = toProto $ toDec' x
    fromProto x = Dec <$> fromProto x
  
  instance (Fact m, CRTElt t Double, Protoable (CycG t m Double))
      => Protoable (Cyc t m Double) where
    type ProtoType (Cyc t m Double) = ProtoType (CycG t m Double)
    toProto = toProto . unCycDbl
    fromProto x = CycDbl <$> fromProto x
  
  instance (Fact m, CRTElt t Int64, Protoable (CycG t m Int64))
      => Protoable (Cyc t m Int64) where
    type ProtoType (Cyc t m Int64) = ProtoType (CycG t m Int64)
    toProto = toProto . unCycI64
    fromProto x = CycI64 <$> fromProto x
  
  instance (Fact m, CRTElt t Double, Protoable (CycG t m (ZqBasic q z)))
      => Protoable (Cyc t m (ZqBasic q z)) where
    type ProtoType (Cyc t m (ZqBasic q z)) = ProtoType (CycG t m (ZqBasic q z))
    toProto = toProto . unCycZqB
    fromProto x = CycZqB <$> fromProto x
  
  instance (Fact m, CRTElt t Double, TensorPowDec t (RRq q Double),
            Protoable (CycRep t D m (RRq q Double)))
      => Protoable (Cyc t m (RRq q Double)) where
    type ProtoType (Cyc t m (RRq q Double)) = ProtoType (CycG t m (RRq q Double))
    toProto (PowRRq x) = toProto $ toDec x
    toProto (DecRRq x) = toProto x
    fromProto x = DecRRq <$> fromProto x
  
  ---------- TH instances of FunctorCyc ----------
  
  -- CJP: the TH needs to appear before/after everything in the module
  -- so as not to screw up scoping
  
  let types = [ [t| Int64 |]
              , [t| Double |]
              , [t| ZqBasic $(varT (mkName "q")) $(varT (mkName "z")) |]
              , [t| RRq $(varT (mkName "q")) $(varT (mkName "r")) |]
              , [t| ( $(varT (mkName "a")) , $(varT (mkName "b"))) |] -- pair
              ]
      -- Instances that rely on IFunctor (in practice, Storable base
      -- types), and go between any two IFElt types.
      mkIFunctorCyc y z =
        [d|
         instance (Fact m, UnCyc t $y, UnCyc t $z,
                   IFunctor t, IFElt t $y, IFElt t $z)
           => FunctorCyc (Cyc t m) $y $z where
           fmapCyc (Just L.Pow) f = cycPow . fmapI f . unCycPow
           fmapCyc (Just L.Dec) f = cycDec . fmapI f . unCycDec
           fmapCyc Nothing      f = fmapCyc (Just L.Pow) f
         |]
      -- Instances that map to Integer, hence need to use fmap.
      mkFunctorCyc y =
        [d|
         instance (Fact m, Functor (t m), UnCyc t $y)
           => FunctorCyc (Cyc t m) $y Integer where
           fmapCyc (Just L.Pow) f = PowIgr . fmap f . unCycPow
           fmapCyc (Just L.Dec) f = DecIgr . fmap f . unCycDec
           fmapCyc Nothing      f = fmapCyc (Just L.Pow) f
         |]
      -- CJP TODO: if/when we get a way to convert Integer between Pow
      -- and Dec, we can also have instances that go *from* Integer
    in fmap concat $ sequence $
       (mkIFunctorCyc <$> types <*> types) ++ (mkFunctorCyc <$> types)
  