Crypto.Lol.Cyclotomic.Tensor

Interface for cyclotomic tensors, and helper functions for tensor indexing.

Documentation

class (TElt t Double, TElt t (Complex Double)) => Tensor t where

Tensor encapsulates all the core linear transformations needed for cyclotomic ring arithmetic.

The type t m r represents a cyclotomic coefficient tensor of index m over base ring r. Most of the methods represent linear transforms corresponding to operations in particular bases. CRT-related methods are wrapped in Maybe because they are well-defined only when a CRT basis exists over the ring r for index m.

The superclass constraint is for convenience, to ensure that we can sample error tensors of Doubles.

Associated Types

type TElt t r :: Constraint

Constraints needed by t to hold type r.

Methods

entailIndexT :: Tagged (t m r) (Fact m :- (Applicative (t m), Traversable (t m)))

Properties that hold for any index. Use with \\.

entailEqT :: Tagged (t m r) ((Eq r, Fact m, TElt t r) :- Eq (t m r))

Properties that hold for any (legal) fully-applied tensor. Use with \\.

entailZTT :: Tagged (t m r) ((ZeroTestable r, Fact m, TElt t r) :- ZeroTestable (t m r))

entailRingT :: Tagged (t m r) ((Ring r, Fact m, TElt t r) :- Ring (t m r))

entailNFDataT :: Tagged (t m r) ((NFData r, Fact m, TElt t r) :- NFData (t m r))

entailRandomT :: Tagged (t m r) ((Random r, Fact m, TElt t r) :- Random (t m r))

scalarPow :: (Ring r, Fact m, TElt t r) => r -> t m r

Converts a scalar to a tensor in the powerful basis

l, lInv :: (Ring r, Fact m, TElt t r) => t m r -> t m r

l converts from decoding-basis representation to powerful-basis representation; lInv is its inverse.

mulGPow, mulGDec :: (Ring r, Fact m, TElt t r) => t m r -> t m r

Multiply by g in the powerful/decoding basis

divGPow, divGDec :: (ZeroTestable r, IntegralDomain r, Fact m, TElt t r) => t m r -> Maybe (t m r)

Divide by g in the powerful/decoding basis. The Maybe output indicates that the operation may fail, which happens exactly when the input is not divisible by g.

crtFuncs :: (ZeroTestable r, IntegralDomain r, CRTrans r, Fact m, TElt t r) => Maybe (r -> t m r, t m r -> t m r, t m r -> t m r, t m r -> t m r, t m r -> t m r)

A tuple of all the operations relating to the CRT basis, in a single Maybe value for safety. Clients should typically not use this method directly, but instead call the corresponding top-level functions: the elements of the tuple correpond to the functions scalarCRT, mulGCRT, divGCRT, crt, crtInv.

tGaussianDec :: (OrdFloat q, Random q, TElt t q, ToRational v, Fact m, MonadRandom rnd) => v -> rnd (t m q)

Sample from the "skewed" Gaussian error distribution t*D in the decoding basis, where D has scaled variance v.

