Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Контакти
 


Тлумачний словник






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

Цей параграф присвячено задачі

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

Задано: п N.

Розпізнати: чи п просте число ?

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

Перший тест простоти був винайдений понад два тисячоліття тому Ератосфеном з Александрії і називається ситом Ератосфєна. Точніше, сито Ератосфєна — це процедура, яка укладає список всіх простих чисел в межах від 1 до заданого п. Коли початковий відрізок простих чисел вже знайдено, наступне просте визначається за таким критерієм: натуральне число є простим тоді і лише тоді, коли воно не ділиться на жодне із передуючих йому простих чисел. Наступний елементарний приклад тесту простоти спирається на ту ж ідею і вимагає часу не більше, ніж просіювання через сито Ератосфeна.

Вхід: п > 1.

Присвоюємо змінній l значення 2.

· Якщо l > [п/2], то закінчуємо роботу і приймаємо вхід (тобто стверджуємо, що п просте).

· Якщо l [п/2] і l | п, то закінчуємо роботу і вхід відхиляємо (зауважимо, що при цьому знайдено перший простий дільник числа п).

· Якщо l [п/2] і l |- п, то збільшуємо l на 1 і вертаємось до виконання того ж умовного оператора.

Однак оцінювання часу роботи дає невтішний діагноз — описаний алгоритм експоненційний. Якщо вхід п є складеним числом, то перевірка цього може й не зайняти багато часу. Скажімо, якщо п > 2 парне, то це з'ясується вже на першому кроці. Але якщо вхід п є простим, то алгоритм змушений виконати [п/2] — 1 крок для кожного l від 2 до [п/2], а це число є експонентою від довжини входу (див. обговорення на стор. 93).

Насправді можна обмежитись [] кроками, позаяк якщо п має нетривіальний дільник l, то мусить мати і нетривіальний дільник, що не перевищує (або сам l, або п/l). Це зауважив близько 1202 року Леонардо Пізанський, знаний як Фібоначчі. Втім, пришвидшений таким чином алгоритм залишається експоненційним. Наступне пониження оцінки часу, необхідного для тестування простоти, було зроблене лише у 1974 році в роботі [113], де запропоновано алгоритм із оцінкою часу O(). Зазначимо, що цей алгоритм теж не тільки визначає, що число складене, а й знаходить його дільник.

Найкращий з існуючих детермінований алгоритм розроблено у [66]. Він розпізнає простоту за час O((logn)clogloglogn) для деякої константи с. Алгоритм з такою оцінкою часу роботи називають квазіполіноміальним. Що важливо, цей алгоритм є ефективним на практиці і реально розпізнає простоту чисел, які мають 100 цифр у десятковому записі.

Поліноміальних алгоритмів тестування простоти сьогодні невідомо.

 

 

ЛЕКЦІЯ 12

 

2.1. Ймовірнісний тест Соловея-Штрассена. Ймовірнісний тест простоти був винайдений у [144]. Він є поліноміальним і має однобічну помилку. Цей тест опирається на

Твердження 2.1. Для непарного п 3 покладемо

Якщо п складене, то ||Sn|| <. ф(п)/2.

Доведення. За мультиплікативністю символу Якобі (пункт 2 твердження 1.7) Sn є підгрупою мультиплікативної групи . Щоб довести твердження, досить показати, що ця підгрупа є власною. Справді, за теоремою Лагранжа ||Sn|| ділить ||.|| = ф(п), а тому, якщо ці числа не рівні між собою, то ||Sn|| може бути щонайбільше ф(п)/2.

Залишається довести існування елемента у\ Sn. Розглянемо два випадки.

Випадок 1: п вільне від квадратів, тобто у розкладі п = р1 .. .рл на прості множники кожне число зустрічається лише один раз.

Виберемо в квадратичний нелишок s за модулем р1. За Китайською теоремою про остачі в існує у таке, що

y = s(modp1), у = 1 (modp2 .. .pk). (1)

Для такого у за пунктами 4 і 1 твердження 1.7 маємо

Проте у(n-1)/2 — 1 (modn), бо інакше було б у(n-1)/2 — 1 (modР2...Pk), суперечність з (1).

Випадок 2: існує просте р таке, що р2 | п.

Візьмемо у = 1 + п/р. Зрозуміло, що для кожного q, простого дільника числа п, виконується конгруенція у 1 (modg). Це означає, що у і = 1, останнє за мультиплікативністю символу Якобі.

З іншого боку у(n-1)/2 — 1 (modn). Справді,

у(n-1)/2 = (1+n/p) (n-1)/2 =

(решта членів у біномі Ньютона кратні п). Отже, якби ліва частина дорівнювала 1 за модулем n, то ми мали б Останнє можливе лише за умови, що р | що неможливо, бо р|п.

ТЕСТ СОЛОВЕЯ-ШРАССЕНА.

