lol-0.4.0.0: A library for lattice cryptography.

Crypto.Lol.CRTrans

Description

$$\def\C{\mathbb{C}}$$

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

Synopsis

# Documentation

class (Monad mon, Ring r) => CRTrans mon 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_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) 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.

Instances

 Source # Returns Nothing Methods Source # Returns Nothing Methods Source # Returns Nothing Methods Source # Returns Nothing Methods (Monad mon, Transcendental a) => CRTrans mon (Complex a) Source # Complex numbers have CRTrans for any index $$m$$ MethodscrtInfo :: Reflects k m Int => TaggedT k * m mon (CRTInfo (Complex a)) Source # (CRTrans mon a, CRTrans mon b) => CRTrans mon (a, b) Source # Product ring MethodscrtInfo :: Reflects k m Int => TaggedT k * m mon (CRTInfo (a, b)) Source # GFCtx k fp d => CRTrans Maybe (GF k fp d) Source # MethodscrtInfo :: Reflects k m Int => TaggedT k * m Maybe (CRTInfo (GF k fp d)) Source # (Reflects k q z, ToInteger z, PID z, Enumerable (ZqBasic k q z)) => CRTrans Maybe (ZqBasic k q z) Source # MethodscrtInfo :: Reflects k m Int => TaggedT k * m Maybe (CRTInfo (ZqBasic k q z)) Source #

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$$.

Minimal complete definition

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

Instances

 Source # Embeds into the complex numbers $$\C$$. Associated Typestype CRTExt Double :: * Source # Methods Source # Embeds into the complex numbers $$\C$$. Associated Typestype CRTExt Int :: * Source # Methods Source # Embeds into the complex numbers $$\C$$. Associated Typestype CRTExt Int64 :: * Source # Methods Source # Embeds into the complex numbers $$\C$$. (May not have sufficient precision.) Associated Typestype CRTExt Integer :: * Source # Methods Source # Self-embed Associated Typestype CRTExt (Complex a) :: * Source # MethodstoExt :: Complex a -> CRTExt (Complex a) Source #fromExt :: CRTExt (Complex a) -> Complex a Source # (CRTEmbed a, CRTEmbed b) => CRTEmbed (a, b) Source # Product ring Associated Typestype CRTExt (a, b) :: * Source # MethodstoExt :: (a, b) -> CRTExt (a, b) Source #fromExt :: CRTExt (a, b) -> (a, b) Source # (Reflects k q z, ToInteger z, Ring (ZqBasic k q z)) => CRTEmbed (ZqBasic k q z) Source # Embeds into the complex numbers $$\C$$. Associated Typestype CRTExt (ZqBasic k q z) :: * Source # MethodstoExt :: ZqBasic k q z -> CRTExt (ZqBasic k q z) Source #fromExt :: CRTExt (ZqBasic k q z) -> ZqBasic k q z Source #

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

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$$.