НОУ ІНТУЇТ | лекція | Алгоритми тестування на простоту і факторизации

1. 2.1 Тестування на простоту
2. 2.1.1 Імовірнісні тести простоти
3. 2.1.2 Тест Ферма
4. 2.1.3 Тест Леманна
5. 2.1.4 Тест Соловея-Штрассена
6. 2.1.5 Тест Міллера-Рабіна
7. 2.1.6 N - 1-алгоритми генерації простих чисел

Анотація: Для побудови багатьох систем захисту інформації потрібні прості числа великої розрядності. У зв'язку з цим актуальною є задача тестування на простоту натуральних чисел. У лекції 2 розглядаються тести техніка комп'ютерних обчислень з багаторозрядних числами.

Визначення 2.1 Час роботи алгоритму має верхню оцінку (пишуть , Читають "Про велике від від "), Якщо існує натуральне число і позитивна постійна такі, що виконується нерівність: .

Приклад 2.1 Доведемо, що функція має верхню оцінку .

Дійсно, покладемо , . тоді виконується нерівність . отже, .

Оцінка складності алгоритму - найважливіше питання для криптографії, оскільки від оцінки складності вирішальним чином залежить стійкість відповідної криптосистеми.

Далі ми будемо розглядати алгоритми (в основному теоретико-числові) і в більшості випадків будемо приводити оцінку складності представленого алгоритму.

2.1 Тестування на простоту

Існує два типи критеріїв простоти: детерміновані і імовірнісні. Детерміновані тести дозволяють довести, що тестоване число - просте. Практично застосовні детерміновані тести здатні дати позитивну відповідь не для кожного простого числа, оскільки використовують лише достатні умови простоти.

Детерміновані тести більш корисні, коли необхідно побудувати велике просте число, а не перевірити простоту, скажімо, деякого однини.

На відміну від детермінованих, імовірнісні тести можна ефективно використовувати для тестування окремих чисел, однак їх результати, з певною ймовірністю, можуть бути невірними. На щастя, ціною кількості повторень тесту з модифікованими вихідними даними ймовірність помилки можна зробити як завгодно малою.

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

На практиці розглянуті алгоритми найчастіше окремо не застосовуються. Щоб перевірити, скільки на простоту використовують або їх комбінації, або детерміновані тести на простоту.

Детермінований алгоритм завжди діє за однією і тією ж схемою і гарантовано вирішує поставлене завдання. Імовірнісний алгоритм використовує генератор випадкових чисел і дає не гарантовано точну відповідь. Імовірнісні алгоритми в загальному випадку не менш ефективні, ніж детерміновані (якщо використовується генератор випадкових чисел завжди дає набір одних і тих же чисел, можливо, залежать від вхідних даних, то імовірнісний алгоритм стає детермінованим).

2.1.1 Імовірнісні тести простоти

Для того щоб перевірити імовірнісним алгоритмом, чи є ціле число простим, вибирають випадкове число , , І перевіряють умову алгоритму. якщо число не проходить тест на підставі , То алгоритм видає результат "Число складене ", і число дійсно є складовим.

Якщо ж проходить тест на підставі , Не можна сказати про те, чи дійсно число є простим. Послідовно провівши ряд перевірок таким тестом для різних і отримавши для кожного з них відповідь "Число , Ймовірно, просте ", можна стверджувати, що число є простим з імовірністю, близькою до 1. Якщо ймовірність того, що складене число пройде тест, дорівнює , То для забезпечення ймовірності того, що перевірене число є простим, необхідно зробити ітерацій (див. Мал. 1.1 }).

2.1.2 Тест Ферма

Відповідно до малої теореми Ферма для простого числа і довільного цілого числа , , Виконується порівняння:

Отже, якщо для непарного існує таке ціле , що , і , То число ймовірно просте. Таким чином, отримуємо наступний імовірнісний алгоритм перевірки числа на простоту:

Вхід: непарне ціле число .

Вихід: "Число , Ймовірно, просте "або" Число складене ".

1. Вибрати випадкове ціле число , .
2. обчислити .
3. при результат: "Число , Ймовірно, просте ". В іншому випадку результат:" Число складене ".

На кроці 1 алгоритму ми не розглядаємо числа і , оскільки для будь-якого цілого і для будь-якого непарного .

Складність тесту Ферма дорівнює: .

Тест має істотний недолік у вигляді наявності чисел Кармайкла. Це непарні складові числа, для яких порівняння з формули виконується при будь-якому , , Взаємно просте з . Для всіх , , Тест буде видавати помилковий результат.

Числа Кармайкла є досить рідкісними. В межах до 100000 існує лише 16 чисел Кармайкла: 561, 1105, №1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361.

2.1.3 Тест Леманна

Якщо для будь-якого цілого числа , меншого , Не виконується умова:

то число - складене. Якщо ця умова виконується, то число - можливо просте, причому ймовірність помилки не перевищує 50%.

