64-bit discrete logarithm
- From: ctgPi <fabio@xxxxxxxxxxxxxxxxxxx>
- Date: Mon, 17 Jan 2011 07:30:22 -0800 (PST)
I'm writing a number theory reference sheet for programming contest
competitors; I'm building a rough outline right now of topics I will
mention. Two of them are integer factorization and discrete
Fortunately, in most programming competitions big integer arithmetic
isn't required; most integers are bounded to 64 bits. So I plan to
write about Pollard's rho for integer factorization — in this case,
O(n^1/4) ~ 2^16, which is small enough to factorize any 64-bit integer
in a fraction of a second. I was a bit dismayed to find out both of
Pollard's algorithms for discrete logarithms are, however, O(n^1/2).
This is a problem if the modulus is a 64-bit safe prime, since the
algorithm runtime will be on the order of 2^32, which takes a few
seconds. I'm looking for another discrete log algorithm that is:
1) fast — subsecond performance on a modern x86 for 64-bit moduli.
Probably O(n^1/4) or O(n^1/3) would be good enough here; O(n^1/4) or
O(n^1/3) memory is also fine.
2) simple — has a short C/C++ implementation on Linux/gcc for x86.
Contestants CAN use written notes but must actually type in the code
during the contest, so shorter code allows for less errors and
consumes less contest time. *Conceptual* simplicity is nice to have,
but not a real requirement. I'm thinking 100 lines or less here,
without counting supporting functions like modular multiplication/
exponentiation and gcd.
Is there any algorithm that might satisfy both constraints? Or is the
discrete log problem intrinsically harder than factorization at 64
Fábio Dias Moreira
- Prev by Date: differential cryptanalysis
- Next by Date: Re: differential cryptanalysis
- Previous by thread: differential cryptanalysis
- Next by thread: Re: 64-bit discrete logarithm