| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Data.Number.Flint.Groups.DLog
Description
- - 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.
Synopsis
- dlog_once :: CULong -> CULong -> Ptr CNMod -> CULong -> IO CULong
- data DLogPrecomp = DLogPrecomp !(ForeignPtr CDLogPrecomp)
- 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 :: Ptr CDLogPrecomp -> CULong -> IO CULong
- dlog_precomp_clear :: Ptr CDLogPrecomp -> IO ()
- dlog_precomp_modpe_init :: Ptr CDLogPrecomp -> CULong -> CULong -> CULong -> CULong -> CULong -> IO ()
- dlog_precomp_p_init :: Ptr CDLogPrecomp -> CULong -> CULong -> CULong -> CULong -> IO ()
- dlog_precomp_pe_init :: Ptr CDLogPrecomp -> CULong -> CULong -> CULong -> CULong -> CULong -> CULong -> IO ()
- dlog_precomp_small_init :: Ptr CDLogPrecomp -> CULong -> CULong -> CULong -> CULong -> IO ()
- dlog_vec_fill :: Ptr CULong -> CULong -> CULong -> IO ()
- dlog_vec_set_not_found :: Ptr CULong -> CULong -> Ptr CNMod -> IO ()
- dlog_vec :: Ptr CULong -> CULong -> CULong -> CULong -> Ptr CNMod -> CULong -> Ptr CNMod -> IO ()
- dlog_vec_add :: Ptr CULong -> CULong -> CULong -> CULong -> Ptr CNMod -> CULong -> Ptr CNMod -> IO ()
- dlog_vec_loop :: Ptr CULong -> CULong -> CULong -> CULong -> Ptr CNMod -> CULong -> Ptr CNMod -> IO ()
- dlog_vec_loop_add :: Ptr CULong -> CULong -> CULong -> CULong -> Ptr CNMod -> CULong -> Ptr CNMod -> IO ()
- dlog_vec_eratos :: Ptr CULong -> CULong -> CULong -> CULong -> Ptr CNMod -> CULong -> Ptr CNMod -> IO ()
- dlog_vec_eratos_add :: Ptr CULong -> CULong -> CULong -> CULong -> Ptr CNMod -> CULong -> Ptr CNMod -> IO ()
- dlog_vec_sieve_add :: Ptr CULong -> CULong -> CULong -> CULong -> Ptr CNMod -> CULong -> Ptr CNMod -> IO ()
- dlog_vec_sieve :: Ptr CULong -> CULong -> CULong -> CULong -> Ptr CNMod -> CULong -> Ptr CNMod -> IO ()
Discrete logarithms mod ulong primes
Single evaluation
dlog_once :: CULong -> CULong -> Ptr CNMod -> CULong -> IO CULong Source #
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 Source #
Constructors
| DLogPrecomp !(ForeignPtr CDLogPrecomp) |
Instances
| Storable CDLogPrecomp Source # | |
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 Source #
newDLogPrecompN :: CULong -> CULong -> CULong -> CULong -> IO DLogPrecomp Source #
newDLogPrecompModpe :: CULong -> CULong -> CULong -> CULong -> CULong -> IO DLogPrecomp Source #
newDLogPrecompP :: CULong -> CULong -> CULong -> CULong -> IO DLogPrecomp Source #
newDLogPrecompPE :: CULong -> CULong -> CULong -> CULong -> CULong -> CULong -> IO DLogPrecomp Source #
newDLogPrecompSmall :: CULong -> CULong -> CULong -> CULong -> IO DLogPrecomp Source #
withDLogPrecomp :: DLogPrecomp -> (Ptr CDLogPrecomp -> IO a) -> IO (DLogPrecomp, a) Source #
dlog_precomp_n_init :: Ptr CDLogPrecomp -> CULong -> CULong -> CULong -> CULong -> IO () Source #
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 Source #
dlog_precomp pre b
Return \(\log(b)\) for the group described in pre.
dlog_precomp_clear :: Ptr CDLogPrecomp -> IO () Source #
dlog_precomp_clear pre
Clears t.
dlog_precomp_modpe_init :: Ptr CDLogPrecomp -> CULong -> CULong -> CULong -> CULong -> CULong -> IO () Source #
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 () Source #
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 () Source #
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 () Source #
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 () Source #
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 () Source #
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 () Source #
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 () Source #
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 () Source #
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 () Source #
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 () Source #
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 () Source #
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 () Source #
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 () Source #
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.