МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів Контакти
Тлумачний словник |
|
|||||||
Тестування простотиЦей параграф присвячено задачі Тестування простоти Задано: п 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 грунтується Читайте також:
|
||||||||
|