mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2020-09-23, 22:57   #100
tuckerkao
 
Jan 2020

3×41 Posts
Default

Quote:
Originally Posted by carpetpool View Post
There seems to be no n congruent to 3 or 5 modulo 8 (a.k.a 2 is a quadratic non-residue mod n).

I replaced b=2 to b=3:

Code:
[3, 1683683, 15, 879443]
[3, 1898999, 141, 1444216]
[3, 2586083, 27, 1612472]
[3, 2795519, 171, 2214249]
[3, 4042403, 25, 940643]
[3, 4099439, 207, 3562151]
[3, 5087171, 28, 3216314]
[3, 8243111, 120, 2486937]
Similarly, there are no counterexamples that 3 is a Q non-residue mod n, or n congruent to 5 or 7 modulo 12.

Maybe there could be some undiscovered primality test associated with that?
How about replace b = 4 or b = 8?
tuckerkao is offline   Reply With Quote
Old 2020-09-23, 23:16   #101
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

66618 Posts
Default

Quote:
Originally Posted by tuckerkao View Post
How about replace b = 4 or b = 8?
b=2, b=4 and b=8 seems to give counterexamples 7 mod 8, as you can see by running the Pari/GP program given in that post.

Last fiddled with by paulunderwood on 2020-09-23 at 23:17
paulunderwood is offline   Reply With Quote
Old 2020-09-23, 23:25   #102
tuckerkao
 
Jan 2020

3·41 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
b=2, b=4 and b=8 seems to give counterexamples 7 mod 8, as you can see by running the Pari/GP program given in that post.
Since 2, 4, 8 are the related bases, so the algorithm generates the similar results as the whole group.

Since the thread title is "Amazing 6", If b = 6, will the results be linked to b = 3 and/or b = 9?

Maybe I should go with the prime numbers such as b = 5 and b = 7.

Last fiddled with by tuckerkao on 2020-09-23 at 23:32
tuckerkao is offline   Reply With Quote
Old 2020-09-23, 23:41   #103
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5×701 Posts
Default

Quote:
Originally Posted by tuckerkao View Post
Since 2, 4, 8 are the related bases, so the algorithm generates the similar results as the whole group.

Since the thread title is "Amazing 6", If b = 6, will the results be linked to b = 3 and/or b = 9?

Maybe I should go with the prime numbers such as b = 5 and b = 7.
It is ad hoc. b=3 and all powers of 3 give counterexamples. I have not found any for b=5 -- I can't recall b=7 counterexample.

By plugging in primes to the aforementioned program will show you that sometimes a prime b will give counterexamples readily and sometimes another b not. If a prime does give counterexamples then so will its powers. Likewise powers of b that don't readily give counterexamples seem not to give counterexamples.

So maybe the powers are consistent.

Although this thread is labelled "Amazing 6" it has rambled on to other tests, all quadratric, some based on quadratic equations and most recently x^2-2*x+2^r as can be seen in this paper hot off the press.

Last fiddled with by paulunderwood on 2020-09-24 at 00:09
paulunderwood is offline   Reply With Quote
Old 2020-09-28, 03:49   #104
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5×701 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
I can tighten things up by doing the following test (for any a=2^r):
  • gcd(a-2,n)==1
  • gcd(a-4,n)==1
  • kronecker(1-a,n)==-1
  • Mod(1-a,n)^((n-1)/2)==-1
  • Mod(2,n)^((n-1)/2)==kronecker(2,n)
  • Mod(Mod(x,n),x^2-(4/a-2)*x+1)^((n+1)/2)==kronecker(a,n)

Reaching 10^15 should be doable over time and by dedicating enough cores to it; It took just over 2 days to get to 10^12 using Pari/GP on a single core. Rewriting in GMP+pari will speed up computation.
It is good up to 10^13 the verification of which took about 5 days on 1 core with GMP. If znorder is large for a particular n then it takes that n a few hours. I am going to put verification on the back boiler for now until the depths of winter when I will fire up a dedicated computer to take it to the next exponent or two.

Last fiddled with by paulunderwood on 2020-09-28 at 03:53
paulunderwood is offline   Reply With Quote
Old 2020-09-28, 17:04   #105
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5·701 Posts
Question x^2-y test

I have devised another PRP for odd non-square n:

Let y = 2^r-1

Then seek

gcd(r-1,n-1)==1
kronecker(y,n)==-1

and test

Mod(2,n)^(n-1)==1
Mod(y,n)^((n-1)/2)==-1
(x+1)^(n+1) == -y + 1 (mod n, x^2 - y)

Early results are good.

Edit: After 32 hours of pure Pari/GP, verification reached 10^12. Clearly GMP is required to take it up an exponent or two.

Last fiddled with by paulunderwood on 2020-09-30 at 20:32
paulunderwood is offline   Reply With Quote
Old 2020-10-01, 20:52   #106
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5·701 Posts
Thumbs up

Pari/GP took 32 hours to verify all "r" up to n<10^12. GMP was just over 4 times faster. I could speed things a little by doing a base-2 Euler PRP test on the list of 2-PSP I am using, but I will continue with Fermat 2-PRP tests. I will report back when I reach the next exponent, in a couple of days.

Edit: 10^13 was reached and no counterexamples found.

The GMP program and the required ".dat" file are attached -- remove ".txt".
Attached Files
File Type: c x2my.c (3.4 KB, 28 views)
File Type: txt x2my.dat.txt (4 Bytes, 20 views)

Last fiddled with by paulunderwood on 2020-10-04 at 17:10
paulunderwood is offline   Reply With Quote
Old 2020-10-06, 00:38   #107
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5×701 Posts
Default A slight variation for x^2-y

Instead of using base x+1 choose to use base x+2. Then the test is, with any y=2^r-1, for non-square odd n:

find jacobi(y,n)==-1

then test

2^(n-1) == 1 (mod n)
y^((n-1)/2)==-1 (mod n)
(x+2)^(n+1) == -y + 4 (mod n, x^2-y)

I can replace the Fermat 2-PRP test with an Euler 2-PRP to speed up verification.

Here is the (Euler 2-PRP version of) the in GMP plus ".dat" file -- remove ".txt"

The test has been verified up to 10^12
Attached Files
File Type: c x2myxp2.c (3.4 KB, 14 views)
File Type: txt x2myxp2.dat.txt (4 Bytes, 14 views)

Last fiddled with by paulunderwood on 2020-10-06 at 14:03
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Don't miss this amazing trick that the moon is going to do! Uncwilly Astronomy 6 2018-02-01 05:40
Amazing result in P-1 Miszka Information & Answers 2 2014-07-04 17:11
Amazing academic resource Xyzzy Lounge 6 2012-03-25 22:57
Amazing!!! R.D. Silverman Factoring 5 2006-01-26 09:14
Two Amazing Things clowns789 Hardware 1 2003-12-27 16:57

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

Thu Dec 3 11:22:12 UTC 2020 up 7:33, 0 users, load averages: 1.58, 1.31, 1.14

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.