Re: Elementary group theory: Proof of Fermat-Maas primality-test (was: correcting *** ...)


Robert Maas, see http://tinyurl.com/uh3t schrieb:

I finished my side topics, namely constructing a primitive element
of the mulplicative group modulo a prime, after you've already used
the Fermat-Maas algorithm to prove it's really prime, making use of
the known factorization of p-1 that you got when you directly
constructed p from it. So now I'm finally back to directly
replying to what *** wrote:

From: "*** T. Winter" <***.Win...@xxxxxx>
Even the current methods take a considerably long time (minutes or
hours) to factor *each* 80-digit number. In that time I could
randomly synthesize thousands of 80-digit products, not just one.
Yes. But generating those numbers *is* much faster than factorising.
Primality proving is *much* faster than factorising.

Are you claiming that your suggested method
- generating random large odd numbers, applying Fermat's little
theorem as a preliminary filter to get rid of most composites,
then applying state-of-art method for testing primality of p
without knowing factorization of p-1,
is faster then my favorite method of
- directly synthesizing a known product for p-1, applying Fermat's
little theorem as a preliminary filter to get rid of most
composites, then testing primality p using the Fermat-Maas
algorithm?

This slightly resembles the procedure to generate good candidates for
factors of an RSA product p*q
as spelled out in my 20 years old Knuth.
To avoid easily factored cases one should be sure that
(1) p-1, q-1 are not divisible by 3
(2) p-1, q-1, p+1, q+1 should have at least one /large/ factor
(3) p/q should not be near a simple fraction.

Knuth proposes:
Let n0 = random number with 80 digits, say.
Search for the first prime p1>=n0 (requires ~90 tests, however Knuth is
satisfied with probable primes)
Let n2 = random number with 40 digits, say.
Check numbers of the form k*p1+1 for primality, where k>=n2 and k even
and k=p1 mod 3 (requires ~45 tests of 120 digit numbers).
Let p be the first prime found among these. (p has ~120 digits; as a
bonus for the paranoid: Retry if p+1 has a simple factorization).
Similarly find q with about 130 digits. Then we have an N=pq with 250
digits.

It looks like this method also favors prime generation based on a known
factorization of p-1.

.