🚀 go-pugleaf

In sci.crypt, article <C1Exs1.8uz@ms.uky.edu>,
  jedwards@ms.uky.edu (Jonathan Edwards) writes:
> I am reading an old paper by Tompa that describes Blum's protocol for
> flipping coins by telephone.  The first thing the verifier must do is
> verify that a very large (hundreds of digits) number has at least two
> distinct prime factors (i.e., that the number is not a prime power).
> Tompa gives no hint how to do this and I haven't been able to find anyone
> else who knows.  I'd very much appreciate it if someone could explain
> how it's done or point me to a paper somewhere...

This is probably a very stupid algorithm, but..:

isprimeroot(x) ::=

if(x prime) return TRUE;
for all n >= 2, n prime:
   y = x ^ (1/n)
   if (y integer) { if (y prime) return TRUE, else return FALSE }
   if (y < 2) return FALSE.

How to calculate n'th roots is left as an exercise to the reader.

Warning: The above is off the top of my head, so it may or may not be correct.

-- 
A spilled drink flows in the direction of the most expensive object.
                                       -- "The New Official Rules"
-- 
Matthias Urlichs  --  urlichs@smurf.sub.org -- urlichs@smurf.ira.uka.de   /(o\
Humboldtstrasse 7 -- 7500 Karlsruhe 1 -- Germany  --  +49-721-9612521     \o)/