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 probable prime

To test whether 97 is a strong probable prime base 2:
* Step 1: Find and for which , where is odd
** Beginning with , would be
** Increasing , we see that and , since
* Step 2: Choose , . We will choose .
* Step 3: Calculate , i.e. . Since it isn't congruent to , we continue to test

1.Previous
3.Next