Таким чином, отримуємо наступний імовірнісний алгоритм перевірки числа на простоту:

Вхід: непарне ціле число .

Вихід: "Число , Ймовірно, просте "або" Число складене ".

1. Вибрати випадкове ціле число , .
2. обчислити .
3. при і результат: "Число складене ". В іншому випадку результат:" Число , Ймовірно, просте ".

Складність тесту Леманна дорівнює .

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

В основі цього тесту лежить наступна теорема:

Теорема 1.28 (критерій Ейлера) Непарне число є простим тоді і тільки тоді, коли для будь-якого цілого числа , , Взаємно простого з , Виконується порівняння:

де - символ Якобі від параметрів і .

Критерій Ейлера лежить в основі наступного імовірнісного тесту числа на простоту:

Вхід: непарне ціле число .

Вихід: "Число , Ймовірно, просте "або" Число складене ".

1. Вибрати випадкове ціле число , .
2. обчислити .
3. при і результат: "Число складене ".
4. Обчислити символ Якобі .
5. при результат: "Число складене ". В іншому випадку результат:" Число , Ймовірно, просте ".

На кроці 1 ми знову не розглядаємо числа і , Оскільки в силу властивостей символу Якобі порівняння у формулі (2.1) для цих чисел виконується при будь-якій непарній . якщо , то ділить і число , Що обчислюється на кроці 2. Таким чином, при перевірці нерівності на кроці 3 автоматично перевіряється умова .

Складність тесту Соловея-Штрассена визначається складністю обчислення символу Якобі і дорівнює .

Для тесту Соловея-Штрассена не існує чисел, подібних числах Кармайкла, тобто складених чисел, які були б ейлеровимі псевдопростимі по всіх підставах .

2.1.5 Тест Міллера-Рабіна

На сьогоднішній день для перевірки чисел на простоту найчастіше використовується тест Міллера-Рабіна, заснований на наступному спостереженні. якщо - просте, і , то або .

нехай число непарне і , де - непарне. За малої теореми Ферма, якщо - просте, то для будь-якого натурального числа . З нашого спостереження випливає, що, в ряду елементів при будь-якому ми будемо мати і при .

Це властивості лежить в основі наступного тесту:

Вхід: непарне ціле число .

Вихід: "Число , Ймовірно, просте "або" Число складене ".

1. уявити у вигляді , Де число - непарне.
2. Вибрати випадкове ціле число , , Взаємно просте з .
3. обчислити .
4. при і виконати наступні дії.
5. Результат: "Число , Ймовірно, просте ".

В результаті виконання тесту для простого числа в послідовності обов'язково перед 1 повинна з'явитися (Або, що те ж саме, ). Це означає, що для простого числа єдиними рішеннями порівняння є . якщо число складене і має різних простих дільників (тобто не є ступенем простого числа), то по китайській теоремі про залишки існує рішень порівняння . Дійсно, для будь-якого простого дільника числа існує два рішення зазначеного порівняння: . Тому таких порівнянь дають наборів рішень по модулях , Що містять елементи .

Складність тесту Міллера-Рабіна дорівнює . Імовірність помилки, тобто того, що тест оголосить складене число простим, не більше .

2.1.6 N - 1-алгоритми генерації простих чисел

Перерахуємо деякі теореми, які можуть бути використані для генерації доказово простих чисел [1].

Теорема 2.1 (Прот, 1878) Нехай , де , , і поділяє . тоді - просте тоді і тільки тоді, коли

Для генерації простого числа потрібно перебирати числа і і для кожного варіанту перевіряти умова (2.2). Коли умова буде виконана, отримане число буде простим.

Недоліком цього підходу є погане розподіл генеруються простих чисел: всі вони будуть мати вигляд для великого і не дуже великого . У прикладі 1.42 ми також бачили, що чим менше прості подільники числа , Тим легше здійснити дискретне логарифмування по модулю . Це робить генеруються на основі теореми Прота прості числа мало придатними, наприклад, для криптосистеми і електронного підпису Ель-Гамаля.

Теорема 2.2 (Діемітко, 1988) Нехай , де - непарне просте число, - парне, і . Якщо існує ціле число таке, що

то просте число.

За допомогою цієї теореми генерувати прості числа можна ітераційно. На вхід кожної ітерації подається якесь просте число . Під час ітерації перебираються числа і і перевіряються умови теореми Діемітко. Як тільки всі умови виконані, ми отримали нове просте число , Порядок якого приблизно вдвічі більше, ніж у вихідного простого числа . Ітерації можна починати з будь-якого відомого простого числа, а закінчувати, коли отримане просте число досягне необхідного розміру.

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

Ця теорема лежала в основі алгоритму генерації простих чисел для алгоритму цифрового підпису ГОСТ 34.10-94, поки цей алгоритм ні замінений на новий, заснований на групі точок еліптичної кривої.