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

2019-02-16, 01:10   #12
paulunderwood

Sep 2002
Database er0rr

23×3×139 Posts

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
 6_r.cpp.txt (3.1 KB, 33 views)

Last fiddled with by paulunderwood on 2019-02-16 at 01:10

2019-02-17, 07:21   #13
paulunderwood

Sep 2002
Database er0rr

23×3×139 Posts

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

 2019-02-19, 00:15 #14 paulunderwood     Sep 2002 Database er0rr 333610 Posts 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
 2019-02-22, 15:48 #15 paulunderwood     Sep 2002 Database er0rr 23·3·139 Posts 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.
2019-02-23, 05:41   #16
paulunderwood

Sep 2002
Database er0rr

23·3·139 Posts

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

2019-02-25, 19:32   #17
paulunderwood

Sep 2002
Database er0rr

333610 Posts

Quote:
 Originally Posted by paulunderwood 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
 6_r_lucas.cpp.txt (2.7 KB, 32 views)

 2019-08-31, 23:11 #18 paulunderwood     Sep 2002 Database er0rr 1101000010002 Posts 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
2019-09-04, 22:26   #19
paulunderwood

Sep 2002
Database er0rr

23×3×139 Posts

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

2019-10-23, 17:21   #20
paulunderwood

Sep 2002
Database er0rr

23·3·139 Posts

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

Last fiddled with by paulunderwood on 2019-10-24 at 07:41

 2019-10-24, 04:38 #21 LaurV Romulan Interpreter     Jun 2011 Thailand 100001101110112 Posts 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
 2019-10-24, 07:03 #22 paulunderwood     Sep 2002 Database er0rr 1101000010002 Posts 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 "

 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 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