Вхід: п — непарне.

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

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

· Якщо , то зупинитись з резолюцією "складене" , інакше зупинитись з резолюцією "просте" .

Коректність. Тест стверджує, що вхід п є простим, для таких і лише таких х, що

НСД(x, n) = 1 i

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

Якщо п складене, то ці дві умови справедливі для всіх х з множини Sn, означеної у твердженні 2.1, і лише для них. Отже, складене п витримує тест з імовірністю, що за твердженням 2.1 не перевищує ф(n)/(2(n-1))<1/2

Таким чином, тест Соловея-Штрассена має однобічну помилку, меншу від 1/2.

Ефективність. Перевірка всіх умов у тесті може бути здійснена ефективно. НСД (х, п) обчислюється за допомогою алгоритму Евкліда, — за допомогою алгоритму із пункту 1.2, а — за допомогою бінарного методу з пункту III. 2. 2. Кожен з цих алгоритмів робить O(logn) операцій ділення з остачею чи множення в Zn. За умови, що ці операції виконуються за час O(log2 n), час роботи тесту є O(log3 n)

Ймовірність помилки можна знизити до 2-k, повторюючи тест k разів згідно із загальною схемою, описаною в пункті III. 3.1. Платою за це буде збільшення часу роботи у k разів.

2.2. Лас Вегас алгоритм. Тест Соловея-Штрассена розпізнає множину простих чисел за поліноміальний час з однобічною помилкою. В [65] запропоновано ймовірнісний поліноміальний алгоритм, що розпізнає з однобічною помилкою множину складених чисел. Як наслідок, для тестування простоти існує Лас Вегас алгоритм (див. вправу III. 3.3).

2.3. Псевдопрості числа. Мала теорема Ферма стверджує, що якщо п — просте число, то для всіх x

xn-1 1(mod) (1)

Непарне п, яке задовольняє умову (1), але не є простим, називається псєвдопростим числом Ферма або просто псєвдопростим за основою х. Деякі складені числа є псевдопростими за будь-якою основою. Це так звані числа Кармайкла, найменшим з яких є 561 = 3 • 11 • 17.

Критерій Ойлера стверджує, що якщо п — непарне просте число, то для всіх x виконується конгруенція

(2)

Непарне п, яке задовольняє умову (2), але не є простим, називається псєвдопростим числом Ойлера за основою х.

Оскільки із (2) випливає (1), то кожне псевдопросте число Ойлера за основою х є також псєвдопростим числом Ферма за цією ж основою. Зворотнє твердження неправильне. З нього випливало б, що кожне число Кармайкла є псєвдопростим числом Ойлера за будь-якою основою. Однак чисел з такою властивістю не існує за твердженням 2.1.

Знову припустимо, що п непарне просте. Нехай п — 1 = 2st, де t непарне. Для елемента х групи розглянемо в цій групі послідовність

Останній член цієї послідовності дорівнює 1 за малою теоремою Ферма, а кожен попередній є квадратним коренем наступного. Оскільки для простого n є полем, то коренем з 1 може бути лише 1 або — 1. Отже, або вся послідовність складається з одиниць, або має хвіст із деякого числа одиниць, перед якими знаходиться —1. Остання умова рівносильна такій:

або xt 1 (mod n),

або існує j, 0 j s, таке, що —1 (mod n).

Непарне п, де п - 1 = 2st з непарним t, яке задовольняє умові (3) для x називається сильно псєвдопростим числом за основою х.

Доведення наступних двох тверджень можна знайти в [111, твердження V.1.6] або [55, теорема 17.2], і в [111, твердження V.1.7], відповідно.

Твердження 2.2. З умови (3) випливав умова (2). Отже, сильно псевдопрості числа за основою х є псевдопростими числами Ойлера за цією ж основою.

Твердження 2.3. Непарне складене число п є сильно псєвдопростим за основою х щонайбільше для четвертої частини всіх х таких, що 1х<п.

2.4. Ймовірнісний тест Міллера-Рабіна. На твердженні 2.3 грунтується


Читайте також:

  1. Для детального тестування
  2. ЕКСПЕРИМЕНТ (ТЕСТУВАННЯ)
  3. Етап тестування
  4. Метод тестування
  5. Методика тестування КІСП аудитором
  6. Оскарження або опротестування.
  7. Оскарження або опротестування.
  8. Перегляд у порядку нагляду рішень, ухвал, постанов у цивільній справі, завдання, суб‘єкти опротестування, суди, які розглядають справи.
  9. ПРИКЛАД ОФОРМЛЕННЯ КОНТРОЛЬНОГО ТЕСТУВАННЯ
  10. Пробне тестування
  11. Протокол тестування
  12. Процес тестування




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

<== попередня сторінка | наступна сторінка ==>
Арифметика II | ТЕСТ МІЛЛЕРА-РАБІНА.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.003 сек.