Crypto.Lol.CRTrans

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

Documentation

class Ring r => CRTrans 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, omega' are respectively the values returned for m, m' where m' divides m, then it should be the case that omega^(m/m')=omega'.

Minimal complete definition

Nothing

Methods

crtInfo :: Int -> Maybe (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. The default implementation returns Nothing.

Instances

CRTrans Double

CRTrans Int

CRTrans Int64

CRTrans Integer

Transcendental a => CRTrans (Complex a)

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

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

(ReflectsTI k q z, PID z, Enumerable (ZqBasic k q z)) => CRTrans (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.

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

CRTEmbed Int

CRTEmbed Int64

CRTEmbed Integer

Transcendental a => CRTEmbed (Complex a)

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

(ReflectsTI k q z, Ring (ZqBasic k q z)) => CRTEmbed (ZqBasic k q z)

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

Information that characterizes the (invertible) Chinese remainder transformation over a ring r, namely:

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

crtInfoFact :: (Fact m, CRTrans r) => TaggedT m Maybe (CRTInfo r)

crtInfo wrapper for Fact types.

crtInfoPPow :: (PPow pp, CRTrans r) => TaggedT pp Maybe (CRTInfo r)

crtInfo wrapper for PPow types.

crtInfoPrime :: (Prim p, CRTrans r) => TaggedT p Maybe (CRTInfo r)

crtInfo wrapper for Prime types.

gEmbPPow :: forall pp r. (PPow pp, CRTrans r) => TaggedT pp Maybe (Int -> r)

A function that returns the ith embedding of g_{p^e} = g_p for i in Z*_{p^e}.

gEmbPrime :: (Prim p, CRTrans r) => TaggedT p Maybe (Int -> r)

A function that returns the ith embedding of g_p for i in Z*_p, i.e., 1-omega_p^i.