Probable prime: Difference between revisions

Browse history interactively

← Previous edit

Content deleted Content added

VisualWikitext

Revision as of 19:05, 5 November 2023 edit 102.13.101.214 (talk) No edit summary Tags: Reverted Visual edit Mobile edit Mobile web edit ← Previous edit		Latest revision as of 17:45, 22 April 2024 edit undo CheeseyHead (talk \| contribs) Extended confirmed users 1,832 edits Some fixes Tag: Visual edit
(3 intermediate revisions by 3 users not shown)
Line 1: {{distinguish\|Provable prime}} In [[number theory]], a '''probable prime''' ('''PRP)''') is an [[integer]] that satisfies a specific condition that is satisfied by all [[prime numbers]], but which is not satisfied by most [[composite number]]s. Different types of probable primes have different specific conditions. While there may be probable primes that are composite (called [[pseudoprime]]s), the condition is generally chosen in order to make such exceptions rare. Fermat's test for compositeness, which is based on [[Fermat's little theorem]], works as follows: given an integer ''n'', choose some integer ''a'' that is not a multiple of ''n''; (typically, we choose ''a'' in the range {{nowrap\|1 < ''a'' < ''n'' − 1}}). Calculate {{nowrap\|''a''<sup>''n'' − 1</sup> [[modular arithmetic\|modulo]] ''n''}}. If the result is not 1, then ''n'' is composite. If the result is 1, then ''n'' is likely to be prime; ''n'' is then called a '''probable prime to base''' ''a''. A '''weak probable prime to base''' ''a'' is an integer that is a probable prime to base ''a'', but which is not a strong probable prime to base ''a'' (see below). For a fixed base ''a'', it is unusual for a composite number to be a probable prime (that is, a pseudoprime) to that base. For example, up to {{nowrap\|25 × 10<sup>9</sup>}}, there are 11,408,012,595 odd composite numbers, but only 21,853 pseudoprimes base 2.<ref name="PSW">{{cite journal \|author1 = Carl Pomerance \|author-link1 = Carl Pomerance \|author2 = John L. Selfridge \|author-link2 = John L. Selfridge \|author3 = Samuel S. Wagstaff, Jr. \|author-link3 = Samuel S. Wagstaff, Jr. \|title=The pseudoprimes to 25·10<sup>9</sup> \|journal=Mathematics of Computation \|date=July 1980 \|volume=35 \|issue=151 \|pages=1003–1026 \|url=//math.dartmouth.edu/~carlp/PDF/paper25.pdf \|jstor=2006210 \|doi=10.1090/S0025-5718-1980-0572872-7 \|doi-access=free }}</ref>{{rp\|1005}} The number of odd primes in the same interval is 1,091,987,404. ==Properties== ~~[[primality testing\|~~Probable primality is a basis for efficient [[primality testing]] ~~algorithms~~[[algorithm]]s, which find application in [[cryptography]]. These algorithms are usually [[randomized algorithm\|probabilistic]] in nature. The idea is that while there are composite probable primes to base ''a'' for any fixed ''a'', we may hope there exists some fixed ''P''<1 such that for ''any'' given composite ''n'', if we choose ''a'' at random, then the probability that ''n'' is pseudoprime to base ''a'' is at most ''P''. If we repeat this test ''k'' times, choosing a new ''a'' each time, the probability of ''n'' being pseudoprime to all the ''a''s tested is hence at most ''P<sup>k</sup>'', and as this decreases exponentially, only moderate ''k'' is required to make this probability negligibly small (compared to, for example, the probability of computer hardware error).]] This is unfortunately false for weak probable primes, because there exist [[Carmichael number]]s; but it is true for more refined notions of probable primality, such as strong probable primes (''P'' = 1/4, [[Miller–Rabin primality test\|Miller–Rabin algorithm]]), or Line 18: ==Variations== An '''Euler probable prime to base''' ''a'' is an integer that is indicated prime by the somewhat stronger theorem that for any prime ''p'', ''a''<sup>(''p''−1)/2</sup> equals <math>(\tfrac{a}{p})</math> modulo ''p'', where <math>(\tfrac{a}{p})</math> is the [[Jacobi symbol]]. An Euler probable prime which is composite is called an [[Euler–Jacobi pseudoprime]] to base ''a''. The smallest Euler-Jacobi pseudoprime to base 2 is 561.{{r\|PSW\|p=1004}} There are 11347 Euler-Jacobi pseudoprimes base 2 that are less than 25·10<sup>9</sup>.{{r\|PSW\|p=1005}} This test may be improved by using the fact that the only square roots of 1 modulo a prime are 1 and −1. Write ''n'' = ''d'' · 2<sup>''s''</sup> + 1, where ''d'' is odd. The number ''n'' is a '''strong probable prime''' ('''SPRP''') '''to base''' ''a'' if: : <math>a^d\equiv 1\pmod n,\;</math> Line 30: The smallest strong pseudoprime base 2 is 2047.{{r\|PSW\|p=1004}} There are 4842 strong pseudoprimes base 2 that are less than 25·10<sup>9</sup>.{{r\|PSW\|p=1005}} There are also [[Lucas pseudoprime\|Lucas probable prime]]s, which are based on [[Lucas sequence]]s. A Lucas probable prime test can be used alone. The [[Baillie–PSW primality test]] combines a Lucas test with a strong probable prime test. ===Example of ~~SPRP~~testing for a strong probably prime=== To test whether 97 is a strong probable prime base 2: * Step 1: Find <math>d</math> and <math>s</math> for which <math>96=d\cdot 2^s</math>, where <math>d</math> is odd Line 50: * [[Baillie–PSW primality test]] * [[Euler–Jacobi pseudoprime]] * [[Carmichael number]]▼ * [[Lucas pseudoprime]] * [[Miller–Rabin primality test]] * [[Perrin number#Perrin primality test\|Perrin primality test]] ▲* [[Carmichael number]] ==External links==