Re: Elementary group theory: Proof of Fermat-Maas primality-test

hagman a écrit :
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.

The goal of the condition (1) is not to avoid easy factoring but to
ensure that 3 is invertible modulo (p-1)*(q-1) and can be used as
encrypting exponent.

mm
.

Quantcast