Consider the semi-prime n=p*q. From A^n+t^n == (A+t)^n mod n we have both:
A^p+t^p == (A+t)^p mod q
A^q+t^q == (A+t)^q mod p
So in trying to construct a counterexample we might do:
p = k*(q-1)+1
q = l*(p-1)+1
Making the substitution we get:
p = k*l*(p-1)+1 which implies k*l == 1 which means p = q.
If this construction method does not work, can it be extended to more prime factors?
Why do I get the counterexample [n, a, t, t2]=[415681338623, 0, 2106331569, 9028142873] when gcd(a^3-a,n)>1?
Why are two sub-tests needed, one for t and one for t2?
Last fiddled with by paulunderwood on 2021-09-30 at 19:53
|