Copyright	(c) Eric Crockett 2011-2017 Chris Peikert 2011-2017
License	GPL-3
Maintainer	ecrockett0@email.com
Stability	experimental
Portability	POSIX \( \def\C{\mathbb{C}} \)
Safe Haskell	None
Language	Haskell2010

Crypto.Lol.CRTrans

Description

Classes and helper methods for the Chinese remainder transform and ring extensions.

Synopsis

class (Monad mon, Ring r) => CRTrans mon r where
- crtInfo :: Reflects m Int => TaggedT m mon (CRTInfo r)
class (Ring r, Ring (CRTExt r)) => CRTEmbed r where
- type CRTExt r
- toExt :: r -> CRTExt r
- fromExt :: CRTExt r -> r
type CRTInfo r = (Int -> r, r)

Documentation

class (Monad mon, Ring r) => CRTrans mon r where Source #

A ring that (possibly) supports invertible Chinese remainder transformations of various indices.

The values of crtInfo for different indices \(m\) should be consistent, in the sense that if \(\omega_m\), \(\omega_{m'}\) are respectively \(m\)th, \(m'\)th roots of unity where \(m\) divides \(m'\), then it should be the case that \(\omega_{m'}^{m'/m}=\omega_m\).

Methods

crtInfo :: Reflects m Int => TaggedT m mon (CRTInfo r) Source #

CRTInfo for a given index \(m\). The method itself may be slow, but the function it returns should be fast, e.g., via internal memoization.

Instances

CRTrans Maybe Double Source #	Returns `Nothing`
Instance details Defined in Crypto.Lol.CRTrans Methods crtInfo :: Reflects m Int => TaggedT m Maybe (CRTInfo Double) Source #
CRTrans Maybe Int Source #	Returns `Nothing`
Instance details Defined in Crypto.Lol.CRTrans Methods crtInfo :: Reflects m Int => TaggedT m Maybe (CRTInfo Int) Source #
CRTrans Maybe Int64 Source #	Returns `Nothing`
Instance details Defined in Crypto.Lol.CRTrans Methods crtInfo :: Reflects m Int => TaggedT m Maybe (CRTInfo Int64) Source #
CRTrans Maybe Integer Source #	Returns `Nothing`
Instance details Defined in Crypto.Lol.CRTrans Methods crtInfo :: Reflects m Int => TaggedT m Maybe (CRTInfo Integer) Source #
Transcendental a => CRTrans Maybe (Complex a) Source #	For testing ergonomics, we also have a `Maybe` instance of `CRTrans` for complex numbers.
Instance details Defined in Crypto.Lol.CRTrans Methods crtInfo :: Reflects m Int => TaggedT m Maybe (CRTInfo (Complex a)) Source #
Transcendental a => CRTrans Identity (Complex a) Source #	Complex numbers have `CRTrans` for any index \(m\)
Instance details Defined in Crypto.Lol.CRTrans Methods crtInfo :: Reflects m Int => TaggedT m Identity (CRTInfo (Complex a)) Source #
(CRTrans mon a, CRTrans mon b) => CRTrans mon (a, b) Source #	Product ring
Instance details Defined in Crypto.Lol.CRTrans Methods crtInfo :: Reflects m Int => TaggedT m mon (CRTInfo (a, b)) Source #
(Reflects q z, ToInteger z, PID z, Enum z, NFData z) => CRTrans Maybe (ZqBasic q z) Source #
Instance details Defined in Crypto.Lol.Types.Unsafe.ZqBasic Methods crtInfo :: Reflects m Int => TaggedT m Maybe (CRTInfo (ZqBasic q z)) Source #
(GFCtx fp d, NFData fp) => CRTrans Maybe (GF fp d) Source #
Instance details Defined in Crypto.Lol.Types.FiniteField Methods crtInfo :: Reflects m Int => TaggedT m Maybe (CRTInfo (GF fp d)) Source #

class (Ring r, Ring (CRTExt r)) => CRTEmbed r where Source #

A ring with a ring embedding into some ring CRTExt r that has an invertible CRT transformation for every positive index \(m\).

Associated Types

type CRTExt r Source #

Methods

toExt :: r -> CRTExt r Source #

Embeds from r to CRTExt r

fromExt :: CRTExt r -> r Source #

Projects from CRTExt r to r

Instances

CRTEmbed Double Source #	Embeds into the complex numbers \(\C\).
Instance details Defined in Crypto.Lol.CRTrans Associated Types type CRTExt Double :: Type Source # Methods toExt :: Double -> CRTExt Double Source # fromExt :: CRTExt Double -> Double Source #
CRTEmbed Int Source #	Embeds into the complex numbers \(\C\).
Instance details Defined in Crypto.Lol.CRTrans Associated Types type CRTExt Int :: Type Source # Methods toExt :: Int -> CRTExt Int Source # fromExt :: CRTExt Int -> Int Source #
CRTEmbed Int64 Source #	Embeds into the complex numbers \(\C\).
Instance details Defined in Crypto.Lol.CRTrans Associated Types type CRTExt Int64 :: Type Source # Methods toExt :: Int64 -> CRTExt Int64 Source # fromExt :: CRTExt Int64 -> Int64 Source #
CRTEmbed Integer Source #	Embeds into the complex numbers \(\C\). (May not have sufficient precision.)
Instance details Defined in Crypto.Lol.CRTrans Associated Types type CRTExt Integer :: Type Source # Methods toExt :: Integer -> CRTExt Integer Source # fromExt :: CRTExt Integer -> Integer Source #
Transcendental a => CRTEmbed (Complex a) Source #	Self-embed
Instance details Defined in Crypto.Lol.CRTrans Associated Types type CRTExt (Complex a) :: Type Source # Methods toExt :: Complex a -> CRTExt (Complex a) Source # fromExt :: CRTExt (Complex a) -> Complex a Source #
(CRTEmbed a, CRTEmbed b) => CRTEmbed (a, b) Source #	Product ring
Instance details Defined in Crypto.Lol.CRTrans Associated Types type CRTExt (a, b) :: Type Source # Methods toExt :: (a, b) -> CRTExt (a, b) Source # fromExt :: CRTExt (a, b) -> (a, b) Source #
(Reflects q z, ToInteger z, Ring (ZqBasic q z)) => CRTEmbed (ZqBasic q z) Source #	Embeds into the complex numbers \( \C \).
Instance details Defined in Crypto.Lol.Types.Unsafe.ZqBasic Associated Types type CRTExt (ZqBasic q z) :: Type Source # Methods toExt :: ZqBasic q z -> CRTExt (ZqBasic q z) Source # fromExt :: CRTExt (ZqBasic q z) -> ZqBasic q z Source #

type CRTInfo r = (Int -> r, r) Source #

Information that characterizes the (invertible) Chinese remainder transformation over a ring \(R\) (represented by the type r), namely:

a function that returns the \(i\)th power of some principal \(m\)th root of unity (for any integer \(i\))
the multiplicative inverse of \(\hat{m}\in R\).