home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / crypt / 7185 < prev    next >
Encoding:
Text File  |  1993-01-28  |  1.6 KB  |  39 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!charon.amdahl.com!pacbell.com!decwrl!ames!agate!linus!linus.mitre.org!gauss!bs
  3. From: bs@gauss.mitre.org (Robert D. Silverman)
  4. Subject: Re: Is N a prime power?
  5. Message-ID: <1993Jan27.005730.29749@linus.mitre.org>
  6. Sender: news@linus.mitre.org (News Service)
  7. Nntp-Posting-Host: gauss.mitre.org
  8. Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
  9. References: <C1Exs1.8uz@ms.uky.edu> <1993Jan25.150556.24096@linus.mitre.org> <1k3qqpINNt0@gaia.ucs.orst.edu>
  10. Date: Wed, 27 Jan 1993 00:57:30 GMT
  11. Lines: 26
  12.  
  13. In article <1k3qqpINNt0@gaia.ucs.orst.edu> pmontgom@math.orst.edu (Peter Montgomery) writes:
  14. :In article <1993Jan25.150556.24096@linus.mitre.org> bs@fatima.mitre.org 
  15.  
  16. stuff deleted....
  17.  
  18. : >:verify that a very large (hundreds of digits) number has at least two
  19. : >:distinct prime factors (i.e., that the number is not a prime power).
  20. : >:Tompa gives no hint how to do this and I haven't been able to find anyone
  21. : >:else who knows.  I'd very much appreciate it if someone could explain
  22. : 
  23. : >Direct search. An upper bound on the number of exponentiations is
  24. : >log_2(N). Each one takes O(log^3 N), so direct search takes only
  25. : >O(log^4 N) operations. 
  26. :
  27. :    I suggest testing whether GCD(N, b^(N-1) - 1) > 1,
  28. :where b is selected randomly and GCD(N, b) = 1.  
  29. :If N = p^k, then p-1 divides p^k - 1 = N-1, 
  30. :so p divides both N and b^(N-1) - 1.  This takes time O(log^3 N).
  31. :
  32. Indeed. This is a variant of Cantor-Zassenhaus. [for polynomial roots
  33. mod p]. 
  34. --
  35. Bob Silverman
  36. These are my opinions and not MITRE's.
  37. Mitre Corporation, Bedford, MA 01730
  38. "You can lead a horse's ass to knowledge, but you can't make him think"
  39.