🚀 go-pugleaf

In article <1k3qqpINNt0@gaia.ucs.orst.edu> pmontgom@math.orst.edu (Peter Montgomery) writes:
:In article <1993Jan25.150556.24096@linus.mitre.org> bs@fatima.mitre.org 
 
stuff deleted....

: >: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).
:
Indeed. This is a variant of Cantor-Zassenhaus. [for polynomial roots
mod p]. 
--
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"