Crypto.Lol.LatticePrelude

A substitute for the Prelude that is more suitable for Lol. This module exports most of the Numeric Prelude and other frequently used modules, plus some low-level classes, missing instances, and assorted utility functions.

Classes

class Enumerable a where

Poor man's Enum.

Methods

values :: [a]

Instances

GFCtx k fp deg => Enumerable (GF k fp deg)

(ReflectsTI k q z, Enum z) => Enumerable (ZqBasic k q z)

class (ToInteger (ModRep a), Additive a) => Mod a where

Represents a quotient group modulo some integer.

Associated Types

type ModRep a

Methods

modulus :: Tagged a (ModRep a)

Instances

(Mod a, Mod b) => Mod (a, b)

ReflectsTI k q z => Mod (ZqBasic k q z)

class (Additive a, Additive b) => Reduce a b where

Represents that b is a quotient group of a.

Methods

reduce :: a -> b

Instances

(Reduce a b1, Reduce a b2) => Reduce a (b1, b2)

(Reflects k q z, Ring (ZqBasic k q z)) => Reduce Integer (ZqBasic k q z)

ReflectsTI k q z => Reduce z (ZqBasic k q z)

(Reduce a b, Fact m, CElt t a, CElt t b) => Reduce (UCyc t m a) (UCyc t m b)

(Reduce a b, Fact m, CElt t a, CElt t b) => Reduce (Cyc t m a) (Cyc t m b)

(Reduce z zq, Fact s, CElt t z, CElt t zq) => Reduce (Linear t z e r s) (Linear t zq e r s)

