mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > sweety439

Reply
 
Thread Tools
Old 2020-02-11, 03:25   #1
sweety439
 
sweety439's Avatar
 
Nov 2016

7·11·29 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
Old 2020-02-11, 03:26   #2
sweety439
 
sweety439's Avatar
 
Nov 2016

42718 Posts
Default

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.
sweety439 is offline   Reply With Quote
Old 2020-02-11, 05:09   #3
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

23×72×11 Posts
Default

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.
VBCurtis is online now   Reply With Quote
Old 2020-02-11, 05:18   #4
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

572710 Posts
Default

Quote:
Originally Posted by sweety439 View Post
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.
So much plagiarism.
Quote:
Originally Posted by 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.
You could have at least acknowledged your sources.

[edit]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.

Last fiddled with by retina on 2020-02-11 at 05:24
retina is offline   Reply With Quote
Old 2020-02-11, 11:08   #5
sweety439
 
sweety439's Avatar
 
Nov 2016

7·11·29 Posts
Default

Quote:
Originally Posted by retina View Post
So much plagiarism.You could have at least acknowledged your sources.

[edit]There are even a notes on the WP page that say:
This test always uses base 2 for the Fermat test part, 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 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 2020-02-11 at 11:11
sweety439 is offline   Reply With Quote
Old 2020-02-11, 11:27   #6
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

3·23·83 Posts
Default

Quote:
Originally Posted by sweety439 View Post
Thus, this test not the same as my test.
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.
retina is offline   Reply With Quote
Old 2020-02-11, 13:52   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Thumbs up

Quote:
Originally Posted by retina View Post
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.
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.

Last fiddled with by R.D. Silverman on 2020-02-11 at 13:58
R.D. Silverman is offline   Reply With Quote
Old 2020-02-11, 19:49   #8
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22·5·173 Posts
Default

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:
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.
I certainly find plagiarism objectionable.

OTOH the reporting window says

Quote:
Note: This is ONLY to be used to report spam, advertising messages, and problematic (harassment, fighting, or rude) posts.
I'm not sure the post sinks to this level.
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Pretty Fast Primality Test (for numbers = 3 mod 4) tapion64 Miscellaneous Math 40 2014-04-20 05:43
Proof of Primality Test for Fermat Numbers princeps Math 15 2012-04-02 21:49
The fastest primality test for Fermat numbers. Arkadiusz Math 6 2011-04-05 19:39
A primality test for Fermat numbers faster than Pépin's test ? T.Rex Math 0 2004-10-26 21:37
Using Motorola 7410s to factor numbers or test for primality nukemyrman Hardware 7 2003-03-04 16:08

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

Mon Sep 21 20:02:06 UTC 2020 up 11 days, 17:13, 1 user, load averages: 3.31, 2.78, 2.46

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.