mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   Singleton / Complex / General Tests -- Trinomiality Preservation (https://www.mersenneforum.org/showthread.php?t=27142)

paulunderwood 2021-09-30 20:04

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);}[/code]

Testing A^n+t^n == (A+t)^n mod n and A^n+t2^n == (A+t2)^n mod n with GCDs.

[QUOTE=Nick;589094]For that formula, you need n to be prime not just semi-prime (or I have misunderstood what you mean!)[/QUOTE]

It works for n prime, always (with kronecker(a^2-4,n)==-1). I am firstly trying to construct a semi-prime counterexample.

paulunderwood 2021-10-01 11:32

[QUOTE=paulunderwood;589091]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

[/QUOTE]

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.

:spider:

[n, a, t, t2]=[79786523, 20692263, 4163322, 8326644] is a counterexample. Once again the primes win!

paulunderwood 2021-10-06 15:57

1 Attachment(s)
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
[/CODE]


All times are UTC. The time now is 23:14.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.