 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

4,133 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

4,133 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

4,133 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, 43 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 09:10.

Mon May 23 09:10:50 UTC 2022 up 39 days, 7:12, 0 users, load averages: 1.83, 1.51, 1.40