content: {-|
  Module      : Crypto.Lol.Cyclotomic.Language
  Description : Abstract interfaces for operations on cyclotomic rings.
  Copyright   : (c) Chris Peikert, 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}} \)
  -}
  
  {-# LANGUAGE ConstraintKinds       #-}
  {-# LANGUAGE FlexibleContexts      #-}
  {-# LANGUAGE MultiParamTypeClasses #-}
  {-# LANGUAGE RankNTypes            #-}
  {-# LANGUAGE ScopedTypeVariables   #-}
  {-# LANGUAGE TypeFamilies          #-}
  {-# LANGUAGE TypeOperators         #-}
  
  module Crypto.Lol.Cyclotomic.Language
  where
  
  import Crypto.Lol.Prelude
  
  import Control.Monad.Random (MonadRandom)
  
  -- | Used to specify a basis for cyclotomic operations
  data Basis = Pow | Dec
  
  -- | Operations on cyclotomics.
  class Cyclotomic cmr where
    -- | Multiply by the special element \( g \).
    mulG :: cmr -> cmr
  
    -- | Divide by the special element \( g \), returning 'Nothing' if
    -- the input is not evenly divisible.
    divG :: cmr -> Maybe cmr
  
    -- | Yield an equivalent element that /may/ be in
    -- powerful\/decoding\/CRT representation.  This can serve as an
    -- optimization hint. E.g., call 'adviseCRT' prior to multiplying a
    -- value by many other values.
    advisePow, adviseDec, adviseCRT :: cmr -> cmr
  
  class GSqNormCyc cm r where
    -- | Yield the scaled squared norm of \( g_m \cdot e \) under the
    -- canonical embedding, namely, \( \hat{m}^{-1} \cdot \| \sigma(g_m
    -- \cdot e) \|^2 \).
    gSqNorm :: cm r -> r
  
  -- | Sampling from tweaked Gaussian distributions over cyclotomic
  -- number fields.
  class GaussianCyc cmq where
    -- | Sample from the "tweaked" Gaussian distribution \( t \cdot D
    -- \), where \( D \) has scaled variance \( v \).
    tweakedGaussian :: (ToRational v, MonadRandom rnd) => v -> rnd cmq
  
  -- | Sampling from /discretized/ tweaked Gaussian distributions over
  -- cyclotomic number rings.
  class RoundedGaussianCyc cmz where
    -- | Sample from the tweaked Gaussian with given scaled variance,
    -- deterministically rounded using the decoding basis.
    roundedGaussian :: (ToRational v, MonadRandom rnd) => v -> rnd cmz
  
  -- | Sampling from tweaked Gaussian distributions, discretized to
  -- mod-p cosets of cyclotomic number rings.
  class CosetGaussianCyc rp where
    -- | Sample from the tweaked Gaussian with scaled variance \( v
    -- \cdot p^2 \), deterministically rounded to the given coset of
    -- \( R_p \) using the decoding basis.
    cosetGaussian :: (ToRational v, MonadRandom rnd)
                  => v -> rp -> rnd (LiftOf rp)
  
  -- | Cyclotomic extensions \( \O_{m'}/\O_m \).
  class ExtensionCyc c r where
    -- | Embed into a cyclotomic extension.
    embed :: (m `Divides` m') => c m r -> c m' r
  
    -- | The "tweaked trace" (twace) \( \Tw(x) = (\hat{m} / \hat{m}')
    -- \cdot \Tr((g' / g) \cdot x) \), which is the left-inverse of
    -- 'embed' (i.e., @twace . embed == id@).
    twace :: (m `Divides` m') => c m' r -> c m r
  
    -- | The relative powerful/decoding bases of the extension.
    powBasis :: (m `Divides` m') => Tagged m [c m' r]
  
    -- | Yield the coefficient vector with respect to the given
    -- (relative) basis of the extension.
    coeffsCyc :: (m `Divides` m') => Basis -> c m' r -> [c m r]
  
  coeffsPow, coeffsDec :: (ExtensionCyc c r, m `Divides` m') => c m' r -> [c m r]
  -- | 'coeffsCyc' specialized to the powerful basis.
  coeffsPow = coeffsCyc Pow
  -- | 'coeffsCyc' specialized to the decoding basis.
  coeffsDec = coeffsCyc Dec
  
  -- | Relative CRT sets of cyclotomic extensions.
  class ExtensionCyc c r => CRTSetCyc c r where
    -- | The relative mod-@r@ CRT set of the extension.
    crtSet :: (m `Divides` m') => Tagged m [c m' r]
  
  -- | Map over coefficients in a specified basis.
  class FunctorCyc cm a b where
    -- | Map in the specified basis (where 'Nothing' indicates that
    -- any 'Basis' may be used).
    fmapCyc :: Maybe Basis -> (a -> b) -> cm a -> cm b
  
  -- | Convenient specializations of 'fmapCyc'.
  fmapAny, fmapPow, fmapDec :: FunctorCyc cm a b => (a -> b) -> cm a -> cm b
  fmapAny = fmapCyc   Nothing
  fmapPow = fmapCyc $ Just Pow
  fmapDec = fmapCyc $ Just Dec
  
  -- | Fold over coefficients in a specified basis.
  class FoldableCyc cm a where
    -- | Fold in the specified basis (where 'Nothing' indicates that
    -- any 'Basis' may be used).
    foldrCyc :: Maybe Basis -> (a -> b -> b) -> b -> cm a -> b
  
  -- | Convenient specializations of 'foldrCyc'.
  foldrAny, foldrPow, foldrDec :: FoldableCyc cm a => (a -> b -> b) -> b -> cm a -> b
  foldrAny = foldrCyc   Nothing
  foldrPow = foldrCyc $ Just Pow
  foldrDec = foldrCyc $ Just Dec
  
  -- | Reduce on a cyclotomic (in an arbitrary basis).
  reduceCyc :: (FunctorCyc cm a b, Reduce a b) => cm a -> cm b
  reduceCyc = fmapAny reduce
  
  -- | Lift a cyclotomic in a specified basis.
  class LiftCyc cmr where
    -- | Lift in the specified basis (where 'Nothing' indicates that any
    -- 'Basis' may be used).
    liftCyc :: Maybe Basis -> cmr -> LiftOf cmr
  
  -- | Convenient specializations of 'liftCyc'.
  liftAny, liftPow, liftDec :: LiftCyc cmr => cmr -> LiftOf cmr
  liftAny = liftCyc   Nothing
  liftPow = liftCyc $ Just Pow
  liftDec = liftCyc $ Just Dec
  
  -- | Rescaling on cyclotomics from one base ring to another. (This is
  -- a separate class because there are optimized rescaling algorithms
  -- that can't be implemented using 'FunctorCyc'.)
  class RescaleCyc cm a b where
    -- | Rescale in the given basis.
    rescaleCyc :: Basis -> cm a -> cm b
  
  rescalePow, rescaleDec :: (RescaleCyc cm a b) => cm a -> cm b
  -- | 'rescaleCyc' specialized to the powerful basis.
  rescalePow = rescaleCyc Pow
  -- | 'rescaleCyc' specialized to the decoding basis.
  rescaleDec = rescaleCyc Dec
  
  