МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ТЕСТУВАННЯ ЧИСЕЛ НА ПРОСТОТУ ТА ПОБУДОВА ДОВГИХ ПРОСТИХ ЧИСЕЛ. ФАКТОРИЗАЦІЯ СКЛАДЕНИХ ЧИСЕЛ.
МЕТОДИЧНІ ВКАЗІВКИ ДО ЛАБОРАТОРНОЇ РОБОТИ № 3
З ДИСЦИПЛІНИ “АЛГОРИТМІЧНІ ОСНОВИ КРИПТОЛОГІЇ”
для студентів базових напрямів
6.170101 “Безпека інформаційних і комунікаційних систем”,
6.170102 “Системи технічного захисту інформації”,
6.170103 “Управління інформаційною безпекою”
Затверджено на засiданнi кафедри “Захист інформації”,
протокол № від 2008 р.
Львів – 2008
Тестування чисел на простоту та побудова довгих простих чисел. Факторизація складених чисел: Методичні вказівки до лабораторної роботи №3 з дисципліни “Алгоритмічні основи криптології” для студентів базових напрямів 6.170101 “Безпека інформаційних і комунікаційних систем”, 6.170102 “Системи технічного захисту інформації”, 6.170103 “Управління інформаційною безпекою” /Укл.: А.Е.Лагун, В.М.Іванюк - Львів: НУЛП 2008. - 00 с.
Укладачі: А.Е.Лагун, к.т.н., доцент
В.М.Іванюк, асистент
Відповідальний за випуск:
І.Я. Тишик, старший викладач.
Рецензент: В.В.Максимович, д.т.н., професор.
ЛАБОРАТОРНА РОБОТА №3
І. Тестування чисел на простоту і побудова великих простих чисел
Мета роботи
Засвоїти основні програмні методи тестування чисел на простоту.
Вказівки до роботи
Ознайомитися з лекційним матеріалом, а також з літературою [2], [8], [14] – [16], [18].
6.1. Метод пробних ділень
Якщо - складне, тоді , де причому . Тому для ми перевіряємо чи ділиться на ? Якщо дільник числа не буде знайдений, тоді – просте. В іншому випадку буде знайдено мінімальний простий дільник числа , тобто ми навіть розкладемо на два множника. Складність методу складає арифметичних операцій з цілими числами.
Можливі модифікації цього методу. Наприклад, ми можемо перевірити чи ділиться на 2 і на 3, і якщо ні, то перебираємо далі тільки числа виду .
6.2. Решето Ератосфена
Якщо ми хочемо скласти таблицю всіх простих чисел серед чисел 2, 3, ..., тоді необхідно спочатку викреслити всі числа, які діляться на 2, крім 2. Потім взяти число 3 і викреслити всі наступні числа, які діляться на 3. Потім взяти наступне не викреслене число (тобто 5) і викреслити всі наступні числа, які діляться на нього і так далі. В результаті залишаться лише прості числа.
Для реалізації методу необхідний великий об’єм пам’яті ЕОМ, але для складання таблиць простих чисел він є найкращим.
Всього необхідно арифметичних операцій.
6.3. Критерій Вільсона
Теорема 1.
Для будь-якого наступні умови еквівалентні:
– просте;
Даний критерій інколи буває зручним в доказах, але застосовувати його для перевірки простоти неможливо через складність.
6.4. Тест на основі малої теореми Ферма
Мала теорема Ферма стверджує, що якщо – просте, тоді виконується умова: можливе порівняння:
(1)
Обернене твердження хибне.
З цієї теореми випливає, що якщо (1) не виконалося хоча б для одного числа а в інтервалі , тоді – складне. Тому можна запропонувати наступний ймовірнісний тест простоти:
Вибираємо випадкове число з інтервалу і перевіряємо за допомогою алгоритму Евкліда умову .
Перевіряємо виконуваність порівняння .
Якщо порівняння (1) не виконано, то відповідь - складне.
Якщо порівняння (1) виконано, тоді відповідь невідома, але можна повторити тест ще раз.
Якщо виконується порівняння (1), то говорять, що число є псевдопростим відносно . Відзначимо, що існує безкінечно багато пар чисел , де - складне і псевдопросте відносно . Наприклад, при отримуємо , хоча .
Особливий випадок складають складні числа, для яких умова порівняння виконується при всіх основах. Вони називаються псевдопростими числами, або числами Кармайкла.
Таким чином, при застосуванні описаного вище тесту може виникнути три ситуації:
число просте і тест завжди говорить «не відомо»;
число складне і не є числом Кармайкла; тоді з ймовірністю успіху не менше тест дає відповідь « - складне»;
число складне і є числом Кармайкла, тоді тест завжди дає відповідь «не відомо».
Числа Кармайкла є достатньо рідкісними. Так, існує всього 2163 числа Кармайкла, що не перевищують . До числами Кармайкла є тільки наступні 16 чисел: 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973 та 75361. Перевірка того чи є задане число числом Кармайкла вимагає знаходження розкладу числа на прості співмножники, тобто факторизації числа. Оскільки факторизація чисел є більш складною ніж задача перевірки простоти, то попередня відбраківка чисел Кармайкла не є можливою. Тому в наведеному вище тесті прості числа і числа Кармайкла повністю нерозрізнені.
6.5. Тест Соловея-Штрассена
Теорема 2.
Для будь-якого непарного наступні умови еквівалентні:
- просте;
:
(2)
де – символ Лежандра.
Р. Соловей та В. Штрассен запропонували наступний ймовірнісний тест для перевірки простоти чисел:
Вибираємо випадкове число з інтервалу і перевіряємо за допомогою алгоритму Евкліда умову .
Якщо вона не виконується, тоді – складне.
Перевіряємо виконуваність порівняння (2).
Якщо воно не виконується, тоді – складне.
Якщо порівняння виконано, тоді відповідь невідома (і тест можна повторити ще раз).
Складність даного тесту, як і тесту на основі малої теореми Ферма, оцінюється величиною .
Даний тест повністю аналогічний тесту на основі малої теореми Ферма, але він володіє вагомою перевагою – при його використанні виникає лише дві ситуації:
число просте і тест завжди говорить «не відомо»;
число складне і тест з ймовірністю успіху не менше дає відповідь « - складне».
Після повторення тесту разів ймовірність невідбраківки складного числа не перевищує .
6.6. Тест Леманна
Далі наведена послідовність дій при перевірці простоти числа :
Вибрати випадково число , менше за .
Обрахувати .
Якщо (або або), тоді не є простим.
Якщо (або або), тоді ймовірність того, що число не є простим не перевищує .
Повторіть цю перевірку разів. Якщо результат обрахунків дорівнює 1 або -1, але не завжди дорівнює 1, тоді є простим числом з ймовірністю помилки .
6.7. Тест Рабіна-Міллера
Нехай – непарне і , - непарне. Якщо число є простим, тоді при всіх виконується порівняння . Тому, розглядаючи елементи можна помітити, що серед них знайдеться або рівний - , або .
На цьому зауваженні базується наступний ймовірнісний тест простоти:
Вибираємо випадкове число із інтервалу і перевіряємо за допомогою алгоритму Евкліда умову .
Якщо вона не виконується, тоді відповідь « - складне».
Обраховуємо .
Якщо , тоді переходимо до кроку 1.
Обраховуємо до тих пір, поки не з’явиться -1.
Якщо жодне з цих чисел не дорівнює -1, тоді відповіді « - складне»;
Якщо ми досягли , тоді відповідь невідома (і тест можна повторити ще раз).
Арифметична складність даного тесту, відповідно, складає .
Після повторення даного тесту разів ймовірність невідбраківки складного числа не перевищує .
Тест Рабіна-Міллера завжди сильніший за тест Соловея-Штрассена. Точніше, якщо при фіксованому число проходить тест Рабіна-Міллера і не показує, що складне, тоді воно проходить тест Соловея-Штрассена з тим самим результатом.
6.8. Поліноміальний тест розпізнавання простоти
Даний алгоритм базується на наступному критерії простоти.
Теорема 3.
Нехай числа взаємно прості. Число – просте тоді і тільки тоді, коли виконане порівняння:
(3)
Наведемо сам алгоритм.
Вхід: ціле .
Якщо число має вигляд , тоді відповідь « - складне».
Цикл поки :
Якщо , тоді « - складне»
Якщо – просте, тоді обрахувати – найбільший простий дільник ; якщо і , тоді вийти із циклу.
.
Завершити цикл.
Якщо , тоді відповідь « - складне».
Якщо , тоді перевірити виконання умови .
Якщо , тоді перевірити виконання умови .
Якщо на кроці 9-10 порушилися рівності, тоді відповідь « - складне».
Якщо ми дійшли до цього кроку, тоді відповідь « - просте».
6.9. Тест Конягіна-Померанса
Якщо для відомо повний розклад на прості множники або достатньо велика частина цього розкладу, тоді можна з поліноміальною складністю перевірити, просте чи складне.
Алгоритм перевірки простоти числа:
Заготовляємо таблицю для всіх простих чисел, що не перевищують . здійснюємо 2 етап (2-7 кроки), поки не доведемо, що – просте або, що – складне число.
Якщо – складне (див. таблицю 1 етапу), тоді і йдемо до кроку 7.
Якщо – просте і , тоді і йдемо до кроку 7. В іншому випадку перевіряємо чи виконується порівняння: . Якщо ні, тоді – складне.
Використовуючи розклад на прості співмножники, знайти порядок числа , тобто найменше натуральне число , таке, що .
Перевіряємо чи виконується умова:
Якщо вона не виконується, тоді – складне.
Якщо , тоді – просте.
Якщо , тоді повертаємося до початку виконання 2 етапу (2 крок) для наступного значення . Якщо ж , тоді – складне.
Алгоритм знаходження порядку елементу.
На вході алгоритму задані – розклад на прості множники; на виході порядок .
.
Цикл. перевірити чи виконане порівняння: . Якщо так, тоді перейти до кроку 4. В іншому випадку перейти до наступного значення в циклі.
Якщо , тоді повернутися на 2 крок; інакше видати .
6.10. Метод Міхалеску
Даний метод є алгоритмом генерації доказово простих чисел.
Алгоритм генерації доказово простих –розрядних чисел полягає в наступному. Нехай – ціле число і – дійсні константи.
Якщо , тоді алгоритм повертає випадкове просте число з двійковими розрядами (породжене за допомогою пробних ділень).
Будуємо за допомогою рекурсії ціле число із інтервалу , факторизація якого повністю відома, де можна покласти або в залежності від використовуваної достатньої умови простоти.
Вибираємо випадкове число .
Шукаємо просте число в арифметичній прогресії
.
Тест простоти, що застосовується на кроці 4, виконується в 2 етапи.
Етап 1. Пробні ділення на прості числа, що не перевищують , де – задана верхня межа.
Етап 2. Перевірка простоти за допомогою тесту Рабіна-Міллера.
Завдання
Реалізувати додаток, який дає можливість генерувати просте число за наступною схемою (з використанням, наприклад, тесту Рабіна-Міллера):
Згенеруйте випадкове –бітове число .
Встановіть старший та молодші біти рівними 1. (Старший біт гарантує необхідну довжину простого числа, а молодший біт забезпечує його непарність).
Переконайтесь, що не ділиться на невеликі прості числа: 3, 5, 7, 11 тощо. В багатьох реалізаціях перевіряється ділимість на всі прості числа менші 256. Найбільш ефективною є перевірка на ділимість для всіх простих чисел менших 2000.
Всі прості числа, що не перевищують 256 перераховані нижче:
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251.
Виконайте один тест Рабіна-Міллера перевірки простоти числа для деякого випадкового . Якщо проходить тест, згенеруйте інше випадкове і повторіть перевірку. Обирайте невеликі значення для пришвидшення обчислень. Виконайте п’ять тестів. (Одного може бути достатньо, але виконайте п’ять). Якщо не проходить одної з перевірок, згенеруйте інше і спробуйте знову.
Можна не генерувати випадковим чином кожен раз, але послідовно перебирати числа, починаючи з випадково обраного до тих пір, поки не буде знайдено просте число.
Етап (3) не є обов’язковим, але це є хороша ідея. Перевірка, що випадкове непарне не ділиться на 3, 5 і 7 відсікає 54 процента непарних чисел ще до етапу (4). Перевірка ділимості на всі прості числа, що менші 100, забирає 76 процентів непарних чисел, перевірка ділимості на всі прості числа, що менші за 256, забирає 80 процентів непарних чисел. В загальному випадку доля непарних кандидатів, які не діляться ні на одне просте число, менша , рівна .
Замість тесту Рабіна-Міллера необхідно використовувати тест, заданий у варіанті.
В звіті обов’язково повинні бути тести, що підтверджують правильність розроблених програм.
Варіант
Алгоритм
Доповнення
Тест Соловея-Штрассена
Тест Леманна
Поліноміальний тест розпізнавання простоти
Тест Рабіна-Міллера
Метод Міхалеску
Тест Леманна
Метод Міхалеску
Тест на основі малої теореми Ферма
Тест Рабіна-Міллера
Метод Міхалеску
Поліноміальний тест розпізнавання простоти
Тест Рабіна-Міллера
Тест Соловея-Штрассена
Критерій Вільсона + Решето Ератосфена
Поліноміальний тест розпізнавання простоти
Контрольні запитання
Прості числа.
Метод пробних ділень 45.
Решето Ератосфена.
Критерій Вільсона.
Тест на основі малої теореми Ферма.
Тест Соловея-Штрассена.
Тест Леманна.
Тест Рабіна-Міллера.
Поліноміальний тест розпізнавання простоти.
Тест Конягіна-Померанса.
Метод Міхалеску.
Вирішити порівняння першого степеня використовуючи:
Алгоритм Евкліда;
Розширений алгоритм Евкліда;
Метод Ейлера (якщо можливо).
Порівняння:
;
;
;
;
;
.
Навести всі кроки алгоритму. Перевірити результат (підставити знайдений розв’язок в порівняння).
ІІ. Факторизація складених чисел
Мета роботи:
Освоїти прості алгоритми факторизації складного числа.
Вказівка до роботи
Ознайомитися з лекційним матеріалом, а також з літературою [2], [14] - [18]. Для криптографічного розтину алгоритму шифрування RSA1 досить розкласти частину відкритого ключа на прості множники, тому завдання факторизації складного числа придбало велике практичне значення. Дане завдання зворотне до завдання визначення простоти конкретного числа, але набагато складніше. Далі представлені найбільш прості методи факторизації складного числа.
7.1. Метод Ферма.
Даний метод заснований на пошуку чисел х і у, таких, що х2≡у2(mod n), де n треба розкласти на множники.
Теорема 1 (Ейлера про представлення числа у вигляді різниці квадратів). Якщо – n>1 непарне, то існує взаємно однозначна відповідність між розкладом на множники n = a*b і представленням у вигляді різниці квадратів n= х2 - у2, x > y > 0. Тут ,, x= 2 , a=x+y, b=x-y.
Метод Ферма полягає в тому, що при малих значеннях параметра y в представленні n= х2 - у2 можна знайти пару(x,y) перебираючи в якості кандидатів на значення x числа , , … і перевіряючи для кожного з них рівність
Алгоритм факторизації методом Ферма:
Вхід: n - непарне число, p1……pk- невеликі прості числа.
Перевірити чи ділять без остачі pi, i= число . Якщо так, то дільник знайдений.
[ +1; +n0] обчислити величини tx2-n, tit mod pi, i=.
3. Якщо хоч би для одного i= виконана одна з умов:
ti=0 і pi2 не ділить t
ti0 і то перейти до наступного x на кроці 2. Інакше перейти до кроку 4.
4. Перевірити, чи tx2-n є повним квадратом. Якщо = х2 - n = у2 тo n - складене; ; якщо tx2-n не повний квадрат, то перейти до наступного x на кроці 2.
Інший варіант методу Ферма запропонував Кнут (без операцій ділення).
Хай n=UV де UV
Допустимо, що n - непарне, тоді U,V теж непарні. Тому можна постановити , ; n= х2 - у2, 0 y - x n.
Метод Ферма полягає в пошуку x,y що задовольняє цим співвідношенням. Тоді n=(x-y)(x+y).
Наступний алгоритм показує, як, не виконуючи операцій ділення, можна реалізувати метод Ферма:
1. x'2+1; y'1; r2-n, під час роботи алгоритму x',y',r відповідають відповідно 2x-1.2y+1, х2 + у2-n
2. Якщо r0, то перейти в крок (4)
3. rr-y'; y'y'+2 і повернутися на крок (2).
4. Якщо r=2, то кінець циклу: маємо і значення є найбільшим множником числа m.
5. rr+x'; x'x'+2 і повернутися на крок (3).
Число кроків, що виконуються у цьому алгоритмі для знаходження U,V
пропорційно .
Метод Ферма ефективний, якщо дільники n близькі один до одного. Даний метод є, по суті, методом перебору, тобто неефективним.
7.2. (p-1 ) - факторизація Полларда.
Припустимо, що n - непарне складене число, що не має невеликих простих дільників. Позначимо через p найменший простий дільник числа n. Наше завдання полягає в його знаходженні.
Припустимо, що число (p-1) розкладається в добуток невеликих простих дільників. Виберемо число k, яке є параметром методу. Для успішної роботи алгоритму потрібно, щоб виконувалася умова (p-1 ) ділить M(k), де M(k)=HСД(1,2,…,k)(замість M(k), наприклад, можна використовувати k! ).
В силу малої теореми Ферма виконується порівняння 2M(k)1(mod p). Якщо при цьому 2M(k) 1(mod n),то p ділить HСД(2M(k)-1,n) де p>1, HСД(2M(k)-1,n)<n
Таким чином HСД(2M(k)-1,n), є дільником числа n, кратним p.
Оскільки число невідоме, то воно шукається в алгоритмі перебором.
Алгоритм методу факторизації (p-1 ) - факторизація Полларда:
Нехай k - ціле число, наприклад k<106, і - невелике ціле з умовою HСД(c,n)=1, наприклад, c=2 .
1. = обчислюється micМ(i)mod n і перевіряється тест кроку (2).
2. Обчислити dHСД (mі-1,n). Якщо 1<d<n то знайдений нетривіальний дільник числа n. Інакше вважаємо ii+1.
Оцінка складності даного методу у гіршому разі складає O(n1/2 logconst n) арифметичних операцій. Проте в деяких випадках алгоритм може швидко видати дільника числа n.
На практиці (p-1) метод Полларда зазвичай використовують до застосування сильніших алгоритмів факторизації для того, щоб відокремити невеликих простих дільників числа n.
7.3. Метод ρ -Полларда.
Далі приведений алгоритм цього методу:
1. Вибираємо випадковим чином xi з множини {0,1,…,n-1}; xx1; k2.
2. ii+1 і обчислюємо наступний елемент послідовності
xif(xi-1)mod n.
3. Якщо dHСД(y- xi, n): d1 і dn то d дільник n, цикл завершений.
4. Якщо i рівне k, то y xi, k2k.
Можливо, що цикл значень по модулю n виявиться більшим ніж . Метод має евристичну оцінку складності O(n1/4)арифметичних операцій. Він дуже популярний і зазвичай використовується для відділення невеликих простих дільників факторизованого числа n.
Основна ідея даного методу дуже проста. Якщо період послідовності ximod n може бути порядку n, то період послідовності ximod p для простого дільника p числа n не перевершує p. Це означає, що y і xi можуть бути різними по модулю n, але співпадати по модулю p.
Існує константа, така, що для будь-якого>0 імовірність не знайти нетривіального дільника n за clog3n бітових операцій буде менше, ніж e .
7.4. Метод Шермана-Лемана.
Нехай n непарне, n>8.
1. Для a=2,3,…,[n1/3] перевірити, що a ділить n. Якщо на цьому кроці ми не розклали n на множники, то переходимо до кроку 2.
2. Якщо на 1 кроці дільник не знайдений і n складене, то n=pq де p,q -прості числа, і n1/3<pq<n2/3.
Тоді для всіх k=1,2,…,[n1/3] і всіх d=0,2,…, +1 перевірити, чи є число квадратом натурального числа. Якщо є, то для і виконано порівняння .
В цьому випадку перевірити умову . Якщо ця умова виконана, то ми розклали n на два множника і алгоритм зупиняється. Якщо даний алгоритм не знайшов розкладу n на два множники, то n - просте число. Даний алгоритм розкладає n на множники за O(n1/3) арифметичних операцій.
7.5. Метод Ленстри.
Теорема 2.
Нехай r,s,n - натуральні числа, що задовольняють умовам .
Тоді існує не більше 11 дільників ri числа n таких, що Існує алгоритм, який знаходить всі ці ri за O(logn) арифметичних операцій.
Алгоритм методу факторизації Ленстри:
На вході задані числа , що задовольняють умовам теореми.
1. За допомогою узагальненого алгоритму Евкліда знайти . Знайти r' таке, що .
2. Для чергового значення i=0,1,… знайти числа по наступних правилах:
де
3. Для чергового набору знайти всі цілі числа с, що задовольняють умовам:
Таких с буде не більш двох.
4. Для кожного c із кроку 3 вирішити в цілих числах систему рівнянь
Якщо x і y виявляться ненегативними цілими числами, то додати (xs+r) до списку шуканих дільників.
5. Якщо ai=0, то алгоритм закінчує роботу. Інакше повертаємося на крок 2 до наступного значення ii+1 .
Завдання
1. Реалізувати програму, що дозволяє знаходити розкладання на множники заданого числа n:
a) методом пробних ділень;
b) згідно заданого варіанту;
c) комбінованим методом: на першому етапі методом пробних ділень перевіряється розкладність n; якщо n пройшло цей тест, то на другому етапі застосовуйте заданий у варіанті алгоритм.
Сліду зважати на те, що всі представлені методи шукають тільки один дільник n . Таким чином необхідно застосовувати метод кілька разів, поки не вийде повний розклад числа на множники.
2. Приступаючи до факторизації числа, слід спочатку переконатися, що воно не просте. Це треба зробити за допомогою програм, написаних під час лабораторної роботи №6. Трудомісткість тестів простоти, як правило, значно менше, ніж у алгоритмів факторизації. Парне число теж не слідує факторизувати.
3. Порівняти два реалізовані методи за часом розкладу досить великого n (наприклад, з 15-ма десятковими розрядами).
Знайти максимальне число операцій, за яке відбудеться повний розклад числа (теоретично). Отримані результати порівняти з числом операції алгоритму факторизації (решето числового поля):
, де .
4. У методі пробних ділень обмежиться діленням на прості числа, приведені далі:
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,19,193,197,199,211,223,227,229,233,239,241,251.
5. У звіті обов'язково повинні бути присутніми тести, підтверджуючі правильність розроблених програм.
Варіант
Алгоритм факторизації
Доповнення
1
Метод ρ-Поларда
2
Метод Ферма (без операцій ділення)
3
(p-1) - факторизація Поларда
4
Метод ρ -Поларда
5
Метод Ферма
6
Метод Шермана-Лемана
7
Метод Ферма (без операцій ділення)
8
Метод Ферма
9
Метод ρ -Поларда
10
Метод Ферма (без операцій ділення)
11
Метод Шермана-Лемана
12
Метод Ленстри
13
(p-1) - факторизація Поларда
14
Метод Ферма
15
Метод Ленстри
Контрольні питання
1. Метод факторизації Ферма.
2. Метод факторизації -Полларда.
3. (p-1)- факторизація Полларда.
4. Метод Шермана-Лемана.
5. Метод Ленстри.
6. Знайти все первісні корені, менші m :
1. m=5 9. m=31
2. m=7 10. m=37
3. m=11 11. m=41
4. m=13 12. m=43
5. m=17 13. m=47
6. m=19 14. m=53
7. m=23 15. m=57
8. m=29 16. m=59
7. Вирішити задачу дискретного логарифма методом:
a) Перебору;
b) По формулі ;
c) Узгодження.
Завдання:
1.
2.
3.
4.
5.
Привести всі кроки алгоритму. Перевірити результат (підставити знайдене рішення в порівняння).