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$.

Minimal complete definition

crtInfo

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

Methods

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

CRTrans Maybe Int

Returns Nothing

Methods

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

CRTrans Maybe Int64

Returns Nothing

Methods

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

CRTrans Maybe Integer

Returns Nothing

Methods

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

(Monad mon, Transcendental a) => CRTrans mon (Complex a)

Complex numbers have CRTrans for any index $m$

Methods

crtInfo :: Reflects k1 m Int => TaggedT * k1 m mon (CRTInfo (Complex a))

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

Product ring

Methods

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

GFCtx k fp d => CRTrans Maybe (GF k fp d)

Methods

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

(Reflects k q z, ToInteger z, PID z, Enumerable (ZqBasic k q z)) => CRTrans Maybe (ZqBasic k q z)

Methods

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

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$.

Minimal complete definition

toExt, fromExt

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$.

Associated Types

type CRTExt Double :: *

Methods

toExt :: Double -> CRTExt Double

fromExt :: CRTExt Double -> Double

CRTEmbed Int

Embeds into the complex numbers $\C$.

Associated Types

type CRTExt Int :: *

Methods

toExt :: Int -> CRTExt Int

fromExt :: CRTExt Int -> Int

CRTEmbed Int64

Embeds into the complex numbers $\C$.

Associated Types

type CRTExt Int64 :: *

Methods

toExt :: Int64 -> CRTExt Int64

fromExt :: CRTExt Int64 -> Int64

CRTEmbed Integer

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

Associated Types

type CRTExt Integer :: *

Methods

toExt :: Integer -> CRTExt Integer

fromExt :: CRTExt Integer -> Integer

Transcendental a => CRTEmbed (Complex a)

Self-embed

Associated Types

type CRTExt (Complex a) :: *

Methods

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

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

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

Product ring

Associated Types

type CRTExt (a, b) :: *

Methods

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

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

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

Embeds into the complex numbers $\C$.

Associated Types

type CRTExt (ZqBasic k q z) :: *

Methods

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

fromExt :: CRTExt (ZqBasic k q z) -> ZqBasic k 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$.