twacePowDec :: (Ring r, m `Divides` m', TElt t r) => t m' r -> t m r

The twace linear transformation, which is the same in both the powerful and decoding bases.

embedPow, embedDec :: (Ring r, m `Divides` m', TElt t r) => t m r -> t m' r

The embed linear transformations, for the powerful and decoding bases.

crtExtFuncs :: (ZeroTestable r, IntegralDomain r, CRTrans r, m `Divides` m', TElt t r) => Maybe (t m' r -> t m r, t m r -> t m' r)

A tuple of all the extension-related operations involving the CRT bases, for safety. Clients should typically not use this method directly, but instead call the corresponding top-level functions: the elements of the tuple correpond to the functions twaceCRT, embedCRT.

coeffs :: (Ring r, m `Divides` m', TElt t r) => t m' r -> [t m r]

Map a tensor in the powerful/decoding/CRT basis, representing an O_m' element, to a vector of tensors representing O_m elements in the same kind of basis.

powBasisPow :: (Ring r, TElt t r, m `Divides` m') => Tagged m [t m' r]

The powerful extension basis w.r.t. the powerful basis.

crtSetDec :: (PrimeField fp, m `Divides` m', Coprime (PToF (CharOf fp)) m', TElt t fp) => Tagged m [t m' fp]

A list of tensors representing the mod-p CRT set of the extension.

fmapT :: (Fact m, TElt t a, TElt t b) => (a -> b) -> t m a -> t m b

Potentially optimized version of fmap when the input and output element types satisfy TElt.

fmapTM :: (Monad mon, Fact m, TElt t a, TElt t b) => (a -> mon b) -> t m a -> mon (t m b)

Potentially optimized monadic fmap.

Instances

Tensor CT

Tensor RT

Top-level CRT functions

hasCRTFuncs :: forall t m r. (ZeroTestable r, IntegralDomain r, CRTrans r, Tensor t, Fact m, TElt t r) => TaggedT (t m r) Maybe ()

Convenience value indicating whether crtFuncs exists.

scalarCRT :: (ZeroTestable r, IntegralDomain r, CRTrans r, Tensor t, Fact m, TElt t r) => Maybe (r -> t m r)

Yield a tensor for a scalar in the CRT basis. (This function is simply an appropriate entry from crtFuncs.)

mulGCRT :: (ZeroTestable r, IntegralDomain r, CRTrans r, Tensor t, Fact m, TElt t r) => Maybe (t m r -> t m r)

Multiply by g in the CRT basis. (This function is simply an appropriate entry from crtFuncs.)

divGCRT :: (ZeroTestable r, IntegralDomain r, CRTrans r, Tensor t, Fact m, TElt t r) => Maybe (t m r -> t m r)

Divide by g in the CRT basis. (This function is simply an appropriate entry from crtFuncs.)

crt :: (ZeroTestable r, IntegralDomain r, CRTrans r, Tensor t, Fact m, TElt t r) => Maybe (t m r -> t m r)

The CRT transform. (This function is simply an appropriate entry from crtFuncs.)

crtInv :: (ZeroTestable r, IntegralDomain r, CRTrans r, Tensor t, Fact m, TElt t r) => Maybe (t m r -> t m r)

The inverse CRT transform. (This function is simply an appropriate entry from crtFuncs.)

twaceCRT :: forall t r m m'. (ZeroTestable r, IntegralDomain r, CRTrans r, Tensor t, m `Divides` m', TElt t r) => Maybe (t m' r -> t m r)

The "tweaked trace" function for tensors in the CRT basis: For cyclotomic indices m | m', Tw(x) = (mhat/m'hat) * Tr(g'/g * x). (This function is simply an appropriate entry from crtExtFuncs.)

embedCRT :: forall t r m m'. (ZeroTestable r, IntegralDomain r, CRTrans r, Tensor t, m `Divides` m', TElt t r) => Maybe (t m r -> t m' r)

Embed a tensor with index m in the CRT basis to a tensor with index m' in the CRT basis. (This function is simply an appropriate entry from crtExtFuncs.)

Tensor indexing

data Matrix r

A Kronecker product of zero of more matrices over r.

indexM :: Ring r => Matrix r -> Int -> Int -> r

Extract the (i,j) element of a Matrix.

twCRTs :: (Fact m, CRTrans r) => TaggedT m Maybe (Matrix r)

The "tweaked" CRT^* matrix: CRT^* . diag(sigma(g_m)).

zmsToIndexFact :: Fact m => Tagged m (Int -> Int)

Convert a Z_m^* index to a linear tensor index in [m].

indexInfo :: forall m m'. m `Divides` m' => Tagged `(m, m')` ([(Int, Int, Int)], Int, Int, [(Int, Int)])

A collection of useful information for working with tensor extensions. The first component is a list of triples (p,e,e') where e, e' are respectively the exponents of prime p in m, m'. The next two components are phi(m) and phi(m'). The final component is a pair (phi(p^e), phi(p^e')) for each triple in the first component.

extIndicesPowDec :: m `Divides` m' => Tagged `(m, m')` (Vector Int)

A vector of phi(m) entries, where the ith entry is the index into the powerful/decoding basis of O_m' of the ith entry of the powerful/decoding basis of O_m.

extIndicesCRT :: forall m m'. m `Divides` m' => Tagged `(m, m')` (Vector Int)

A vector of phi(m) blocks of phi(m')/phi(m) consecutive entries. Each block contains all those indices into the CRT basis of O_m' that "lie above" the corresponding index into the CRT basis of O_m.

extIndicesCoeffs :: forall m m'. m `Divides` m' => Tagged `(m, m')` (Vector (Vector Int))

The i0th entry of the i1th vector is fromIndexPair (i1,i0).

baseIndicesPow :: forall m m'. m `Divides` m' => Tagged `(m, m')` (Vector (Int, Int))

A lookup table for toIndexPair applied to indices [phi(m')].

baseIndicesDec :: forall m m'. m `Divides` m' => Tagged `(m, m')` (Vector (Maybe (Int, Bool)))

A lookup table for baseIndexDec applied to indices [phi(m')].

baseIndicesCRT :: forall m m'. m `Divides` m' => Tagged `(m, m')` (Vector Int)

Same as baseIndicesPow, but only includes the second component of each pair.

digitRev :: PP -> Int -> Int

Base-p digit reversal; input and output are in [p^e].