Тест Лукаса на первичность
- Тест Лукаса — тест на простоту для натурального числа n, основанный на известных простых множителях n — 1.
- Если существует целое число a, 1 < a < n, такое, что и для каждого простого множителя q из n − 1, то n — простое число.
- Если такого числа a не существует, то n равно либо 1, либо 2, либо составному числу.
- Если n является простым, то существует примитивный корень по модулю n, или генератор группы (Z/nZ)*.
- Если существует a < n, такое, что первая эквивалентность не выполняется, a называется свидетелем Ферма для составности n.
- Алгоритм теста Лукаса может быть записан в псевдокоде.
Полный текст статьи: