🚀 go-pugleaf

In article <1993Jan25.150556.24096@linus.mitre.org> bs@fatima.mitre.org 
(Robert D. Silverman) writes:
 >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 suggest testing whether GCD(N, b^(N-1) - 1) > 1,
where b is selected randomly and GCD(N, b) = 1.  
If N = p^k, then p-1 divides p^k - 1 = N-1, 
so p divides both N and b^(N-1) - 1.  This takes time O(log^3 N).

	It is possible for this test to get a nontrivial GCD when
N is not a prime power, but such N should likely be rejected
for other reasons.


-- 
        Peter L. Montgomery              Internet: pmontgom@math.orst.edu
        Dept. of Mathematics, Oregon State Univ, Corvallis, OR 97331-4605 USA
My visiting professorship ends in June.  Interested in program optimization,
compilers, computer arithmetic, number theory.  17 yrs industrial experience.