mersenneforum.org I found the primality test, there seems to be no composite numbers that pass the test
 Register FAQ Search Today's Posts Mark Forums Read

 2020-02-11, 03:25 #1 sweety439     "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 D3D16 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.
 2020-02-11, 03:26 #2 sweety439     "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 3,389 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.
 2020-02-11, 05:09 #3 VBCurtis     "Curtis" Feb 2005 Riverside, CA 5×7×151 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.
2020-02-11, 05:18   #4
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

11×587 Posts

Quote:
 Originally Posted by sweety439 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.

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

2020-02-11, 11:08   #5
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

3,389 Posts

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

2020-02-11, 11:27   #6
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

645710 Posts

Quote:
 Originally Posted by sweety439 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.

2020-02-11, 13:52   #7
R.D. Silverman

Nov 2003

1D2416 Posts

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

2020-02-11, 19:49   #8
Dr Sardonicus

Feb 2017
Nowhere

132308 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:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post tapion64 Miscellaneous Math 40 2014-04-20 05:43 princeps Math 15 2012-04-02 21:49 Arkadiusz Math 6 2011-04-05 19:39 T.Rex Math 0 2004-10-26 21:37 nukemyrman Hardware 7 2003-03-04 16:08

All times are UTC. The time now is 17:44.

Wed May 25 17:44:03 UTC 2022 up 41 days, 15:45, 0 users, load averages: 1.15, 1.20, 1.26

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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