Тестування чисел на простоту. Імовірнісні та детерміновані тести. Тест на основі малої теореми Ферма

При тестуванні чисел на простоту за допомогою імовірнісного тесту, заснованого на малій теоремі Ферма, може виникнути ситуація, коли вірогідність помилки не знижується з кількістю повторень тесту.

В цьому випадку вона рівна одиниці і в результаті тестування може бути прийнято невірне рішення. В зв'язку з цим розроблені і застосовуються на практиці імовірнісні тести, вільні від вказаного недоліку.

Імовірнісний тест Соловея-Штрассена використовує критерій Ейлера для визначення значення символу Лежандра: .

Основою тесту є наступне твердження.

Теорема. Непарне ціле число є простим тоді і тільки тоді, коли для всіх чисел : виконується нерівність вигляду .

Назвемо вказану нерівність співвідношенням Ейлера.

У цьому співвідношенні ліва частина обчислюється безпосередньо, а права частина – за правилами обчислення символу Якобі, який співпадає з символом Лежандра, якщо число n є простим.

Число n, що задовольняє співвідношенню Ейлера, називається Ейлеровим| псевдопростим з основою . Відомо, що ейлерові| псевдопрості є псевдопростими числами.

З теореми випливає, що складених чисел, які були б ейлеровими| псевдопростими з будь-якою основою, не існує.

Тест Соловея-Штрассена аналогічний тесту Ферма.

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

Якщо ми могли б перевірити співвідношення Ейлера для всіх , то ми змогли б точно визначити, чи є число простим. Але для великих це неможливо. Тому необхідно оцінити, як поводиться вірогідність помилки, при збільшенні числа повторень тесту.

Виявляється, при повторенні тесту Соловея-Штрассена разів, вірогідність неотбраковки| складеного числа .

Поиск по сайту: