home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / sci / math / 17553 < prev    next >
Encoding:
Text File  |  1992-12-31  |  1.5 KB  |  44 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!timbuk.cray.com!walter.cray.com!ferrari!slow
  3. From: slow@ferrari.cray.com (David Slowinski)
  4. Subject: checking modular arithmetic
  5. Message-ID: <1992Dec31.134329.21227@walter.cray.com>
  6. Lines: 32
  7. Nntp-Posting-Host: ferrari.cray.com
  8. Reply-To: slow@ferrari.cray.com (David Slowinski)
  9. Organization: Cray Research, Inc.  Eagan, MN.
  10. Date: 31 Dec 92 13:43:29 CST
  11.  
  12. Background:
  13.   For my Mersenne Prime search I use the Lucas-Lehmer test to test
  14. the primality of 2^p-1:
  15. 1)    u = 4
  16. 2)    for i = 3 to p
  17. 3)      u = u^2 mod 2^p-1 - 2
  18. 4)    next i 
  19. 5)    if u == 0 then 2^p-1 is prime
  20.  
  21.   Nearly all of the computer time is spent computing u^2 in line 3.
  22. My current program uses a Schonhage-Strassen multiply based on
  23. a mixed-radix FFT microtasked to run in parallel on multi-cpu
  24. shared memory machines.  Since I often make programming errors and
  25. run on experimental hardware, I use a residue check to verify the
  26. correctness of each 2p bit long multiply.
  27.   Barry Fagin and Richard Crandall have developed a clever algorithm
  28. that directly computes the 'u^2 mod 2^p-1' using FFT's on only p bits.
  29. This algorithm is over twice as fast as the 2p bit FFT multiply that 
  30. I use now.  I would like to use this faster algorithm in my new
  31. mpp based program, but I am afraid to without a check on each 
  32. result to give me confidence.
  33.   
  34. Question:
  35.   Is there a way to check the correctness of the result of 
  36. 'u^2 mod 2^p-1' where p is prime in the range 500,000 - 1,000,000?
  37.   
  38. Thank you kindly,
  39.  
  40. David Slowinski
  41. slow@cray.com
  42. Cray Research Inc
  43. Chippewa Falls, Wisconsin 
  44.