lol-0.2.0.0: A library for lattice cryptography.

Safe HaskellNone
LanguageHaskell2010

Crypto.Lol.CRTrans

Description

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

Synopsis

Documentation

class Ring r => CRTrans r where Source

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) Source

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

class (Ring r, Ring (CRTExt r)) => CRTEmbed r where Source

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 Source

Methods

toExt :: r -> CRTExt r Source

Embeds from r to CRTExt r

fromExt :: CRTExt r -> r Source

Projects from CRTExt r to r

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

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) Source

crtInfo wrapper for Fact types.

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

crtInfo wrapper for PPow types.

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

crtInfo wrapper for Prime types.

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

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) Source

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