64-bit discrete logarithm

Hi everyone,

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
logarithms.

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
bits?

Thanks,

--
Fábio Dias Moreira
.

Relevant Pages

  • Re: MATLAB Programming Contest: May 9 - May 16, 20
    ... The Mathworks runs these contests to engage and excite the MATLAB ... I hope the organizers will stick with the current contest format. ... for their own algorithmic insights, ... both incremental and the main algorithm remains the same. ...
    (comp.soft-sys.matlab)
  • thoughts on Matlab Contest
    ... Congratulations to the organizers for another great Matlab contest! ... add a "captcha" to the entry submission form. ... and encouraged most people to think more about algorithm development ...
    (comp.soft-sys.matlab)
  • Re: now that was interesting
    ... algorithm development. ... so it would be very difficult for the Contest Team ... I think obfuscation is part of the contest, ...
    (comp.soft-sys.matlab)
  • Re: $50,000 DSP Contest- data glitch fixed!
    ... check out our contest seeking an algorithm for signal analysis data set. ... materials. ... FIND Technologies Inc. has recorded which data sets belong to ...
    (comp.dsp)
  • Re: MATLAB Programming Contest: May 9 - May 16, 20
    ... Congratulations to the organizers for another great Matlab contest! ... add a "captcha" to the entry submission form. ... and encouraged most people to think more about algorithm development ...
    (comp.soft-sys.matlab)