• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

ТЕСТ МІЛЛЕРА-РАБІНА.

Вхід: п — непарне натуральне число, п — 1 = 2^s і непарне.

· Вибрати випадкове х таке, що 1 х < п.

· Якщо НСД(x,п) 1, то зупинитись з резолюцією "п складене", інакше продовжувати.

· Обчислити y₀ = x^t (modn).

· Якщо у₀ ±1 (modn), то зупинитись з резолюцією "просте", інакше продовжувати.

· Обчислювати y_j = (modn), доки не виявиться, що y_j ±1 (mod n).

· Якщо y_j 1 (mod n), то зупинитись з резолюцією "складене", а якщо y_j —1 (mod n), то зупинитись з резолюцією "просте".

Час роботи цього тесту O(log³n). З твердження 2.3 і обговорення перед ним безпосередньо випливає, що помилка тесту однобічна, з імовірністю щонайбільше 1/4. Повторенням тесту k разів помилка зменшується до (l/4)^k. Твердження 2.2 показує, що тест Міллера-Рабіна є формальним підсиленням тесту Соловея-Штрассена із вдвічі кращою оцінкою ймовірності помилки.

2.5. Прості числа до 25 000 000 000. В [128] доведено, що серед чисел, менших від 25 • 109, лише одне є сильно псєвдопростим за кожною із чотирьох основ 2, 3, 5, 7. Цим числом є
3 215 031 751. Отже, дуже легко перевірити, чи задане число п < 25 • 10⁹ є простим. Для цього необхідно і досить, щоб п було відмінним від вказаного вище складеного числа, і щоб умова (3) виконувалась для х = 2,3,5,7.

2.6. Розширена гіпотеза Рімана. Дзета функція Рімана є функцією від комплекснозначної змінної s = + i, яка означується за допомогою ряду

Цей ряд абсолютно збігається у будь-якій області з 1, і його сума є аналітичною функцією, що аналітичне продовжується на всю комплексну площину з єдиною особливістю в точці s=l. Недоведена досі гіпотеза Рімана стверджує, що всі нулі дзета-функції в смузі 01 лежать на прямій = 1/2.

Характером групи називається довільний її гомоморфізм у мультиплікативну групу комлексних чисел С* . Кожен характер g : C* визначає функцію : NC* ,

яка називається характером Дiріхле за модулем т. Характер називається головним, якщо він приймає значення лише 0 та 1. Для характера Діріхле L-функція Дiріхле від комплексної змінної s означується як сума ряду

який збігається в області > 0 (див. [15]).

Розширена гіпотеза Рімана, для якої далі буде вживатися абревіатура РГР, стверджує, що для неголовного характеру х всі нулі функції У півшплощині > 0 знаходяться на прямій = 1/2.

За припущення справедливості РГР Міллер довів, що кожне непарне складене п принаймні для однієї основи х < 2 (ln п)² не є сильно псевдопростим числом за цією основою. Звідси негайно випливає, що за умови справедливості РГР для тестування простоти існує детермінований поліноміальний алгоритм. Цей алгоритм констатує простоту заданого непарного п в разі виконання умови (3) для всіх х < 2(lп п)². Зауважимо, що від справедливості РГР залежить не поліноміальність цього алгоритму, яка є безумовним фактом, а його коректність. Якщо РГР хибна, то не виключено, що описаний тест витримують деякі складені числа.

2.7. Виробництво простих чисел. Багато криптосистем використовують параметр, який є простим числом, причому надійність криптосистеми грунтується на тому, що цей параметр тримається від суперника в таємниці. Щоб позбавити суперника найменших шансів відгадати це просте число, останнє слід вибирати великим і випадковим. Зокрема, не слід користуватись простими числами спеціального виду на зразок простих чисел Мерсенна (див. вправу 2.7), хоча вони і приваблюють добре вивченими критеріями простоти. Вибір простих чисел гарантується в широкому асортименті оцінкою Чебишова для функції (п) та пізнішими результатами про розподіл простих чисел, цитованими у розділі 1.3.

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

Генерування випадкового простого числа заданого розміру l відбувається наступним чином. Вибирається випадкове натуральне число п між 10^l-1 і 0^l. Далі почергово перебираються числа п + 1, п + 2, п + 3 і т.д., кожне з яких випробовується тестом простоти. Зауважимо, що числа, кратні кільком першим простим, вигідніше відкидати негайно, а не в результаті тестування (за ознаками подільності на 2, 3, 5, 7, 11, 13, 17 і т.д. звертатись до [13]). Цей процес триває до того моменту, поки чергове число п + т не витримає тест. Воно й береться в якості шуканого простого.

