| Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3). |
Navigation
| Topics | Help • Register • News • History • How to • Sequences statistics • Template prototypes |
Difference between revisions of "Lucas primality test"
(restored) |
(Adding to new subcategory) |
||
| (One intermediate revision by one other user not shown) | |||
| Line 1: | Line 1: | ||
| − | The '''Lucas primality test''' invented in 1891 by [[ | + | The '''Lucas primality test''' invented in 1891 by [[Édouard Lucas]], determines whether a number N is prime or not, using the complete factorization of N-1. |
If, for some integer b, the quantity b<sup>N-1</sup> is congruent to 1 modulo N, and if b<sup>(N-1)/q</sup> is not congruent to 1 modulo N for any prime divisor q of N-1, then N is a prime. | If, for some integer b, the quantity b<sup>N-1</sup> is congruent to 1 modulo N, and if b<sup>(N-1)/q</sup> is not congruent to 1 modulo N for any prime divisor q of N-1, then N is a prime. | ||
| Line 20: | Line 20: | ||
==External links== | ==External links== | ||
| − | *[ | + | *[[wikipedia:Lucas primality test|Wikipedia]] |
| − | [[Category: | + | |
| + | [[Category:Deterministic primality tests]] | ||
Latest revision as of 01:13, 11 August 2024
The Lucas primality test invented in 1891 by Édouard Lucas, determines whether a number N is prime or not, using the complete factorization of N-1.
If, for some integer b, the quantity bN-1 is congruent to 1 modulo N, and if b(N-1)/q is not congruent to 1 modulo N for any prime divisor q of N-1, then N is a prime.
Example
Prove that N = 811 is prime knowing that N-1 = 2 × 34 × 5
Let's start with b = 3.
- [math]\displaystyle{ 3^{810/2}\,= \,3^{405}\,\equiv \, 810\,\pmod{811} }[/math]
- [math]\displaystyle{ 3^{810/3}\,= \,3^{270}\,\equiv \, 680\,\pmod{811} }[/math]
- [math]\displaystyle{ 3^{810/5}\,= \,3^{162}\,\equiv \, 212\,\pmod{811} }[/math]
- [math]\displaystyle{ 3^{810}\,\equiv \, 1\,\pmod{811} }[/math]
All conditions of the test hold so 811 is prime.
The fourth computation is not needed: compute b(N-1)/2 as done in the example, if it is congruent to 1, the value b must be changed, if it is congruent to N-1, the first condition of the test holds, otherwise N is composite.
Notice the b = 7 is a bad choice because:
- [math]\displaystyle{ 7^{810/2}\,= \,7^{405}\,\equiv \, 1\,\pmod{811} }[/math]
