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, omega' are respectively the roots of unity used for m, m' where m divides m', then it should be the case that omega'^(m'/m)=omega.

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

CRTrans Maybe Int

Returns Nothing

CRTrans Maybe Int64

Returns Nothing

CRTrans Maybe Integer

Returns Nothing

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

Complex numbers have CRTrans for any index m

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

Product ring

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

(Reflects k q z, ToInteger z, PID z, Enumerable (ZqBasic k q z)) => CRTrans Maybe (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

Embeds into complex numbers

CRTEmbed Int

Embeds into complex numbers

CRTEmbed Int64

Embeds into complex numbers

CRTEmbed Integer

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

Transcendental a => CRTEmbed (Complex a)

Self-embed

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

Product ring

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

Embeds into complex numbers

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.