mersenneforum.org (https://www.mersenneforum.org/index.php)
-   sweety439 (https://www.mersenneforum.org/forumdisplay.php?f=137)
-   -   I found the primality test, there seems to be no composite numbers that pass the test (https://www.mersenneforum.org/showthread.php?t=25213)

 sweety439 2020-02-11 03:25

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 2020-02-11 03:26

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.

 VBCurtis 2020-02-11 05:09

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.

 retina 2020-02-11 05:18

[QUOTE=sweety439;537289]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.[/QUOTE]So much plagiarism.[quote=https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test]1 Optionally, perform trial division to check if n is divisible by a small prime number less than some convenient limit.
2 Perform a base 2 strong probable prime test. If n is not a strong probable prime base 2, then n is composite; quit.
3 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.
4 Perform a strong Lucas probable prime test on n using parameters D, P, and Q. If n is not a strong Lucas probable prime, then n is composite. Otherwise, n is almost certainly prime.[/quote]You could have at least acknowledged your sources.

There are even a notes on the WP page that say:[quote]The second step is a single application of the Miller-Rabin primality test using base 2. There is nothing special about using base 2; other bases might work just as well. However, much work has been done (see above) to verify that the combination of the base 2 strong probable prime test and a strong Lucas test does a good job of distinguishing primes from composites.
<-->
If n is a perfect square, then step 3 will never yield a D with (D/n) = −1; this is not a problem because perfect squares are easy to detect using Newton's method for square roots. If step 3 fails to produce a D quickly, one should check whether n is a perfect square.[/quote]

 sweety439 2020-02-11 11:08

[QUOTE=retina;537304]So much plagiarism.You could have at least acknowledged your sources.

There are even a notes on the WP page that say:[/QUOTE]

This test [I]always uses base 2 for the Fermat test part[/I], but I use the base which is the smallest integer b>=2 such that JacobiSymbol(b,n) = -1

Thus, this test not the same as my test.

Edit: n must be an [B]odd nonsquare number[/B], if n is either even or square then we can know that n is composite (except n=2).

 retina 2020-02-11 11:27

[QUOTE=sweety439;537320]Thus, this test not the same as my test.[/QUOTE]I didn't say the test was the same. I said you plagiarised the text. You showed no respect to the original authors. Perhaps we should show you a similar amount of respect in return.

 R.D. Silverman 2020-02-11 13:52

[QUOTE=retina;537321]I didn't say the test was the same. I said you plagiarised the text. You showed no respect to the original authors. Perhaps we should show you a similar amount of respect in return.[/QUOTE]

Thank you!

BTW, the change of base is irrelevant. [Hint: it is just a different sub-group 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) sub-groups.

If he can't then he should STFU and stop stealing and copying ideas (that he doesn't understand) from elsewhere.

 Dr Sardonicus 2020-02-11 19:49

OP said in title (my emphasis), "I [b][i]found[/i][/b] the primality test, there seems to be no composite numbers that pass the test"

I conclude that "found" means "located." I therefore ask, "[i]Where?[/i]" 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]You will find 'Report' links in many places throughout the board. These links allow you to alert the board staff to anything which you find to be offensive, objectionable or illegal.[/quote]I certainly find plagiarism objectionable.

OTOH the reporting window says

[quote][b]Note:[/b] This is ONLY to be used to report spam, advertising messages, and problematic (harassment, fighting, or rude) posts.[/quote]I'm not sure the post sinks to this level.

 All times are UTC. The time now is 04:02.