20200211, 03:25  #1 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
41×89 Posts 
I found the primality test, there seems to be no composite numbers that pass the test
Input: Integer n>1
1. Check if n is a square: if n = m^2 for integers m, output composite; quit. 2. Find the first b in the sequence 2, 3, 4, 5, 6, 7, ... for which the Jacobi symbol (b/n) is −1. 3. Perform a base b strong probable prime test. If n is not a strong probable prime base b, then n is composite; quit. 4. Find the first D in the sequence 5, −7, 9, −11, 13, −15, ... for which the Jacobi symbol (D/n) is −1. Set P = 1 and Q = (1 − D) / 4. 5. Perform a strong Lucas probable prime test using parameters D, P, and Q. If n is not a strong Lucas probable prime, then n is composite. Otherwise, n is prime. The numbers which is strong pseudoprime to base b (where b is the first number in the sequence 2, 3, 4, 5, 6, 7, 8, ... such that (b/n) = −1) are 703, 3277, 3281, 8911, 14089, 29341, 44287, 49141, 80581, 88357, 97567, ... The numbers which is strong Lucas pseudoprime to (P, Q) (where P = 1, Q is the first number in the sequence −1, 2, −2, 3, −3, 4, −4, ... such that ((1−4Q)/n) = −1) are 5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309, 58519, 75077, 97439, ... I conjectured that the intersection of these two sequence is empty. 
20200211, 03:26  #2 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
41·89 Posts 
The step 1 "check if n is a square" is needed, since the search in step 2 and step 4 will never succeed if n is square.

20200211, 05:09  #3 
"Curtis"
Feb 2005
Riverside, CA
2^{4}×347 Posts 
And yet, since you have no proof that the intersection is empty, it's just another probable prime test. A counterexample is possible, so it's not a primality proof.

20200211, 05:18  #4  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
29·229 Posts 
Quote:
Quote:
[edit]There are even a notes on the WP page that say: Quote:
Last fiddled with by retina on 20200211 at 05:24 

20200211, 11:08  #5  
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
7101_{8} Posts 
Quote:
Thus, this test not the same as my test. Edit: n must be an odd nonsquare number, if n is either even or square then we can know that n is composite (except n=2). Last fiddled with by sweety439 on 20200211 at 11:11 

20200211, 11:27  #6 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
14761_{8} Posts 

20200211, 13:52  #7  
"Bob Silverman"
Nov 2003
North of Boston
16510_{8} Posts 
Quote:
BTW, the change of base is irrelevant. [Hint: it is just a different subgroup generator; see just below] One other thing. Now that we have a "new" test [It isn't], perhaps the author will explain to us how he derived this test. He can start with an explanation of what computations are being performed in GF(p^2) where p is the number being tested. Perhaps he can give an explanation in terms of the generators of the various (multiplicative) subgroups. If he can't then he should STFU and stop stealing and copying ideas (that he doesn't understand) from elsewhere. Last fiddled with by R.D. Silverman on 20200211 at 13:58 

20200211, 19:49  #8  
Feb 2017
Nowhere
2^{2}×5^{2}×61 Posts 
OP said in title (my emphasis), "I found the primality test, there seems to be no composite numbers that pass the test"
I conclude that "found" means "located." I therefore ask, "Where?" and demand the poster give due credit. I also note that it is often stated that there are thought to be infinitely many composites which "pass" a BPSW test, though none have been found. I am unsure whether to report the post to the Moderators. The FAQ says Quote:
OTOH the reporting window says Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Pretty Fast Primality Test (for numbers = 3 mod 4)  tapion64  Miscellaneous Math  40  20140420 05:43 
Proof of Primality Test for Fermat Numbers  princeps  Math  15  20120402 21:49 
The fastest primality test for Fermat numbers.  Arkadiusz  Math  6  20110405 19:39 
A primality test for Fermat numbers faster than Pépin's test ?  T.Rex  Math  0  20041026 21:37 
Using Motorola 7410s to factor numbers or test for primality  nukemyrman  Hardware  7  20030304 16:08 