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\).