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)

 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