Crypto.Lol.Prelude

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 and families

class Enumerable a where

Poor man's Enum.

Methods

values :: [a]

Instances

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

(Reflects k q z, ToInteger 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)

Product ring of Zqs as a Zq (with Integer modulus)

(Reflects k q z, ToInteger z) => Mod (ZqBasic k q z)

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

Represents that a is a subgroup of b.

Methods

fromSubgroup :: a -> b

Instances

(ToInteger i, RealField r, Reflects k q i, Reflects k q r) => Subgroup (ZqBasic k q i) (RRq k q r)

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)

Reduce into product ring.

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

(Reflects k q z, ToInteger z) => Reduce z (ZqBasic k q z)

(Reflects k q r, RealField r, Additive (RRq k q r)) => Reduce r (RRq k q r)

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

(Reduce a b, Tensor t, Fact m, TElt t a, TElt t b) => Reduce (UCyc t m D a) (UCyc t m D b)

(Reduce a b, Tensor t, Fact m, TElt t a, TElt t b) => Reduce (UCyc t m P a) (UCyc t m P 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 family LiftOf b

The type of representatives of b.

Instances

type LiftOf (a, b) = Integer

type LiftOf (ZqBasic k q z) = z

type LiftOf (RRq k q r) = r

type LiftOf (Cyc t m r) = Cyc t m (LiftOf r)

type LiftOf (UCyc t m D r) = UCyc t m D (LiftOf r)

type LiftOf (UCyc t m P r) = UCyc t m P (LiftOf r)

type LiftOf (Linear t zp e r s) = Linear t (LiftOf zp) 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.

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)

Lift product ring of Zqs to Integer

(Reflects k q z, ToInteger z) => Lift' (ZqBasic k q z)

(Reflects k q r, Reduce r (RRq k q r), Ord r, Ring r) => Lift' (RRq k q r)

(Lift' r, Tensor t, Fact m, TElt t r, TElt t (LiftOf r)) => Lift' (UCyc t m D r)

(Lift' r, Tensor t, Fact m, TElt t r, TElt t (LiftOf r)) => Lift' (UCyc t m P r)

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

lifts with respect to powerful basis, for best geometry

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)

Rescale up to a product ring of Zqs

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

Rescale up to a product ring of Zqs

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

Rescale a (multi-)product ring of Zqs

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

Rescale a (multi-)product ring of Zqs

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

Rescale a product ring of Zqs

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

Rescale a product ring of Zqs

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

(Rescale a b, Tensor t, Fact m, TElt t a, TElt t b) => Rescale (UCyc t m D a) (UCyc t m D b)

(Rescale a b, Tensor t, Fact m, TElt t a, TElt t b) => Rescale (UCyc t m P a) (UCyc t m P b)

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)

Encode for a product ring

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

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

Inverted entries of lsdToMSD.

type family CharOf fp :: k

The characteristic of a ring, represented as a type.

Instances

type CharOf k (ZqBasic k p z) = p

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.

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

Arguments

:: (IntegralDomain i, Ord i)

=> i

dividend a

-> i

divisor b

-> (i, i)

(quotient, remainder)

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

CRandom Int64

CRandomR Int64

C Int64

C Int64

C Int64

C Int64

C Int64

C Int64

C Int64

C Int64

C Int64

C Int64

Prim Int64

GPB Int64

Wire Int64

TextType Int64

Mergeable Int64

Default Int64

Elt Int64

Unbox Int64

Lift Int64

CRTEmbed Int64

Embeds into complex numbers

Vector Vector Int64

MVector MVector Int64

CRTrans Maybe Int64

Returns Nothing

MessageAPI msg (msg -> Int64) Int64

(Fact m, Reflects k q Int64) => Protoable (CT m (ZqBasic k q Int64))

(Fact m, Reflects k q Int64) => Protoable (RT m (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)

type ProtoType (CT m (ZqBasic k q Int64)) = Rq

type ProtoType (RT m (ZqBasic k q Int64)) = Rq

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)

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

Complex numbers have CRTrans for any index m

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)

Custom instance replacing the one provided by numeric prelude: it always returns 0 as the remainder of a division. (The NP instance sometimes has precision issues, because it yields nonzero remainders, which is a problem for divG methods.)

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)

Self-embed

data MVector s (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 => Tagged t 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. (SingI n => TaggedT n mon r) -> Sing n -> mon r

Transformer version of withWitness.

module Data.Functor.Trans.Tagged

module Data.Proxy