![]()
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів
Контакти
Тлумачний словник Авто Автоматизація Архітектура Астрономія Аудит Біологія Будівництво Бухгалтерія Винахідництво Виробництво Військова справа Генетика Географія Геологія Господарство Держава Дім Екологія Економетрика Економіка Електроніка Журналістика та ЗМІ Зв'язок Іноземні мови Інформатика Історія Комп'ютери Креслення Кулінарія Культура Лексикологія Література Логіка Маркетинг Математика Машинобудування Медицина Менеджмент Метали і Зварювання Механіка Мистецтво Музика Населення Освіта Охорона безпеки життя Охорона Праці Педагогіка Політика Право Програмування Промисловість Психологія Радіо Регилия Соціологія Спорт Стандартизація Технології Торгівля Туризм Фізика Фізіологія Філософія Фінанси Хімія Юриспунденкция |
|
|||||||
Обчислення функції Ойлера5.1. Випадок аргументу п = pq. Ми почнемо з аналізу задачі обчислення функції ойлера від п = pq Задано: п = pq, де р Обчислити: ф(п). Слід зазначити, що співмножники р і q не входять в умову задачі. Однак якщо вони, відомі, то ф(п) легко обчислюється за формулою Ф(pq) = (p- 1)(q-1). Таким чином обчислення функції Ойлера від аргументів виду n= pq зводиться до факторизації таких чисел. Має місце й обернене зведення. Припустимо, що для числа п = pq відоме значення ф(п). Зауважимо, що ф(п)= п- р- q + 1. Тому співмножники р і q визначаються із системи тобто є розв'язками квадратного рівняння X2 - Х(п + 1 - ф(п)) + п = 0. 5.2. Деякі узагальнення. Для п = pq позначимо ψ(n) = НСК (р - 1,q- 1). Очевидно, що значення ф(п) є кратним до ψ (п). В попередньому пункті ми бачили, що п легко розкладається на співмножники у випадку, коли відомо значення ф(п). Виявляється, для факторизації числа п досить мати довільне число, кратне ψ (n). Точніше, факторизація чисел вигляду п = pq, які є добутком двох простих, зводиться за допомогою поліноміального ймовірнісного алгоритму до такої задачі. Задано: п = pq — добуток двох простих. Знайти: т таке, що ψ (п) ׀ т і т < У другій умові на m, c служить позначенням для довільно фіксованої додатної константи. Таким чином, ця умова означає, що довжина запису т повинна обмежуватись деяким поліномом від довжини запису п. Опис зведення, що пропонується нижче, супроводжується коментарями, які допоможуть зрозуміти, чому зведення влаштоване так, а не інакше. При аналізі зведення нам буде зручно на підставі наслідку II.2.13 утотожнювати мультиплікативну групу у = x mod р і z = х mod q. Нагадаємо, що х отримується з (у, z) ефективним чином, як і навпаки. Перейдемо до опису зведення, тобто деякого алгоритму факторизації чисел п = pq, який має змогу отримувати від оракула певну підказку у вигляді числа m із зазначеними вище властивостями. Вхід: п = pq, де р · Отримати від оракула значення т. Коментар. Оскільки (р— 1) | і (q — 1) | m, то для кожного х хт xm · Якщо (1) виконується для всіх х · Зменшити значення т вдвічі. · Незалежним чином вибрати k випадкових елементів х1,..., хk · Якщо для всіх х =xі з і Коментар. Перед виконанням наступного пункту маємо значення т, для якого (1) виконується не для всіх х x2m (де ймовірність вимірюється за всіма випадковими виборами, що робилися на попередніх кроках, і від яких власне й залежить значення параметру т в поточний момент роботи алгоритму). Справді, множина елементів х, для яких виконується конгруенція (2), утворює підгрупу в За допомогою алгоритму Евкліда обчислити значення НСД ( Оцінимо, з якою ймовірністю описаний алгоритм подає на вихід якийсь із нетривіальних дільників р або q числа п. Як зазначалось, із ймовірністю принаймні 1 -2k для останнього значення параметру m порівняння (2) має місце для всіх х ф(п)=(р- 1)(q- 1). По-друге, для кожного х Випадок 1: (р- 1) | m, (q- 1) | т. Для х = (y,z) маємо хт = (ут,гт), де піднесення до степеня відбувається в групах Випадок 2: (q — 1) | m, (р — 1) | т. Цей випадок симетричний до попереднього. Ті ж міркування показують, що завжди хт = 1 (mod q), але у половині випадків хт = -1 (mod p). Випадок 3: (р — 1) | т, (q — 1)† m. Такими ж міркуваннями, як у випадку 1, встановлюємо, що для випадкового (у, z) Як бачимо, в усіх випадках з імовірністю 1/2 для випадкового х число хт -1ділиться рівно на одне із чисел р або q, тобто НСД (хт -1,п) є нетривіальним дільником числа п = pq. Ймовірність того, що цього не трапиться для жодного з k випадкових х1,.., ,xk, дорівнює 2-k. У підсумку, ймовірність того, що алгоритм не видасть нетривіального дільника числа п, не перевищує 2-k + 2-k, де один доданок береться із щойно отриманої оцінки, а другий обмежує ймовірність того, що порушується зроблене на початку наших міркувань припущення про параметр т. Таким чином, алгоритм досягає мети з імовірністю щонайменше 1 -2-k+1 . ВПРАВИ 5.1.Число 9991 є добутком двох простих і ф(9991) = 9792. Розкласти його на множники. 5.2.Прослідкувати роботу алгоритму із пункту 5.2 на вході п = 35, припустивши, що оракул робить підказку т = 48. ЛІТЕРАТУРА Зробимо кілька зауважень про зв'язок між задачами обчислення функції Ойлера від довільного аргументу та факторизації. Обчислення ф(п) в загальному випадку зводиться до факторизації аргументу п безпосередньо за формулою для функції Ойлера, встановленою в пункті II.2.4. Існування оберненої звідності доведено за РГР в [45]. У [64] зауважується, що із [45] випливає ймовірнісна звідність факторизації до обчислення функції Ойлера. Зокрема, з [45] виводиться звідність, представлена нами в пункті 5.2 (див. також [111, §2.2 розділу IV]).
Читайте також:
|
||||||||
|