Safe Haskell | None |
---|---|
Language | Haskell2010 |
\( \def\Z{\mathbb{Z}} \) \( \def\Tw{\text{Tw}} \) \( \def\Tr{\text{Tr}} \) \( \def\CRT{\text{CRT}} \) \( \def\O{\mathcal{O}} \)
Interface for cyclotomic tensors, and helper functions for tensor indexing.
- class (TElt t Double, TElt t (Complex Double)) => Tensor t where
- type TElt t r :: Constraint
- hasCRTFuncs :: forall t m mon r. (CRTrans mon r, Tensor t, Fact m, TElt t r) => TaggedT (t m r) mon ()
- scalarCRT :: (CRTrans mon r, Tensor t, Fact m, TElt t r) => mon (r -> t m r)
- mulGCRT :: (CRTrans mon r, Tensor t, Fact m, TElt t r) => mon (t m r -> t m r)
- divGCRT :: (CRTrans mon r, Tensor t, Fact m, TElt t r) => mon (t m r -> t m r)
- crt :: (CRTrans mon r, Tensor t, Fact m, TElt t r) => mon (t m r -> t m r)
- crtInv :: (CRTrans mon r, Tensor t, Fact m, TElt t r) => mon (t m r -> t m r)
- twaceCRT :: forall t m m' mon r. (CRTrans mon r, Tensor t, m `Divides` m', TElt t r) => mon (t m' r -> t m r)
- embedCRT :: forall t m m' mon r. (CRTrans mon r, Tensor t, m `Divides` m', TElt t r) => mon (t m r -> t m' r)
- data Kron r
- indexK :: Ring r => Kron r -> Int -> Int -> r
- gCRTK :: (Fact m, CRTrans mon r) => TaggedT m mon (Kron r)
- gInvCRTK :: (Fact m, CRTrans mon r) => TaggedT m mon (Kron r)
- twCRTs :: (Fact m, CRTrans mon r) => TaggedT m mon (Kron r)
- zmsToIndexFact :: Fact m => Tagged m (Int -> Int)
- indexInfo :: forall m m'. m `Divides` m' => Tagged '(m, m') ([(Int, Int, Int)], Int, Int, [(Int, Int)])
- extIndicesPowDec :: m `Divides` m' => Tagged '(m, m') (Vector Int)
- extIndicesCRT :: forall m m'. m `Divides` m' => Tagged '(m, m') (Vector Int)
- extIndicesCoeffs :: forall m m'. m `Divides` m' => Tagged '(m, m') (Vector (Vector Int))
- baseIndicesPow :: forall m m'. m `Divides` m' => Tagged '(m, m') (Vector (Int, Int))
- baseIndicesDec :: forall m m'. m `Divides` m' => Tagged '(m, m') (Vector (Maybe (Int, Bool)))
- baseIndicesCRT :: forall m m'. m `Divides` m' => Tagged '(m, m') (Vector Int)
- digitRev :: PP -> Int -> Int
Documentation
class (TElt t Double, TElt t (Complex Double)) => Tensor t where Source #
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 constraints are for convenience, to ensure that we
can sample error tensors of Double
s.
WARNING: as with all fixed-point arithmetic, the methods
in Tensor
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 method is determined by the linear transform it
implements.
entailIndexT, entailEqT, entailZTT, entailNFDataT, entailRandomT, entailShowT, entailModuleT, scalarPow, l, lInv, mulGPow, mulGDec, divGPow, divGDec, crtFuncs, tGaussianDec, gSqNormDec, twacePowDec, embedPow, embedDec, crtExtFuncs, coeffs, powBasisPow, crtSetDec, fmapT, fmapTM, zipWithT, unzipT
type TElt t r :: Constraint Source #
Constraints needed by t
to hold type r
.
entailIndexT :: Tagged (t m r) (Fact m :- (Applicative (t m), Traversable (t m))) Source #
Properties that hold for any index. Use with \\
.
entailEqT :: Tagged (t m r) ((Eq r, Fact m, TElt t r) :- Eq (t m r)) Source #
Holds for any (legal) fully-applied tensor. Use with \\
.
entailZTT :: Tagged (t m r) ((ZeroTestable r, Fact m, TElt t r) :- ZeroTestable (t m r)) Source #
Holds for any (legal) fully-applied tensor. Use with \\
.
entailNFDataT :: Tagged (t m r) ((NFData r, Fact m, TElt t r) :- NFData (t m r)) Source #
Holds for any (legal) fully-applied tensor. Use with \\
.
entailRandomT :: Tagged (t m r) ((Random r, Fact m, TElt t r) :- Random (t m r)) Source #
Holds for any (legal) fully-applied tensor. Use with \\
.
entailShowT :: Tagged (t m r) ((Show r, Fact m, TElt t r) :- Show (t m r)) Source #
Holds for any (legal) fully-applied tensor. Use with \\
.
entailModuleT :: Tagged (GF fp d, t m fp) ((GFCtx fp d, Fact m, TElt t fp) :- Module (GF fp d) (t m fp)) Source #
Holds for any (legal) fully-applied tensor. Use with \\
.
scalarPow :: (Additive r, Fact m, TElt t r) => r -> t m r Source #
Convert a scalar to a tensor in the powerful basis.
l, lInv :: (Additive r, Fact m, TElt t r) => t m r -> t m r Source #
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 Source #
Multiply by \(g_m\) in the powerful/decoding basis
divGPow, divGDec :: (ZeroTestable r, IntegralDomain r, Fact m, TElt t r) => t m r -> Maybe (t m r) Source #
Divide by \(g_m\) 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_m\).
crtFuncs :: (CRTrans mon r, Fact m, TElt t r) => mon (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 scalarCRT
, mulGCRT
, divGCRT
, crt
, crtInv
.
tGaussianDec :: (OrdFloat q, Random q, TElt t q, ToRational v, Fact m, MonadRandom rnd) => v -> rnd (t m q) Source #
Sample from the "tweaked" Gaussian error distribution \(t\cdot D\) in the decoding basis, where \(D\) has scaled variance \(v\).
gSqNormDec :: (Ring r, Fact m, TElt t r) => t m r -> r Source #
Given the coefficient tensor of \(e\) with respect to the decoding basis of \(R\), 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\).
twacePowDec :: (Ring r, 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 :: (Additive r, m `Divides` m', TElt t r) => t m r -> t m' r Source #
The embed
linear transformations, for the powerful and
decoding bases.
crtExtFuncs :: (CRTrans mon r, m `Divides` m', TElt t r) => mon (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 :: (Ring r, m `Divides` m', TElt t r) => t m' r -> [t m r] Source #
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] 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 #
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
.
zipWithT :: (Fact m, TElt t a, TElt t b, TElt t c) => (a -> b -> c) -> t m a -> t m b -> t m c Source #
Potentially optimized zipWith for types that satisfy TElt
.
unzipT :: (Fact m, TElt t (a, b), TElt t a, TElt t b) => t m (a, b) -> (t m a, t m b) Source #
Potentially optimized unzip for types that satisfy TElt
.
Top-level CRT functions
hasCRTFuncs :: forall t m mon r. (CRTrans mon r, Tensor t, Fact m, TElt t r) => TaggedT (t m r) mon () Source #
Convenience value indicating whether crtFuncs
exists.
scalarCRT :: (CRTrans mon r, Tensor t, Fact m, TElt t r) => mon (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 :: (CRTrans mon r, Tensor t, Fact m, TElt t r) => mon (t m r -> t m r) Source #
Multiply by \(g_m\) in the CRT basis. (This function is simply an
appropriate entry from crtFuncs
.)
divGCRT :: (CRTrans mon r, Tensor t, Fact m, TElt t r) => mon (t m r -> t m r) Source #
Divide by \(g_m\) in the CRT basis. (This function is simply an
appropriate entry from crtFuncs
.)
crt :: (CRTrans mon r, Tensor t, Fact m, TElt t r) => mon (t m r -> t m r) Source #
The CRT transform. (This function is simply an appropriate entry
from crtFuncs
.)
crtInv :: (CRTrans mon r, Tensor t, Fact m, TElt t r) => mon (t m r -> t m r) Source #
The inverse CRT transform. (This function is simply an
appropriate entry from crtFuncs
.)
twaceCRT :: forall t m m' mon r. (CRTrans mon r, Tensor t, m `Divides` m', TElt t r) => mon (t m' r -> t m r) Source #
The "tweaked trace" function for tensors in the CRT basis:
For cyclotomic indices \(m \mid m'\),
\(\Tw(x) = (\hat{m}/\hat{m}') \cdot \Tr((g'/g) \cdot x)\).
(This function is simply an appropriate entry from crtExtFuncs
.)
embedCRT :: forall t m m' mon r. (CRTrans mon r, Tensor t, m `Divides` m', TElt t r) => mon (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
.)
Special vectors/matrices
gCRTK :: (Fact m, CRTrans mon r) => TaggedT m mon (Kron r) Source #
A \(\varphi(m)\)-by-1 matrix of the CRT coefficients of \(g_m\), for \(m\)th cyclotomic.
gInvCRTK :: (Fact m, CRTrans mon r) => TaggedT m mon (Kron r) Source #
A \(\varphi(m)\)-by-1 matrix of the inverse CRT coefficients of \(g_m\), for \(m\)th cyclotomic.
twCRTs :: (Fact m, CRTrans mon r) => TaggedT m mon (Kron r) Source #
The "tweaked" \(\CRT^*\) matrix: \(\CRT^* \cdot \text{diag}(\sigma(g_m))\).
Tensor indexing
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 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 \(\varphi(m)\) and \(\varphi(m')\). The final component is a pair \( ( \varphi(p^e), \varphi(p^{e'}))\) for each triple in the first component.
extIndicesPowDec :: m `Divides` m' => Tagged '(m, m') (Vector Int) Source #
A vector of \(\varphi(m)\) entries, where the \(i\)th entry is the index into the powerful/decoding basis of \(\O_{m'}\) of the \(i\)th entry of the powerful/decoding basis of \(\O_m\).
extIndicesCRT :: forall m m'. m `Divides` m' => Tagged '(m, m') (Vector Int) Source #
A vector of \(\varphi(m)\) blocks of \(\varphi(m')/\varphi(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)) Source #
The \(i_0\)th entry of the \(i_1\)th vector is
fromIndexPair
\((i_1,i_0)\).
baseIndicesPow :: forall m m'. m `Divides` m' => Tagged '(m, m') (Vector (Int, Int)) Source #
A lookup table for toIndexPair
applied to indices \([\varphi(m')]\).
baseIndicesDec :: forall m m'. m `Divides` m' => Tagged '(m, m') (Vector (Maybe (Int, Bool))) Source #
A lookup table for baseIndexDec
applied to indices \([\varphi(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.