Як запустити тест Ферма на первинність менше ніж за 3 хвилини

Тест Ферма базується на результатах теорії чисел, відомих як маленька теорема Ферма.

Згідно з малою теоремою Ферма, якщо n - просте число, а d - будь-яке додатне ціле число, менше n , то d, підняте до n-ї степені, відповідає d за модулем n .

Якщо два числа мають однаковий залишок при діленні на n, тоді вони називаються конгруентними за модулем n . d за модулем n - це просто залишок від числа d, поділений на n .

Наприклад, 34 співпадає з 16 (за модулем 3) як

34 за модулем 3 = 1 і 16 за модулем 3 = 1.

Тест Ферма на первинність

  1. Для даного числа n виберіть випадкове додатне число d таке, що d < ; n.
  2. Обчислити (d ^ n) за модулем n .
  3. d за модулем n завжди буде d, оскільки ми завжди вибираємо d, що задовольняє умові d < ; n.
  4. Якщо результат (d ^ n) за модулем n не дорівнює d , то d , звичайно, не є простим.
  5. Якщо результат (d ^ n) за модулем n дорівнює d , то великі шанси, що n є простим.
  6. Виберіть інший випадковий d, який задовольняє умові d < n, і повторіть наведені вище кроки.

Примітка : У прикладах цього допису використовується Swift 4.1

Нам потрібна функція для обчислення експоненції числа за модулем іншого числа.

Ми використовуємо модульне підрахування ступеня для обчислення значень, коли показник ступеня більше 1, оскільки це дозволяє нам виконувати обчислення, маючи справу лише з числами менше n ( за модулем у наведеній вище функції).

Тест Ферма вибирає випадковим чином число d від 1 до n-1 ( число - 1 у наведеній вище функції) включно. Мета полягає в тому, щоб перевірити, чи дорівнює залишок за модулем n-ї степені d d.

Проводиться тест Ферма для зазначеного підрахунку. Якщо число не відповідає тесту Ферма, ми запевняємо, що воно не є простим. Якщо число проходить тест Ферма, воно не гарантовано буде простим. Ми намагаємось зменшити ймовірність помилки в нашому тесті на первинність, запускаючи тест достатньо разів.

Випробовуючи все більше і більше значень d (випадкове позитивне число від 1 до n-1), ми можемо збільшити нашу впевненість у результаті.