20190216, 01:10  #12 
Sep 2002
Database er0rr
2^{3}×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. Last fiddled with by paulunderwood on 20190216 at 01:10 
20190217, 07:21  #13  
Sep 2002
Database er0rr
2^{3}×3×139 Posts 
Quote:
Testing has reached 5.9*10^11 Last fiddled with by paulunderwood on 20190217 at 07:23 

20190219, 00:15  #14 
Sep 2002
Database er0rr
3336_{10} Posts 
We can test Euler 6^((n1)/2)==kronecker(6,n) mod n and the Lucas binary chain: x^((n+1)/2) == kronecker(6^r+2,n) mod (n, x^26^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 20190219 at 00:26 
20190222, 15:48  #15 
Sep 2002
Database er0rr
2^{3}·3·139 Posts 
b=3 and semiprimes
Up until now this thread has been about b=6. If b=3 then pseudoprimes seem to be semiprimes (n<10^9). Moreover, znorder(Mod(3,n))+1 == 2*r for such pseudoprimes.

20190223, 05:41  #16  
Sep 2002
Database er0rr
2^{3}·3·139 Posts 
Quote:
Code:
[n,znorder(Mod(3,n)),r,z+1==2*r,factor(n)]= [1479967201, 124200, 101203, 0, [41, 1; 461, 1; 78301, 1]] 

20190225, 19:32  #17  
Sep 2002
Database er0rr
3336_{10} Posts 
Quote:


20190831, 23:11  #18 
Sep 2002
Database er0rr
110100001000_{2} Posts 
Recall this test:
Code:
gcd(210,n)==1 b=6 a=6^r where kronecker(a^24,n) == 1 and gcd(a^3a,n) == 1 Test (b*x)^((n+1)/2) == b*kronecker(b*(a+2),n) mod (n,x^2a*x+1) I have had some nearmisses 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 timeconsuming. Last fiddled with by paulunderwood on 20190831 at 23:54 
20190904, 22:26  #19  
Sep 2002
Database er0rr
2^{3}×3×139 Posts 
Quote:
1. What is the probability of a composite number such that gcd(210,n) == 1 is 6PRP? 2. Of those numbers what is the average order of 6? 3. What is the probability for those that have gcd(a^3a, n) == 1 and kronecker(a^24, n) == 1 Last fiddled with by paulunderwood on 20190904 at 22:41 

20191023, 17:21  #20 
Sep 2002
Database er0rr
2^{3}·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. Last fiddled with by paulunderwood on 20191024 at 07:41 
20191024, 04:38  #21 
Romulan Interpreter
Jun 2011
Thailand
10000110111011_{2} 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^21,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 1selfridge test. So it seems that you waste a selfridge, not gaining one, isn't it? Last fiddled with by LaurV on 20191024 at 05:16 
20191024, 07:03  #22 
Sep 2002
Database er0rr
110100001000_{2} 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 "<order(6,n)" as indication to where one should look. It should not be calculated. Last fiddled with by paulunderwood on 20191024 at 07:17 
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  20180201 05:40 
Amazing result in P1  Miszka  Information & Answers  2  20140704 17:11 
Amazing academic resource  Xyzzy  Lounge  6  20120325 22:57 
Amazing!!!  R.D. Silverman  Factoring  5  20060126 09:14 
Two Amazing Things  clowns789  Hardware  1  20031227 16:57 