Тест Соловея — Штрассена

Немає перевірених версій цієї сторінки; ймовірно, її ще не перевіряли на відповідність правилам проекту.

Тест Соловея — Штрассена — імовірнісний тест простоти, відкритий у 1970-х роках Робертом Мартіном Соловеем спільно з Фолькером Штрассеном.^[1] Тест завжди коректно визначає, що просте число є простим, але для складених чисел з деякою ймовірністю він може дати неправильну відповідь. Основна перевага тесту полягає в тому, що він, на відміну від тесту Ферма, розпізнає числа Кармайкла як складені.

Історія

У 17 столітті Ферма довів твердження, назване пізніше малою теоремою Ферма, що слугує основою тесту Ферма на простоту:

Якщо n — просте і a не ділиться на n, то

a^{n-1}\equiv 1{\pmod {n}}

.

Ця перевірка для заданого n не вимагає великих обчислень, однак твердження, протилежне цьому, є невірним. Так, існують числа Кармайкла, які є складеними, для яких твердження, наведене в малій теоремі Ферма, виконується для всіх цілих чисел взаємнопростих з заданим числом. У 1994 році було показано, що таких чисел нескінченно багато.^[2] У зв'язку з виявленим недоліком тесту Ферма, актуальності набуло завдання збільшення достовірності ймовірнісних тестів. Першим тест, що відсіює числа Кармайкла як складені, запропонував Леманн. Цей недолік відсутній також у тестах Соловея — Штрассена і Міллера — Рабіна за рахунок більш сильного критерію відсіву, ніж мала теорема Ферма. Незалежно від один одного Д. Лемер в 1976 році і Р. Соловей спільно з Ф. Штрассеном в 1977 році довели, що аналога чисел Кармайкла, які є складеними і одночасно ейлеровими псевдопростими, немає.^[3] На основі цього і був запропонований тест Соловея — Штрассена на простоту, він був опублікований в 1977 році, доповнення до нього в 1978 році.

Обґрунтування

Тест Соловея — Штрассена спирається на малу теорему Ферма і властивості символу Якобі^[4]:

Якщо n — непарне складене число, то кількість цілих чисел a, взаємнопростих з n і менших n, що задовольняють порівнянню $\textstyle a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}$ не перевищує ${\frac {n}{2}}$ .

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

Алгоритм Соловея — Штрассена

Алгоритм Соловея — Штрассена^[5] параметризується кількістю ітерацій k. У кожній ітерації випадковим чином вибирається число a < n. Якщо НСД(a,n) > 1, то виноситься рішення, що n - складене. Інакше перевіряється справедливість порівняння $\textstyle a^{(n-1)/2}\equiv \left({a \over n}\right){\pmod {n}}$ . Якщо воно не виконується, то виноситься рішення, що n — складене. Якщо це порівняння виконується, то a є свідком простоти числа n. Далі вибирається інше випадкове a і процедура повторюється. Після знаходження k свідків простоти в k ітераціях виноситься висновок, що n є простим числом з імовірністю $\textstyle 1-2^{-k}$ .

На псевдокоді алгоритм може бути записаний наступним чином:

 Ввід:  $n$  > 2, непарне натуральне число, що тестується;
       $k$ , параметр, що визначає точність тесту.
Вивід: складене, означає, що  $n$  точно складене;
       ймовірно просте, означає, що  $n$  ймовірно є простим.

for i = 1, 2, ...,  $k$ :
    $a$  = випадкове ціле від 2 до  $n-1$ , включно;
   якщо НСД(a, n) > 1, тоді:
       вивести, що  $n$  — складене, і зупинитися.
   якщо  $a^{(n-1)/2}\not \equiv \left({a \over n}\right){\pmod {n}}$ , тоді: 
       вивести, що  $n$  — складене, і зупинитися.

інакше вивести, що  $n$  — просте  зі ймовірністю  $\textstyle 1-2^{-k}$ , і зупинитися.

Приклад застосування алгоритму

Перевіримо число n = 19 на простоту. Виберемо параметр точності k = 2.

 k = 1
 Виберемо довільне число a = 11; 2 < a < n - 1
 Перевіримо умову НСД(a,n)>1
 НСД(11,19)=1; отже, перевіряємо виконання порівняння  $\textstyle a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}$   
  $r=\left({\frac {a}{n}}\right)=\left({\frac {11}{19}}\right)=1$ 
  $\textstyle s=a^{(n-1)/2}=11^{(19-1)/2}{\pmod {19}}=1$ 
 Отримали, що  $\textstyle r=s$ , тому переходимо до наступної ітерації

 k = 2
 Виберемо довільне число a = 5; 2 < a < n - 1
 Перевіримо умову НСД(a,n)>1
 НСД(5,19)=1; отже, перевіряємо виконання порівняння  $\textstyle a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}$   
  $r=\left({\frac {a}{n}}\right)=\left({\frac {5}{19}}\right)=1$ 
  $\textstyle s=a^{(n-1)/2}=5^{(19-1)/2}{\pmod {19}}=1$ 
  $\textstyle r=s$  і це була остання ітерація, звідси робимо висновок, що 19 - просте число з імовірністю  $1-2^{-2}$

