 mersenneforum.org Singleton / Complex / General Tests -- Trinomiality Preservation
 Register FAQ Search Today's Posts Mark Forums Read  2021-09-30, 20:04   #12
paulunderwood

Sep 2002
Database er0rr

2·7·281 Posts Recap:

Code:
{tst(n,a)=gcd(a^3-a,n)==1&&kronecker(a^2-4,n)==-1&&Mod(Mod(x,n),x^2-a*x+1)^(n+1)==1;}

{tst1(n,a,t)=gcd(t^2-1,n)==1&&gcd(a+t,n)==1&&gcd(a*t+1,n)==1&&
Mod(t,n)^(n-1)==1&&Mod(Mod(x+t,n),x^2-a*x+1)^(n+1)==(a+t)*t+1;}

{tst2(n,a,t,t2)=gcd(t^2-t2^2,n)==1&&gcd((t*t2)^2-1,n)==1&&
tst(n,a)&&tst1(n,a,t)&&tst1(n,a,t2);}
Testing A^n+t^n == (A+t)^n mod n and A^n+t2^n == (A+t2)^n mod n with GCDs.

Quote:
 Originally Posted by Nick For that formula, you need n to be prime not just semi-prime (or I have misunderstood what you mean!)
It works for n prime, always (with kronecker(a^2-4,n)==-1). I am firstly trying to construct a semi-prime counterexample.

Last fiddled with by paulunderwood on 2021-09-30 at 20:08   2021-10-01, 11:32   #13
paulunderwood

Sep 2002
Database er0rr

393410 Posts Quote:
 Originally Posted by paulunderwood 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
This is wrong. If kronecker(a^2-4,p)==-1 then

1/A^q + t^q == | (A + t)^q | / (A + t)^q mod p (I think).

I can't make nor tails of it. Semi-prime testing has reached p = 2521 and q = 2*k*(p-1)+1 for k=4..14. It is slow going. [n, a, t, t2]=[79786523, 20692263, 4163322, 8326644] is a counterexample. Once again the primes win!

Last fiddled with by paulunderwood on 2021-10-01 at 13:27   2021-10-06, 15:57   #14
paulunderwood

Sep 2002
Database er0rr

393410 Posts David Broadhurst gave me a file (attached to this message) of 100 small frauds that fool tst2, which took 42 seconds to produce.

He also found this 111 digit counterexample:

Code:
{[n,a,t,t2]=[
710641788142972835479085586911122643420643446726634578803992738008610099322008489919397662572833644270860844387,
481905506343238180263291435373078635219195334156921743957480549136989940684358483625484024629644986669892081256,
148287259869443430225832503946134162145762408831833753293682564445021118105658569785248629217653453554212689421,
238592749879783960713735924092293283842736794675381443476994761164913615939177038960039158690185545733634042511];

if(tst2(n,a,t,t2),print("\\\\ fooled at "#Str(n)" digits"));}
\\ fooled at 111 digits
Attached Files forpaul.txt (7.4 KB, 21 views)   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post MattcAnderson Miscellaneous Math 2 2020-11-26 00:48 devarajkandadai Miscellaneous Math 2 2019-08-27 14:52 bhelmes Math 1 2018-08-08 20:19 fivemack Factoring 5 2007-12-30 11:17 dave_0273 Math 3 2004-11-08 17:15

All times are UTC. The time now is 22:40.

Wed Dec 1 22:40:57 UTC 2021 up 131 days, 17:09, 1 user, load averages: 1.52, 1.33, 1.36