View Single Post
 2020-02-11, 03:25 #1 sweety439   Nov 2016 22×3×5×47 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.