Обчислювальна складність і точність

Точність у порівнянні з іншими ймовірнісними тестами на простоту (тут k — число незалежних ітерацій)

назва тесту	ймовірність (що число складене)^[6]	примітки
Ферма	${\textstyle 2^{-k}}$	не розпізнає числа Кармайкла як складені
Леманна	$2^{-k}$
Соловея — Штрассена	$2^{-k}$

Теоретична складність обчислень всіх наведених у таблиці тестів оцінюється як $O(\log ^{3}n)$ .^[3]
Алгоритм вимагає $O(k\log _{2}m)$ операцій над довгими цілими числами.
При реалізації алгоритму, для зниження обчислювальної складності, числа a вибираються з інтервалу 0 < a < c < n, де c — константа рівна максимально можливому значенню натурального числа, що міститься в одному регістрі процесора.^[5]

Застосування

Ймовірнісні тести застосовуються в системах заснованих на проблемі факторизації, наприклад RSA або схема Рабіна. Однак на практиці ступінь достовірності тесту Соловея — Штрассена не є достатньою, замість нього використовується тест Міллера — Рабіна. Більш того, використовуються об'єднані алгоритми, наприклад пробний поділ і тест Міллера — Рабіна, при правильному виборі параметрів можна отримати кращі результати, ніж при застосуванні кожного тесту окремо.

Поліпшення тесту

У 2005 році на Міжнародній конференції Bit+ «Informational Technologies -2005» А. А. Балабанов, А. Ф. Агафонов, В. А. Рику запропонували модернізований тест Соловея — Штрассена. Тест Соловея — Штрассена заснований на обчисленні символу Якобі, що займає час, еквівалентний $\log _{2}n$ . Ідея поліпшення полягає в тому, щоб у відповідності з теоремою квадратичного закону взаємності Гаусса, перейти до обчислення величини $\left({\frac {n}{a}}\right)$ ,що є оберненою символу Якобі, що є більш простою процедурою.^[7].

Див. також

Псевдопросте число

Примітки

↑ Solovay, Robert M. and Volker Strassen (1977, submitted in 1974). A fast Monte-Carlo test for primality. SIAM Journal on Computing. 6 (1): 84—85. doi:10.1137/0206006.
↑ W. R. Alford, A. Granville, C. Pomerance (1994). There are Infinitely Many Carmichael Numbers (PDF). Annals of Mathematics. 139: 703—722. doi:10.2307/2118576.
↑ ^а ^б Черемушкин, 2001.
↑ Нестеренко, 2011.
↑ ^а ^б Нестеренко, 2011, с. 84.
↑ Б. Шнайер Прикладная криптография — М. : ТРИУМФ, 2002 . — Глава 11.
↑ Балабанов А. А.,Агафонов А. Ф.,Рыку В. А.Алгоритм быстрой генерации ключей в криптографической системе RSA. — Вестник научно-технического развития, 2009 № 7(23). — С. 11.

Література

Коблиц Н. Курс теории чисел и криптографии. — М. : Научное издательство ТВП, 2001. — С. 149 - 160. — ISBN 5-94057-103-4.
Нестеренко А. Введение в современную криптографию. Теоретико-числовые алгоритмы. — 2011. — С. 79 - 90. — ISBN 978-5-94506-320-4.
Черемушкин А. В. Лекции по арифметическим алгоритмам в криптографии. — МЦНМО. — М., 2001. — С. 42 - 59. — ISBN 5-94057-060-7.
Саломаа А. Криптография с открытым ключом / Пер. з англ. І.А. Віхлянцева. — М. : Мир, 1995. — С. 176 - 184. — ISBN 5-03-001991-X.

[sspaper-1] Solovay, Robert M. and Volker Strassen (1977, submitted in 1974). A fast Monte-Carlo test for primality. SIAM Journal on Computing. 6 (1): 84—85. doi:10.1137/0206006.

[2] W. R. Alford, A. Granville, C. Pomerance (1994). There are Infinitely Many Carmichael Numbers (PDF). Annals of Mathematics. 139: 703—722. doi:10.2307/2118576.

[FOOTNOTEЧеремушкин2001-3] а ^б Черемушкин, 2001.

[FOOTNOTEНестеренко2011-4] Нестеренко, 2011.

[FOOTNOTEНестеренко201184-5] а ^б Нестеренко, 2011, с. 84.

[шнайер-6] Б. Шнайер Прикладная криптография — М. : ТРИУМФ, 2002 . — Глава 11.

[7] Балабанов А. А.,Агафонов А. Ф.,Рыку В. А.Алгоритм быстрой генерации ключей в криптографической системе RSA. — Вестник научно-технического развития, 2009 № 7(23). — С. 11.

[1]

[2]

[3]

[4]

[5]

[6]

[7]