тести простоти
Примітка: у всіх формулахn позначає перевіряється число.
-
перебір дільників. достатньо поділити
n на всі прості числа від 2 до округленого значення (
).
-
Мала теорема Ферма. попередження: іноді тест помилково ідентифікує складові числа як прості, навіть для всіх величин A.
- виберемо ціле число a, таке що 2 ≤ a ≤ n - 1.
- Якщо an (mod n) = a (mod n), то число, ймовірно, просте. Якщо рівність не виконується, число n є складовим.
- перевірте дану рівність для декількох значень a, щоб збільшити ймовірність того, що перевіряється число дійсно є простим.
-
Тест Міллера-Рабіна. попередження: іноді, хоча і рідко, для декількох значень a тест помилково ідентифікує складові числа як прості.
- знайдіть величини s і d, такі щоб .
- виберіть ціле число a в інтервалі 2 ≤ a ≤ n - 1.
- Якщо ad = +1 (mod n) або -1 (mod n), то n, ймовірно, є простим числом. У цьому випадку перейдіть до результату тесту. Якщо рівність не виконується, перейдіть до наступного кроку.
- зведіть відповідь у квадрат (). Якщо вийде -1 (mod n), то n, ймовірно, просте число. У цьому випадку перейдіть до результату тесту. Якщо рівність не виконується, повторіть ( і так далі) до .
- Якщо на якомусь кроці після зведення в квадрат числа, відмінного від (mod n), у вас вийшло +1 (mod n), n значить є складеним числом. Якщо (mod n), то n не є простим числом.
- результат тесту: якщо n пройшло тест, повторіть його для інших значеньa, щоб підвищити ступінь достовірності.