mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-09-30, 20:04   #12
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·7·281 Posts
Default

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 View Post
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
paulunderwood is offline   Reply With Quote
Old 2021-10-01, 11:32   #13
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

393410 Posts
Unhappy

Quote:
Originally Posted by paulunderwood View Post
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
paulunderwood is offline   Reply With Quote
Old 2021-10-06, 15:57   #14
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

393410 Posts
Default

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
File Type: txt forpaul.txt (7.4 KB, 21 views)
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Pythagorean Theorem in Complex Numbers MattcAnderson Miscellaneous Math 2 2020-11-26 00:48
Complex Devaraj numbers devarajkandadai Miscellaneous Math 2 2019-08-27 14:52
biquadratic complex function and possible factorisation bhelmes Math 1 2018-08-08 20:19
Counting ideals during singleton removal fivemack Factoring 5 2007-12-30 11:17
Complex number problem 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

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.