Data.Number.Flint.Groups.DLog

• - This module implements discrete logarithms, with the application to Dirichlet characters in mind.

In particular, this module defines a dlog_precomp_t structure permitting to describe a discrete log problem in some subgroup of ((mathbb Z/p^e mathbb Z)^times) for primepower moduli \(p^e\), and store precomputed data for faster computation of several such discrete logarithms.

When initializing this data, the user provides both a group description and the expected number of subsequent discrete logarithms calls. The choice of algorithm and the amount of stored data depend both on the structure of the group and this number.

No particular effort has been made towards single discrete logarithm computation. Currently only machine size primepower moduli are supported.

Discrete logarithms mod ulong primes

Single evaluation

dlog_once :: CULong -> CULong -> Ptr CNMod -> CULong -> IO CULong

dlog_once b a mod n

Return \(x\) such that \(b = a^x\) in \((\mathbb Z/mod \mathbb Z)^\times\), where a is known to have order n.

Precomputations

data DLogPrecomp

Constructors

DLogPrecomp !(ForeignPtr CDLogPrecomp)

Instances

Storable CDLogPrecomp

Defined in Data.Number.Flint.Groups.DLog.FFI

Methods

sizeOf :: CDLogPrecomp -> Int

alignment :: CDLogPrecomp -> Int

peekElemOff :: Ptr CDLogPrecomp -> Int -> IO CDLogPrecomp

pokeElemOff :: Ptr CDLogPrecomp -> Int -> CDLogPrecomp -> IO ()

peekByteOff :: Ptr b -> Int -> IO CDLogPrecomp

pokeByteOff :: Ptr b -> Int -> CDLogPrecomp -> IO ()

peek :: Ptr CDLogPrecomp -> IO CDLogPrecomp

poke :: Ptr CDLogPrecomp -> CDLogPrecomp -> IO ()

type CDLogPrecomp = CFlint DLogPrecomp

newDLogPrecompN :: CULong -> CULong -> CULong -> CULong -> IO DLogPrecomp

newDLogPrecompModpe :: CULong -> CULong -> CULong -> CULong -> CULong -> IO DLogPrecomp

newDLogPrecompP :: CULong -> CULong -> CULong -> CULong -> IO DLogPrecomp

newDLogPrecompPE :: CULong -> CULong -> CULong -> CULong -> CULong -> CULong -> IO DLogPrecomp

newDLogPrecompSmall :: CULong -> CULong -> CULong -> CULong -> IO DLogPrecomp

withDLogPrecomp :: DLogPrecomp -> (Ptr CDLogPrecomp -> IO a) -> IO (DLogPrecomp, a)

dlog_precomp_n_init :: Ptr CDLogPrecomp -> CULong -> CULong -> CULong -> CULong -> IO ()

dlog_precomp_n_init pre a mod n num

Precompute data for num discrete logarithms evaluations in the subgroup generated by a modulo mod, where a is known to have order n.

dlog_precomp :: Ptr CDLogPrecomp -> CULong -> IO CULong

dlog_precomp pre b

Return \(\log(b)\) for the group described in pre.

dlog_precomp_clear :: Ptr CDLogPrecomp -> IO ()

dlog_precomp_clear pre

Clears t.

dlog_precomp_modpe_init :: Ptr CDLogPrecomp -> CULong -> CULong -> CULong -> CULong -> CULong -> IO ()

dlog_precomp_modpe_init pre a p e pe num

Assume that a generates the group of residues modulo pe equal \(p^e\) for prime p.

dlog_precomp_p_init :: Ptr CDLogPrecomp -> CULong -> CULong -> CULong -> CULong -> IO ()

dlog_precomp_p_init pre a mod p num

Assume that a has prime order p.

dlog_precomp_pe_init :: Ptr CDLogPrecomp -> CULong -> CULong -> CULong -> CULong -> CULong -> CULong -> IO ()

dlog_precomp_pe_init pre a mod p e pe num

Assume that a has primepower order pe \(p^e\).

dlog_precomp_small_init :: Ptr CDLogPrecomp -> CULong -> CULong -> CULong -> CULong -> IO ()

dlog_precomp_small_init pre a mod n num

Make a complete lookup table of size n. If mod is small, this is done using an element-indexed array (see dlog_table_t), otherwise with a sorted array allowing binary search.

Vector evaluations

dlog_vec_fill :: Ptr CULong -> CULong -> CULong -> IO ()

dlog_vec_fill v nv x

Sets values v[k] to x for all k less than nv.

dlog_vec_set_not_found :: Ptr CULong -> CULong -> Ptr CNMod -> IO ()

dlog_vec_set_not_found v nv mod

Sets values v[k] to DLOG_NONE for all k not coprime to mod.

dlog_vec :: Ptr CULong -> CULong -> CULong -> CULong -> Ptr CNMod -> CULong -> Ptr CNMod -> IO ()

dlog_vec v nv a va mod na order

Sets v[k] to \(\log(k,a)\) times value va for \(0\leq k < nv\), where a has order na. va should be 1 for usual log computation.

dlog_vec_add :: Ptr CULong -> CULong -> CULong -> CULong -> Ptr CNMod -> CULong -> Ptr CNMod -> IO ()

dlog_vec_add v nv a va mod na order

Same parameters as before, but adds \(\log(k,a)\times v_a\) to v[k] and reduce modulo order instead of replacing the value. Indices k such that v[k] equals DLOG_NONE are ignored.

dlog_vec_loop :: Ptr CULong -> CULong -> CULong -> CULong -> Ptr CNMod -> CULong -> Ptr CNMod -> IO ()

dlog_vec_loop v nv a va mod na order

dlog_vec_loop_add :: Ptr CULong -> CULong -> CULong -> CULong -> Ptr CNMod -> CULong -> Ptr CNMod -> IO ()

dlog_vec_loop_add v nv a va mod na order

Perform a complete loop of size na on powers of a to fill the logarithm values, discarding powers outside the bounds of v. This requires no discrete logarithm computation.

dlog_vec_eratos :: Ptr CULong -> CULong -> CULong -> CULong -> Ptr CNMod -> CULong -> Ptr CNMod -> IO ()

dlog_vec_eratos v nv a va mod na order

dlog_vec_eratos_add :: Ptr CULong -> CULong -> CULong -> CULong -> Ptr CNMod -> CULong -> Ptr CNMod -> IO ()

dlog_vec_eratos_add v nv a va mod na order

Compute discrete logarithms of prime numbers less than nv and propagate to composite numbers.

dlog_vec_sieve_add :: Ptr CULong -> CULong -> CULong -> CULong -> Ptr CNMod -> CULong -> Ptr CNMod -> IO ()

dlog_vec_sieve_add v nv a va mod na order

dlog_vec_sieve :: Ptr CULong -> CULong -> CULong -> CULong -> Ptr CNMod -> CULong -> Ptr CNMod -> IO ()

dlog_vec_sieve v nv a va mod na order

Compute the discrete logarithms of the first few prime numbers, then use them as a factor base to obtain the logarithms of larger primes by sieving techniques.

In the the present implementation, the full index-calculus method is not implemented.