Слід звернути увагу на такі нюанси. Якщо застосовується ймовірнісний тест простоти з однобічною помилкою, то вибране число п + т є простим не напевне, а з великою достовірністю. А саме, якщо тест k-кратний, то ймовірність того, що число насправді складене, є експоненційно низькою, наприклад 2^-k у випадку тесту Соловея-Штрассена. Якщо наявні обчислювальні потужності дозволяють взяти k = 100, то ймовірність помилитися стає цілком прийнятною, адже вона не набагато більша за ймовірність того, що суперник зламає криптосистему, банальним чином відгадавши таємне просте число. Числа, які вірогідно, але не напевне прості, часом називають комерційними.

Зупинимось на питанні, якого часу вимагає описана процедура. Зрозуміло, що він обмежується величиною О(т • t(n + m)), де п + т - перше просте число після n, a t(z) — час роботи на вході z тесту простоти, що використовується. Відомі верхні оцінки на т = m(n) наведено у пункті 1.3. Хоча справедливість гіпотези m(n) = (logn)^O(1) невідома, наступні евристичні міркування не розходяться з емпіричним досвідом. Асимптотичний закон розподілу простих чисел (див.пункт 1.3) дає підстави сподіватися, що від п 10¹⁰⁰ найближче просте знаходиться на відстані m ln(10¹⁰⁰) < 230. Якщо ми заощаджуємо тести простоти на числах кратних 2, 3 і 5, то належить протестувати не більше, ніж (1/2 + 1/3 + 1/5 – 1/(2x3) - 1/(2x5) +1/(2x3x5))x230 < 170 чисел. Якщо виключити й числа кратні 7 і 11, то ця кількість зменшиться до 150.

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

ВПРАВИ

2.1.Перевірити, чи є 91 за основою 3 псевдопростим числом а) Ферма, b) Ойлера.

Наступні три вправи запозичені з [111].

2.2. Знайти всі основи х, за якими числа а) 15, b) 21 є псевдопростими.

2.3. Знайти найменше псевдогпросте за основою а) 5, b) 2.

2.4. Нехай п = pq — добуток двох різних простих чисел, і d = НСД (р — 1, q — 1). Довести, що п псевдопросте за основою х тоді і лише тоді, коли xd = 1 (mod п). Виразити через d кількість основ, за якими п псевдопросте.

2.5. Довести, що якщо п є псевдопростим числом Ойлера і п = 3 (mod 4), то п є сильно псевдопростим.

2.6. а) Припустимо, що число п псевдопросте за основами х і у. Довести, що воно псевдопросте також за основою (ху) mod п.

b)Припустимо, що п є псевдопростим числом Ойлера за основами х і у. Довести це також для основи (ху) mod n.

c) Перевірити, що 65 є сильно псевдопростим за основами 8 і 18, але не за основою
14 = (8 • 18) mod 65.

2.7. а) Довести, що якщо число 2^т — 1 просте, то т також мусить бути
простим. Прості числа такого виду називаються простими Мерсенна.

b) Довести, що якщо число 2т + 1 просте, то m мусить бути степенем числа 2. Прості числа такого виду називаються простими Ферма.

Зауваження. Досьогодні невідомо, чи простих Мерсенна є безліч. На 1995 рік було знайдено 33 значення m, для яких 2т — 1 є простим, найбільше з яких є m = 859433 ([127]). Першим складеним числом вигляду 2т — 1 для простого m є 2¹¹ — 1 = 23 • 89. Евклід зауважив, що якщо 2т — 1 є (в сучасній термінології) простим Мерсенна, то число 2m(2m — 1) є досконалим, тобто воно дорівнює сумі всіх своїх дільників (за винятком себе самого). Ойлер довів, що кожне парне досконале число має саме такий вигляд. Питання про існування непарних досконалих чисел відкрите.

Першим складеним числом вигляду є . Розклад цього числа на множники, 4294967297 = 6416700417, отримав Ойлер, спростувавши гіпотезу Ферма, що всі подібні числа є простими. В той час як для багатьох чисел вигляду з l>5 показано, що вони складені, простоту жодного такого числа досі не встановлено [55].

Критерії простоти для чисел Мерсенна і Ферма описані в [55, 12].

2.8. Розглянемо задачу

ПОШУК ПРОСТОГО ПОЗА ЗАДАНОЮ МЕЖЕЮ

Задано: п N.

Знайти: просте р п.

a) Придумати зведення цієї задачі до тестування простоти, яке було б поліноміальним за умови справедливості згаданої в пункті 1.3 гіпотези, що р — п = (log n)^o(1) для простого числа р, найближчого до п зверху. Використовуючи це зведення, описати детермінований алгоритм для пошуку р п, який би був поліноміальним за умови, що справедлива РГР.

b) Придумати поліноміальне ймовірнісне зведення цієї задачі до тестування простоти, і на його основі розробити поліноміальний ймовірнісний алгоритм.

ЛІТЕРАТУРА

В [68] встановлено, що Кармайклових чисел є безіч. Про детермінований тест простоти з [66] йдеться також в [38, 33, 12, 42]. Огляди інших тестів зроблено в [12, 55, 114, 32].

ЛЕКЦІЯ 14

Переглядів: 1296