home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / crypt / 7157 < prev    next >
Encoding:
Internet Message Format  |  1993-01-27  |  1.8 KB
  1. Path: sparky!uunet!sequent!gaia.ucs.orst.edu!pmontgom
  2. From: pmontgom@math.orst.edu (Peter Montgomery)
  3. Newsgroups: sci.crypt
  4. Subject: Re: Is N a prime power?
  5. Date: 26 Jan 1993 17:02:17 GMT
  6. Organization: Oregon State University Math Department
  7. Lines: 29
  8. Message-ID: <1k3qqpINNt0@gaia.ucs.orst.edu>
  9. References: <C1Exs1.8uz@ms.uky.edu> <1993Jan25.150556.24096@linus.mitre.org>
  10. NNTP-Posting-Host: lab12.math.orst.edu
  11.  
  12. In article <1993Jan25.150556.24096@linus.mitre.org> bs@fatima.mitre.org 
  13. (Robert D. Silverman) writes:
  14.  >In article <C1Exs1.8uz@ms.uky.edu> jedwards@ms.uky.edu (Jonathan Edwards) writes:
  15.  >:I am reading an old paper by Tompa that describes Blum's protocol for
  16.  >:flipping coins by telephone.  The first thing the verifier must do is
  17.  >:verify that a very large (hundreds of digits) number has at least two
  18.  >:distinct prime factors (i.e., that the number is not a prime power).
  19.  >:Tompa gives no hint how to do this and I haven't been able to find anyone
  20.  >:else who knows.  I'd very much appreciate it if someone could explain
  21.  
  22.  >Direct search. An upper bound on the number of exponentiations is
  23.  >log_2(N). Each one takes O(log^3 N), so direct search takes only
  24.  >O(log^4 N) operations. 
  25.  
  26.     I suggest testing whether GCD(N, b^(N-1) - 1) > 1,
  27. where b is selected randomly and GCD(N, b) = 1.  
  28. If N = p^k, then p-1 divides p^k - 1 = N-1, 
  29. so p divides both N and b^(N-1) - 1.  This takes time O(log^3 N).
  30.  
  31.     It is possible for this test to get a nontrivial GCD when
  32. N is not a prime power, but such N should likely be rejected
  33. for other reasons.
  34.  
  35.  
  36. -- 
  37.         Peter L. Montgomery              Internet: pmontgom@math.orst.edu
  38.         Dept. of Mathematics, Oregon State Univ, Corvallis, OR 97331-4605 USA
  39. My visiting professorship ends in June.  Interested in program optimization,
  40. compilers, computer arithmetic, number theory.  17 yrs industrial experience.
  41.