mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2019-02-16, 01:10   #12
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23×3×139 Posts
Default

The much faster attached program uses primesieve (4.4) rather than relying on GMP's "mpz_probab_prime_p" function.

Testing has reached 2.6*10^11.
Attached Files
File Type: txt 6_r.cpp.txt (3.1 KB, 33 views)

Last fiddled with by paulunderwood on 2019-02-16 at 01:10
paulunderwood is offline   Reply With Quote
Old 2019-02-17, 07:21   #13
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23×3×139 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
The much faster attached program uses primesieve (4.4) rather than relying on GMP's "mpz_probab_prime_p" function.

Testing has reached 2.6*10^11.
Saving the state to "6_r.dat" in the above program should read "%llu" not just "llu".

Testing has reached 5.9*10^11

Last fiddled with by paulunderwood on 2019-02-17 at 07:23
paulunderwood is offline   Reply With Quote
Old 2019-02-19, 00:15   #14
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

333610 Posts
Default

We can test Euler 6^((n-1)/2)==kronecker(6,n) mod n and the Lucas binary chain: x^((n+1)/2) == kronecker(6^r+2,n) mod (n, x^2-6^r*x+1) (where kronecker(6^(2*r)-4,n) == -1) separately very efficiently (especially when large FFTs are involved.)

No proof is forthcoming from any quarter. Testing of this very strong test for all 6^r has reached 10^12 and I will update my bio page at UTM periodically with my verification status of this test over the next few months by the end of which I hope to raise verification by another factor of 10.

Last fiddled with by paulunderwood on 2019-02-19 at 00:26
paulunderwood is offline   Reply With Quote
Old 2019-02-22, 15:48   #15
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23·3·139 Posts
Default b=3 and semi-primes

Up until now this thread has been about b=6. If b=3 then pseudoprimes seem to be semi-primes (n<10^9). Moreover, znorder(Mod(3,n))+1 == 2*r for such pseudoprimes.
paulunderwood is offline   Reply With Quote
Old 2019-02-23, 05:41   #16
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23·3·139 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Up until now this thread has been about b=6. If b=3 then pseudoprimes seem to be semi-primes (n<10^9). Moreover, znorder(Mod(3,n))+1 == 2*r for such pseudoprimes.
Code:
[n,znorder(Mod(3,n)),r,z+1==2*r,factor(n)]=
[1479967201, 124200, 101203, 0, [41, 1; 461, 1; 78301, 1]]
breaks the rule
paulunderwood is offline   Reply With Quote
Old 2019-02-25, 19:32   #17
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

333610 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
We can test Euler 6^((n-1)/2)==kronecker(6,n) mod n and the Lucas binary chain: x^((n+1)/2) == kronecker(6^r+2,n) mod (n, x^2-6^r*x+1) (where kronecker(6^(2*r)-4,n) == -1) separately very efficiently (especially when large FFTs are involved.)

No proof is forthcoming from any quarter. Testing of this very strong test for all 6^r has reached 10^12 and I will update my bio page at UTM periodically with my verification status of this test over the next few months by the end of which I hope to raise verification by another factor of 10.
I will be looking for a super set of counterexamples (form 10^12) by running the attached code: Fermat base b=6 and Lucas x^(n+1)==1 (mod n, x^2-6^r*x+1). A quick check shows that this verification code is 20% faster than the above code.
Attached Files
File Type: txt 6_r_lucas.cpp.txt (2.7 KB, 32 views)
paulunderwood is offline   Reply With Quote
Old 2019-08-31, 23:11   #18
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1101000010002 Posts
Default

Recall this test:

Code:
gcd(210,n)==1

b=6

a=6^r where kronecker(a^2-4,n) == -1 and gcd(a^3-a,n) == 1

Test (b*x)^((n+1)/2) == b*kronecker(b*(a+2),n) mod (n,x^2-a*x+1)
I have tested up to 10^13 now. This took a 2.2 GHz Opteron core over 6 months. My plan is to test to a further 120 fold, which might take a couple of years.

I have had some near-misses for which (b*x)^(n+1)==b^2 e,g, [n, a] = [2448631680221, 311366822712].

What is the average znorder I can expect for 6 and odd n? Sometimes it is small and sometimes it is very big and time-consuming.

Last fiddled with by paulunderwood on 2019-08-31 at 23:54
paulunderwood is offline   Reply With Quote
Old 2019-09-04, 22:26   #19
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23×3×139 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
.

What is the average znorder I can expect for 6 and odd n? Sometimes it is small and sometimes it is very big and time-consuming.
I will refine my question into three parts:

1. What is the probability of a composite number such that gcd(210,n) == 1 is 6-PRP?

2. Of those numbers what is the average order of 6?

3. What is the probability for those that have gcd(a^3-a, n) == 1 and kronecker(a^2-4, n) == -1

Last fiddled with by paulunderwood on 2019-09-04 at 22:41
paulunderwood is offline   Reply With Quote
Old 2019-10-23, 17:21   #20
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23·3·139 Posts
Default

I am not sure where this paper is going. The plan is still to extend the verified bound.

I have uploaded a new version as there were logical flaws.

Another update after LaurV's post below.
Attached Files
File Type: pdf A_Quadratic_Frobenius_Test.pdf (40.9 KB, 26 views)

Last fiddled with by paulunderwood on 2019-10-24 at 07:41
paulunderwood is offline   Reply With Quote
Old 2019-10-24, 04:38   #21
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

100001101110112 Posts
Default

Something is odd there... I am concerned especially about the part with the "ord(6,n)", if you know that, then you can easily factor n.

And looking to your S_2 code, something is messy too... Did you try to call that function with the argument... say 37*43? What does it return?
Similar for S_1_2 if you call it with, say, 43*55987 ?


Edit: additional, the "while" is quite heavy and it takes a lot of time in both cases, and moreover, a forced exit is necessary if gcd(a^2-1,n) is not 1, in this case you just factored n.
Edit 2: modify 210 to 210*37*43*311*55987 in both algorithms will skip most of the exception cases, and it will make it marginally faster (because early exit). Yet, this is still equivalent to a PRP test to some base, which you may find by calculus, then do a 1-selfridge test. So it seems that you waste a selfridge, not gaining one, isn't it?

Last fiddled with by LaurV on 2019-10-24 at 05:16
LaurV is offline   Reply With Quote
Old 2019-10-24, 07:03   #22
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1101000010002 Posts
Default

Thanks LaurV for taking the time to look at my paper. I have updated it and reposted it based on your observations. Getting the logic sorted around the jacobi symbol and the gcd took some thinking and reworking of the code.

Both functions should now handle your exceptional numbers. Please let me know if there is another problem.

I wrote "<order(6,n)" as indication to where one should look. It should not be calculated.

Last fiddled with by paulunderwood on 2019-10-24 at 07:17
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 06:51.

Wed Aug 12 06:51:23 UTC 2020 up 26 days, 2:38, 1 user, load averages: 1.59, 1.65, 1.56

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.