home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / crypt / 7149 < prev    next >
Encoding:
Internet Message Format  |  1993-01-25  |  1.6 KB
  1. Path: sparky!uunet!spool.mu.edu!yale.edu!ira.uka.de!smurf.sub.org!news
  2. From: urlichs@smurf.sub.org (Matthias Urlichs)
  3. Newsgroups: sci.crypt
  4. Subject: Re: Is N a prime power?
  5. Date: 26 Jan 1993 02:24:09 +0100
  6. Organization: University of Karlsruhe, FRG
  7. Lines: 30
  8. Message-ID: <1k23rp$392@smurf.sub.org>
  9. References: <C1Exs1.8uz@ms.uky.edu>
  10. NNTP-Posting-Host: 127.0.0.1
  11.  
  12. In sci.crypt, article <C1Exs1.8uz@ms.uky.edu>,
  13.   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. > how it's done or point me to a paper somewhere...
  21.  
  22. This is probably a very stupid algorithm, but..:
  23.  
  24. isprimeroot(x) ::=
  25.  
  26. if(x prime) return TRUE;
  27. for all n >= 2, n prime:
  28.    y = x ^ (1/n)
  29.    if (y integer) { if (y prime) return TRUE, else return FALSE }
  30.    if (y < 2) return FALSE.
  31.  
  32. How to calculate n'th roots is left as an exercise to the reader.
  33.  
  34. Warning: The above is off the top of my head, so it may or may not be correct.
  35.  
  36. -- 
  37. A spilled drink flows in the direction of the most expensive object.
  38.                                        -- "The New Official Rules"
  39. -- 
  40. Matthias Urlichs  --  urlichs@smurf.sub.org -- urlichs@smurf.ira.uka.de   /(o\
  41. Humboldtstrasse 7 -- 7500 Karlsruhe 1 -- Germany  --  +49-721-9612521     \o)/
  42.