Crypto.Lol.CRTrans

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

Documentation

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

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)

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

Returns Nothing

Defined in Crypto.Lol.CRTrans

Methods

crtInfo :: Reflects m Int => TaggedT m Maybe (CRTInfo Double)

CRTrans Maybe Int

Returns Nothing

Defined in Crypto.Lol.CRTrans

Methods

crtInfo :: Reflects m Int => TaggedT m Maybe (CRTInfo Int)

CRTrans Maybe Int64

Returns Nothing

Defined in Crypto.Lol.CRTrans

Methods

crtInfo :: Reflects m Int => TaggedT m Maybe (CRTInfo Int64)

CRTrans Maybe Integer

Returns Nothing

Defined in Crypto.Lol.CRTrans

Methods

crtInfo :: Reflects m Int => TaggedT m Maybe (CRTInfo Integer)

Transcendental a => CRTrans Maybe (Complex a)

For testing ergonomics, we also have a Maybe instance of CRTrans for complex numbers.

Defined in Crypto.Lol.CRTrans

Methods

crtInfo :: Reflects m Int => TaggedT m Maybe (CRTInfo (Complex a))

Transcendental a => CRTrans Identity (Complex a)

Complex numbers have CRTrans for any index \(m\)

Defined in Crypto.Lol.CRTrans

Methods

crtInfo :: Reflects m Int => TaggedT m Identity (CRTInfo (Complex a))

(CRTrans mon a, CRTrans mon b) => CRTrans mon (a, b)

Product ring

Defined in Crypto.Lol.CRTrans

Methods

crtInfo :: Reflects m Int => TaggedT m mon (CRTInfo (a, b))

(Reflects q z, ToInteger z, PID z, Enum z, NFData z) => CRTrans Maybe (ZqBasic q z)

Defined in Crypto.Lol.Types.Unsafe.ZqBasic

Methods

crtInfo :: Reflects m Int => TaggedT m Maybe (CRTInfo (ZqBasic q z))

(GFCtx fp d, NFData fp) => CRTrans Maybe (GF fp d)

Defined in Crypto.Lol.Types.FiniteField

Methods

crtInfo :: Reflects m Int => TaggedT m Maybe (CRTInfo (GF fp d))

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

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

Methods

toExt :: r -> CRTExt r

Embeds from r to CRTExt r

fromExt :: CRTExt r -> r

Projects from CRTExt r to r

Instances

CRTEmbed Double

Embeds into the complex numbers \(\C\).

Defined in Crypto.Lol.CRTrans

Associated Types

type CRTExt Double :: Type

Methods

toExt :: Double -> CRTExt Double

fromExt :: CRTExt Double -> Double

CRTEmbed Int

Embeds into the complex numbers \(\C\).

Defined in Crypto.Lol.CRTrans

Associated Types

type CRTExt Int :: Type

Methods

toExt :: Int -> CRTExt Int

fromExt :: CRTExt Int -> Int

CRTEmbed Int64

Embeds into the complex numbers \(\C\).

Defined in Crypto.Lol.CRTrans

Associated Types

type CRTExt Int64 :: Type

Methods

toExt :: Int64 -> CRTExt Int64

fromExt :: CRTExt Int64 -> Int64

CRTEmbed Integer

Embeds into the complex numbers \(\C\). (May not have sufficient precision.)

Defined in Crypto.Lol.CRTrans

Associated Types

type CRTExt Integer :: Type

Methods

toExt :: Integer -> CRTExt Integer

fromExt :: CRTExt Integer -> Integer

Transcendental a => CRTEmbed (Complex a)

Self-embed

Defined in Crypto.Lol.CRTrans

Associated Types

type CRTExt (Complex a) :: Type

Methods

toExt :: Complex a -> CRTExt (Complex a)

fromExt :: CRTExt (Complex a) -> Complex a

(CRTEmbed a, CRTEmbed b) => CRTEmbed (a, b)

Product ring

Defined in Crypto.Lol.CRTrans

Associated Types

type CRTExt (a, b) :: Type

Methods

toExt :: (a, b) -> CRTExt (a, b)

fromExt :: CRTExt (a, b) -> (a, b)

(Reflects q z, ToInteger z, Ring (ZqBasic q z)) => CRTEmbed (ZqBasic q z)

Embeds into the complex numbers \( \C \).

Defined in Crypto.Lol.Types.Unsafe.ZqBasic

Associated Types

type CRTExt (ZqBasic q z) :: Type

Methods

toExt :: ZqBasic q z -> CRTExt (ZqBasic q z)

fromExt :: CRTExt (ZqBasic q z) -> ZqBasic q z

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

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

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