View Single Post 2008-02-08, 15:06   #4
R.D. Silverman

Nov 2003

22·5·373 Posts Quote:
 Originally Posted by drido Hi, unfortunately, after all this time, I didn't solve my problem yet: implementing in C the Index Calculus method for computing discrete logarithms. On the web I didn't find anything different by the proposed version of Studholm but it's too diffilcult to me. Does anyone knows a simple implementation of this method? In particular I'm in trouble to code the linear algebra step of the algorithm: how employ Hensel-type methods for matrix algebra modulo prime powers and chinese remainder methods for gluing powers of different primes. Any suggestions or link to other resources? Thank you for your reply jasonp!
I am not familiar with the method of Studholm, but you do have the
mathod used by Kevin McCurley etal. in their efforts.
If N is the modulus, factor it. Solve the system mod p for each prime p
dividing N. You can do this either by the Lanczos or Weidemann method.
[or even by Gaussian elim if the matrix is small enough]. Then for primes
p that divide N to a higher power than 1, raise the solution to p^k via
Hensel's Lemma. [Hensel's lemma says that if A is a solution to f(x) = 0 mod p^k , then a solution mod p^(k+1) will be of the form A + hp for some h.]

Now paste everything together by the CRT. For an effective implementation of the CRT, see my joint paper with Peter:

P. Montgomery & R. Silverman An FFT Extension to the P-1 Factoring
Algorithm, in Math.Comp.  