type Lift b a = (Lift' b, LiftOf b ~ a)

Represents that b can be lifted to a "short" a congruent to b.

class Reduce (LiftOf b) b => Lift' b where

Fun-dep version of Lift.

Associated Types

type LiftOf b

Methods

lift :: b -> LiftOf b

Instances

(Mod a, Mod b, Lift' a, Lift' b, Reduce Integer (a, b), ToInteger (LiftOf a), ToInteger (LiftOf b)) => Lift' (a, b)

ReflectsTI k q z => Lift' (ZqBasic k q z)

(CElt t zp, CElt t z, (~) * z (LiftOf zp), Lift zp z, Fact s) => Lift' (Linear t zp e r s)

class (Additive a, Additive b) => Rescale a b where

Represents that a can be rescaled to b, as an "approximate" additive homomorphism.

Methods

rescale :: a -> b

Instances

(Ring b, Mod a, Reduce (ModRep a) b) => Rescale b (a, b)

(Ring a, Mod b, Reduce (ModRep b) a) => Rescale a (a, b)

(Rescale ((a, b), c) (a, b), Rescale (a, b) a) => Rescale ((a, b), c) a

(Rescale (a, (b, c)) (b, c), Rescale (b, c) c) => Rescale (a, (b, c)) c

(Mod b, Field a, Lift b (ModRep b), Reduce (LiftOf b) a) => Rescale (a, b) a

(Mod a, Field b, Lift a (ModRep a), Reduce (LiftOf a) b) => Rescale (a, b) b

(ReflectsTI k q z, ReflectsTI k1 q' z, Ring z) => Rescale (ZqBasic k q z) (ZqBasic k q' z)

class (Field src, Field tgt) => Encode src tgt where

Represents that the target ring can "noisily encode" values from the source ring, in either "most significant digit" (MSD) or "least significant digit" (LSD) encodings, and provides conversion factors between the two types of encodings.

Methods

lsdToMSD :: (src, tgt)

The factor that converts an element from LSD to MSD encoding in the target field, with associated scale factor to apply to correct the resulting encoded value.

Instances

(Encode s t1, Encode s t2, Field (t1, t2)) => Encode s (t1, t2)

(Reflects k p z, ReflectsTI k1 q z, Field (ZqBasic k p z), Field (ZqBasic k1 q z)) => Encode (ZqBasic k p z) (ZqBasic k q z)

msdToLSD :: Encode src tgt => (src, tgt)

Inverted entries of lsdToMSD.

Numeric

max :: Ord a => a -> a -> a

The Prelude definition of max.

min :: Ord a => a -> a -> a

The Prelude definition of min.

abs :: Absolute a => a -> a

The sane definition of abs from Numeric rather than the default from NumericPrelude.

realToField :: (Field b, ToRational a) => a -> b

The hidden NP function from ToRational.

type ZeroTestable a = C a

Sane synonym for C.

type Additive a = C a

Sane synonym for C.

type Ring a = C a

Sane synonym for C.

type Module a v = C a v

Sane synonym for C.

type IntegralDomain a = C a

Sane synonym for C.

type ToRational a = C a

Sane synonym for C.

type Field a = C a

Sane synonym for C.

type RealRing a = C a

Sane synonym for C.

type RealField a = C a

Sane synonym for C.

type Algebraic a = C a

Sane synonym for C.

type Transcendental a = C a

Sane synonym for C.

type RealTranscendental a = C a

Sane synonym for C.

type OrdFloat a = (Ord a, Transcendental a)

Convenient synonym for (Ord a, Transcendental a)

type ToInteger a = C a

Sane synonym for C.

type Absolute a = C a

Sane synonym for C.

type RealIntegral a = C a

Sane synonym for C.

type PID a = C a

Sane synonym for C.

type Polynomial a = T a

Sane synonym for T.

(^) :: forall a i. (Ring a, ToInteger i) => a -> i -> a

Our custom exponentiation, overriding NP's version that requires Integer exponent. Copied from http://hackage.haskell.org/package/base-4.7.0.0/docs/src/GHC-Real.html#%5E

modinv :: (PID i, Eq i) => i -> i -> Maybe i

Inverse of a modulo q, in range 0..q-1. (Argument order is infix-friendly.)

decomp :: (IntegralDomain z, Ord z) => [z] -> z -> [z]

Decompose an element into a list of "centered" digits with respect to relative radices.

logCeil :: ToInteger i => i -> i -> Int

Yield ceil (log_b(x)).

roundMult :: (RealField r, ToInteger i) => i -> r -> i

Deterministically round to the nearest multiple of i.

roundScalarCentered :: (RealField r, Random r, ToInteger i, MonadRandom mon) => i -> r -> mon i

Randomly round to the nearest larger or smaller multiple of i, where the round-off term has expectation zero.

divModCent :: (IntegralDomain i, Ord i) => i -> i -> (i, i)

Variant of divMod in which the remainder is in the range [-b/2,b/2).

module NumericPrelude

data Int64 :: *

64-bit signed integer type

Instances

Bounded Int64

Enum Int64

Eq Int64

Integral Int64

Data Int64

Num Int64

Ord Int64

Read Int64

Real Int64

Show Int64

Ix Int64

Random Int64

Arbitrary Int64

CoArbitrary Int64

Storable Int64

Bits Int64

FiniteBits Int64

NFData Int64

Hashable Int64

C Int64

C Int64

C Int64

C Int64

C Int64

C Int64

C Int64

C Int64

C Int64

C Int64

Prim Int64

Elt Int64

Unbox Int64

Lift Int64

CRTEmbed Int64

CRTrans Int64

Dispatch Int64

CRNS Int64

Vector Vector Int64

MVector MVector Int64

Reflects k q Int64 => Dispatch (ZqBasic k q Int64)

data Vector Int64 = V_Int64 (Vector Int64)

type CRTExt Int64 = Complex Double

data MVector s Int64 = MV_Int64 (MVector s Int64)

Complex

data Complex a

Newtype wrapper (with slightly different instances) for numeric-prelude Complex.

Instances

Unbox a0 => Vector Vector (Complex a)

Unbox a0 => MVector MVector (Complex a)

Eq a => Eq (Complex a)

Show a => Show (Complex a)

Random a => Random (Complex a)

Arbitrary a => Arbitrary (Complex a)

Storable a => Storable (Complex a)

NFData a => NFData (Complex a)

C a => C (Complex a)

Field a => C (Complex a)

C a => C (Complex a)

C a => C (Complex a)

C a => C (Complex a)

Elt a => Elt (Complex a)

Unbox a0 => Unbox (Complex a)

Transcendental a => CRTEmbed (Complex a)

Transcendental a => CRTrans (Complex a)

Dispatch (Complex Double)

(TElt CT (Complex a), Dispatch (Complex a)) => CRNS (Complex a)

data MVector s0 (Complex a0) = MV_Complex (MVector s (a, a))

data Vector (Complex a0) = V_Complex (Vector (a, a))

type CRTExt (Complex a) = Complex a

roundComplex :: (RealRing a, ToInteger b) => Complex a -> (b, b)

Rounds the real and imaginary components to the nearest integer.

cis :: Transcendental a => a -> Complex a

cis t is a complex value with magnitude 1 and phase t (modulo 2*Pi).

real :: Complex a -> a

Real component of a complex number.

imag :: Complex a -> a

Imaginary component of a complex number.

fromReal :: Additive a => a -> Complex a

Embeds a scalar as the real component of a complex number.

Factored

module Crypto.Lol.Factored

Miscellaneous

rescaleMod :: forall a b. (Mod a, Mod b, ModRep a ~ ModRep b, Lift a (ModRep b), Ring b) => a -> b

A default implementation of rescaling for Mod types.

roundCoset :: forall zp z r. (Mod zp, z ~ ModRep zp, Lift zp z, RealField r) => zp -> r -> z

Deterministically round to a nearby value in the desired coset

fromJust' :: String -> Maybe a -> a

Version of fromJust with an error message.

pureT :: Applicative f => TaggedT t Identity a -> TaggedT t f a

Apply any applicative to a Tagged value.

peelT :: Tagged t (f a) -> TaggedT t f a

Expose the monad of a tagged value.

pasteT :: TaggedT t f a -> Tagged t (f a)

Hide the monad of a tagged value.

withWitness :: forall n r. (SingI n => Tagged n r) -> Sing n -> r

Use a singleton as a witness to extract a value from a tagged value.

withWitnessT :: forall n mon r. Monad mon => (SingI n => TaggedT n mon r) -> Sing n -> mon r

Monadic version of withWitness.

module Data.Functor.Trans.Tagged

module Data.Proxy