Ймовірнісній тест Соловай-Штрасена

Тест Соловай-Штрасена базується на критерії Ейлера: якщо п − просте, то для всіх значень а, для яких НСД (a, n)=1

Нехай п – непарне складене число, а − ціле чи­сло, 1 ≤ а ≤ п - 1.

1. Якщо НСД(а, п) > 1 або , то число а називається свідком Ейлера (свідком складеності) для п.

2. Якщо НСД(a,n) = 1 та , то число n називається псевдопростим за осно­вою а. Число а називається брехунцем Ейлера (брехунцем простоти) для п. Кількість брехунців Ейлера для числа n будемо позначати через еl(n) (Euler liars).

АЛГОРИТМ

Вхід: непарне ціле число п ≥ 3, параметр t ≥ 1.

Вихід: визначення, чи є число п простим.

1. for і ← 1 tо t do

1. Обрати довільне ціле а, 2 ≤ а ≤ п-2.

2. Обчислити k← .

3. if k ≠ 1and k ≠ n-1 then return («складене»).

4. Обчислити символ Якобі .

5. if k ≠ j(mod n) then return («складене»).

2. return («просте»).

3. Yandex.RTB R-A-252273-3
   Содержание

   • Тема 5. Прості числа. Тестування числа на простоту
   • Означення простого числа
   • Утворення послідовності простих чисел
   • Тестування числа на простоту, ймовірнісні тести
   • Ймовірнісний тест на простоту Ферма
   • Ймовірнісній тест Соловай-Штрасена
   • Ймовірнісний тест Мілера-Рабіна
   • Властивості брехунців

   Yandex.RTB R-A-252273-4