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 deg => CRTrans (GF k fp deg)

(Reflects k q z, PID z, (~) * r (ZqBasic k q z), Mod r, Enumerable r, Show 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 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.

crtInfoNatC :: (NatC p, CRTrans r) => TaggedT p Maybe (CRTInfo r)

crtInfo wrapper for NatC 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}.

gEmbNatC :: (NatC 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.

omegaPowMod :: forall r. (Mod r, Enumerable r, Ring r, Eq r) => Int -> Maybe (Int -> r)

Default implementation of omegaPow for Mod types. The implementation finds an integer element of maximal multiplicative order, and raises it to the appropriate power. Therefore, the functions returned for different values of the first argument are consistent, i.e., omega_{m'}^(m'/m) = omega_m.

zqHasCRT :: (ToInteger i, PID i) => i -> i -> Bool

zqHasCRT m q says whether Z_q has an invertible CRT transform of index m, i.e., Z_q has an element of multiplicative order m, and mhat is invertible in Z_q.