Editing Probable prime (section)

==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''&minus;1)/2</sup> equals <math>(\tfrac{a}{p})</math> modulo&nbsp;''p'', where <math>(\tfrac{a}{p})</math> is the [[Jacobi symbol]]. An Euler probable prime which is composite is called an [[Euler&ndash;Jacobi pseudoprime]] to base&nbsp;''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 &minus;1. Write ''n''&nbsp;=&nbsp;''d''&nbsp;·&nbsp;2<sup>''s''</sup>&nbsp;+&nbsp;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>
or
: <math>a^{d\cdot 2^r}\equiv -1\pmod n\text{ for some }0\leq r\leq s-1. \, </math>

A composite strong probable prime to base ''a'' is called a [[strong pseudoprime]] to base ''a''. Every strong probable prime to base ''a'' is also an Euler probable prime to the same base, but not vice versa.

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 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
** Beginning with <math>s=0</math>, <math>d</math> would be <math>96</math>
** Increasing <math>s</math>, we see that <math>d=3</math> and <math>s=5</math>, since <math>96=3\cdot 2^5</math>
* Step 2: Choose <math>a</math>, <math>1 < a < 97 - 1</math>. We will choose <math>a = 2</math>.
* Step 3: Calculate <math>a^d \bmod n</math>, i.e. <math>2^3 \bmod 97</math>. Since it isn't congruent to <math>1</math>, we continue to test the next condition
* Step 4: Calculate <math>2^{3\cdot 2^r} \bmod 97</math> for <math>0 \leq r < s</math>. If it is congruent to <math>96</math>, <math>97</math> is probably prime. Otherwise, <math>97</math> is definitely composite
** <math>r=0: 2^3 \equiv 8 \pmod{97}</math>
** <math>r=1: 2^6 \equiv 64 \pmod{97}</math>
** <math>r=2: 2^{12} \equiv 22 \pmod{97}</math>
** <math>r=3: 2^{24} \equiv 96 \pmod{97}</math>
* Therefore, <math>97</math> is a strong probable prime base 2 (and is therefore a probable prime base 2).