🚀 go-pugleaf

In 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
 
Direct search. An upper bound on the number of exponentiations is
log_2(N). Each one takes O(log^3 N), so direct search takes only
O(log^4 N) operations. 

I.E.

Compute M = log_2(N). One then need only check whether it is a perfect
square, cube, 4th power.....  M'th power. Each of these tests is trivial.

--
Bob Silverman
These are my opinions and not MITRE's.
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"