Thread: 1+1 Selfridges PRP test View Single Post
2020-11-19, 14:51   #15
Dr Sardonicus

Feb 2017
Nowhere

4,457 Posts

Quote:
 Originally Posted by paulunderwood Results for a=4: [68368998319, 4] [416032697359, 4] [4752200398399, 4] All semi-primes, p*q, where gcd(p-1,q-1)=2^i*3^j
No. If g= gcd(p-1,q-1) it is not g, but (p-1)/g and (q-1)/g that are 2*i*3^j; in most of the cases g = p-1.

Furthermore, in every single case, p-1 and q-1 are small multiples of a single prime.

I think there's enough numerical evidence to try to devise a script to construct counterexamples p*q to your test. For example, with a = 4, D = 12, E = 140, find primes l for which (say)

p = 6*l + 1 and q = 36*l + 1 are both prime

p*q is congruent to -1 (mod 560)

kronecker(12,p*q) = - 1

[there's another condition I'm too lazy to look up]

The congruence condition mod 560 produces something like 8 possibilities for l (mod 560).

The other examples show the multipliers 6 and 36 aren't the only possibilities.