View Single Post
Old 2021-09-30, 19:23   #10
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×7×281 Posts
Default

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
paulunderwood is offline   Reply With Quote