home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / crypt / 7131 < prev    next >
Encoding:
Text File  |  1993-01-25  |  1.5 KB  |  35 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!cs.utexas.edu!zaphod.mps.ohio-state.edu!saimiri.primate.wisc.edu!ames!agate!linus!linus.mitre.org!fatima!bs
  3. From: bs@fatima.mitre.org (Robert D. Silverman)
  4. Subject: Re: Is N a prime power?
  5. Message-ID: <1993Jan25.150556.24096@linus.mitre.org>
  6. Sender: news@linus.mitre.org (News Service)
  7. Nntp-Posting-Host: fatima.mitre.org
  8. Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
  9. References: <C1Exs1.8uz@ms.uky.edu>
  10. Date: Mon, 25 Jan 1993 15:05:56 GMT
  11. Lines: 22
  12.  
  13. In article <C1Exs1.8uz@ms.uky.edu> jedwards@ms.uky.edu (Jonathan Edwards) writes:
  14. :I am reading an old paper by Tompa that describes Blum's protocol for
  15. :flipping coins by telephone.  The first thing the verifier must do is
  16. :verify that a very large (hundreds of digits) number has at least two
  17. :distinct prime factors (i.e., that the number is not a prime power).
  18. :Tompa gives no hint how to do this and I haven't been able to find anyone
  19. :else who knows.  I'd very much appreciate it if someone could explain
  20.  
  21. Direct search. An upper bound on the number of exponentiations is
  22. log_2(N). Each one takes O(log^3 N), so direct search takes only
  23. O(log^4 N) operations. 
  24.  
  25. I.E.
  26.  
  27. Compute M = log_2(N). One then need only check whether it is a perfect
  28. square, cube, 4th power.....  M'th power. Each of these tests is trivial.
  29.  
  30. --
  31. Bob Silverman
  32. These are my opinions and not MITRE's.
  33. Mitre Corporation, Bedford, MA 01730
  34. "You can lead a horse's ass to knowledge, but you can't make him think"
  35.