View Single Post
Old 2020-02-11, 03:25   #1
sweety439
 
Nov 2016

281910 Posts
Default 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.
sweety439 is offline   Reply With Quote