mersenneforum.org Amazing 6
 Register FAQ Search Today's Posts Mark Forums Read

2020-09-23, 22:57   #100
tuckerkao

Jan 2020

112 Posts

Quote:
 Originally Posted by carpetpool 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?

2020-09-23, 23:16   #101
paulunderwood

Sep 2002
Database er0rr

3,491 Posts

Quote:
 Originally Posted by tuckerkao 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

2020-09-23, 23:25   #102
tuckerkao

Jan 2020

112 Posts

Quote:
 Originally Posted by paulunderwood 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

2020-09-23, 23:41   #103
paulunderwood

Sep 2002
Database er0rr

3,491 Posts

Quote:
 Originally Posted by tuckerkao 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

2020-09-28, 03:49   #104
paulunderwood

Sep 2002
Database er0rr

66438 Posts

Quote:
 Originally Posted by paulunderwood 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

 2020-09-28, 17:04 #105 paulunderwood     Sep 2002 Database er0rr DA316 Posts 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
2020-10-01, 20:52   #106
paulunderwood

Sep 2002
Database er0rr

3,491 Posts

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
 x2my.c (3.4 KB, 28 views) x2my.dat.txt (4 Bytes, 20 views)

Last fiddled with by paulunderwood on 2020-10-04 at 17:10

2020-10-06, 00:38   #107
paulunderwood

Sep 2002
Database er0rr

3,491 Posts
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
 x2myxp2.c (3.4 KB, 13 views) x2myxp2.dat.txt (4 Bytes, 14 views)

Last fiddled with by paulunderwood on 2020-10-06 at 14:03

 Similar Threads Thread Thread Starter Forum Replies Last Post Uncwilly Astronomy 6 2018-02-01 05:40 Miszka Information & Answers 2 2014-07-04 17:11 Xyzzy Lounge 6 2012-03-25 22:57 R.D. Silverman Factoring 5 2006-01-26 09:14 clowns789 Hardware 1 2003-12-27 16:57

All times are UTC. The time now is 03:21.

Wed Nov 25 03:21:43 UTC 2020 up 76 days, 32 mins, 4 users, load averages: 1.72, 1.74, 1.61