Safe Haskell	None
Language	Haskell2010

Crypto.Lol.Cyclotomic.Tensor

Contents

Top-level CRT functions
Tensor indexing

Description

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

Synopsis

Documentation

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

Tensor is a container that supports 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. Many of the methods take and/or produce coefficient tensors relative to particular bases, but the tensor itself does not keep track of the corresponding basis. 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 over Double.

Associated Types

type TElt t r :: Constraint Source

Methods

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

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

entailFullT :: Tagged (t m r) ((Fact m, TElt t r) :- (Eq (t m r), ZeroTestable (t m r), Ring (t m r), NFData (t m r), Random (t m r))) Source

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

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

Converts a scalar to a tensor in the powerful basis

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

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

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

Multiply by g in the powerful/decoding basis

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

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 :: (Fact m, TElt t r, CRTrans 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) Source

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 mulGCRT, divGCRT, crt, crtInv.

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

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

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

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

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

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

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

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 :: (m `Divides` m', TElt t r) => t m' r -> [t m r] Source

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

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

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

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

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 Source

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) Source

Potentially optimized monadic fmap.

Instances

Tensor CT Source
Tensor RT Source

Top-level CRT functions

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

Convenience value indicating whether crtFuncs exists.

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

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

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

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

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

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

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

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

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

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

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

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'. (Tensor t, m `Divides` m', TElt t r, CRTrans r) => Maybe (t m r -> t m' r) Source

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 Source

A Kronecker product of zero of more matrices over r.

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

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

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

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

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

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)]) Source

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

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

The vector is made up of phi(m) blocks of phi(m')/phi(m) consecutive entries. Each block constains all those indices into the Pow (Dec) basis of O_m' that "lie above" the corresponding index into the Pow (Dec) basis of O_m.

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

The vector is made up of phi(m) blocks of phi(m')/phi(m) consecutive entries. Each block constains 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)) Source

Used for extracting coefficients in a relative pow/dec/crt basis Returns a vector of phi(m')/phi(m), each of dimension phi(m) where the i^th vector contains the indices into the source vector corresponding to the Z-coefficients of the i^th R-coefficient for the relative basis. See section "Two Index Transforms" and "Coefficients in Relative Bases" from the corresponding paper.

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

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

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

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

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

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

digitRev :: PP -> Int -> Int Source

Base-p digit reversal; input and output are in [0,p^e).