Быстрые обчислення з цілими числами і полиномами

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

року міністерство освіти Російської Федерации

Ярославський Державний Університет їм. П.Г. Демидова

Курсова работа

По дисципліни «Алгебра»

Швидкі обчислення з цілими числами і полиномами

Виконав: Студент групи КБ-11

Збоїв А.В.

Перевірив: Дурнев В. Г.

Ярославль, 2003

1. Запровадження. Складність теоретико-числовых алгоритмів. 2. Полиномиальные алгоритмы

1. Алгоритм обчислення ad mod m

2. Дихотомический алгоритм спорудження в степень

3. Алгоритм Евклида

4. Алгоритм рішення рівняння ax + by = 1 3. Полиномиальная арифметика

1. Алгоритм перебування делителей багаточлена f (x) в кільці Fp[x]

2. Твір та побудову до рівня багаточленів, заданих массивами

3. Невеликі оптимізації для твори многочленов

4. Обчислення полиномов

1. Схема Горнера

2. Интерполяционная формула Ньютона і табулювання значень багаточлена 4. Дискретне логарифмирование

1. Запровадження. Складність теоретико-числовых алгоритмов

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

На погляд дивним також здається, що операції множення і розподілу прирівнюються за складністю до операцій складання і вирахування. Житейський досвід підказує, що множити числа виявляється значно складнішим, ніж складати їх. Тоді як, обчислення то можна організувати так, що у множення чи розподіл великих чисел знадобиться набагато менше бітових операцій, ніж складання. Існує алгоритм Шенхаге — Штрассена, заснований на так званому швидкому перетворення Фур'є, і вимагає O (n ln n lnln n) бітових операцій для множення двох n-разрядных двійкових чисел. Так само кількістю бітових операцій можна обійтися і під час розподілу із залишком двох двійкових чисел, записуваних лише n цифрами. Порівняйте відзначимо, що складання n-разрядных двійкових чисел вимагає O (n) бітових операций.

Ведучи мову про складності алгоритмів, ми не матимемо у вигляді кількість арифметичних операцій. При побудові ефективних алгоритмів і обговоренні верхніх оцінок складності зазвичай вистачає інтуїтивних понять тій галузі математики, котра має алгоритм. Формалізація цих понять залишається лише тоді, коли йдеться про відсутність алгоритму чи доказі нижніх оцінок сложности.

2. Полиномиальные алгоритмы

Чотири приведених нижче алгоритму ставляться до розряду про полиномиальных алгоритмів. Цю саму назву носять алгоритми, складність яких оцінюється згори статечним чином у залежність від довжини записи вхідних чисел. Якщо найбільше з чисел, поданих на вхід алгоритму, не перевершує m, то складність алгоритмів цього оцінюється величиною O (lncm), де з — деяка абсолютна стала. В усіх життєвих приведених прикладах з =1.

Наступний алгоритм обчислює admod m. У цьому, звісно, передбачається, що натуральні числа a і d вищими за за величиною m.

2.1 Алгоритм обчислення ad mod m

1. Уявімо d в двоичной системі числення d = d02r+…+dr-12+dr, де di, цифри в двоичном поданні, рівні 0 чи 1, d0 = 1.

2. Поклавши a0 = a і далі для і = 1,…, r обчислимо ai (a2i-1adi (mod m).

3. ar є шуканий відрахування admod m.

Справедливість цього алгоритму випливає з сравнения

ai (a2i-1ad02^i+…+di (mod m),

легко доказуваного індукцією по i.

Оскільки кожне обчислення на кроці 2 вимагає трохи більше трьох умножений по модулю m і це крок виконується r (log2 m раз, то складність алгоритму можна оцінити величиною O (ln m).

2.2 Дихотомический алгоритм спорудження в степень.

Загалом вигляді дихотомический алгоритм дозволяє обчислити n-ю ступінь в моноиде. Будучи застосований до безлічі цілих чисел з операцією складання, цей метод дозволяє множити два цілих числа і більше відомий як єгипетське умножение.

Класичний алгоритм спорудження до рівня у вигляді послідовного множення характерний, переважно, своєї неефективністю у звичайних обставин — його час лінійним чином від того показника степени.

Візьмемо моноид М з операцією множення і розглянемо певний елемент x0 з М, і навіть довільне натуральне число n0. А, щоб вычислить

, уявімо n0 в двоичной системі числення: n0 = bt2t + bt — 12t — 1 + … + b121 + b020, припускаючи, що n0 містить (t + 1) двоичных цифр (т. е. що bt (0 і bt + 1 = 0). У умовах вычисляемое вираз то, можливо записано:

або ж.

Якщо задана послідовність (xi)0 (і (t, перший елемент якої є x0 і xi для і([1,t] визначено співвідношенням xi = xi — 12, то можна записати = ({xi | 0 (і (t, bi (0}. Щоб завершити побудова алгоритму і можливість отримати значення попереднього твори, необхідно обчислити біти bi числа n0. Для послідовності (ni) 0 (і (t+1 (з початковим елементом n0), певній співвідношенням ni = [ni-½] нічого для будь-якого і ([1, t + 1], біт bi нульовий, якщо ni чётно, і дорівнює одиниці інакше. Перше значення індексу і, котрій ni одно нулю, є t + 1.

Зрозуміло, що кількість ітерацій, необхідні виконання алгоритму, залежить тільки від показника n.

2t (n (2t + 1 чи t (log2n < t + 1.

Перша частину акцій цього властивості має так: [n/2t + 1] = 0 і [n/2t] (0, що дозволяє точно визначити число скоєних ділень n, однакову числу ітерацій алгоритму при заданому значенні n. Вочевидь, потрібно здійснити t + 1 ітерацій, аби виконати алгоритм, т. е. [log2n] + 1 ітерацій. Отже, трудоёмкость алгоритму є O (log n).

Третій алгоритм — це класичний алгоритм Евкліда обчислення найбільшого загального дільника цілих чисел. Ми вважаємо заданими два натуральних числа a і b і обчислюємо їх найбільший загальний дільник (a, b).

2.3 Алгоритм Евкліда 1. Обчислимо r — залишок від розподілу числа a на b, a = bq+r, 0 (r < b. 2. Якщо r = 0, то b є дані число. 3. Якщо r (0, то замінимо пару чисел (a, b) парою (b, r) і перейдём до шагу1.

Без упину на поясненні, чому алгоритм справді знаходить (a, b), доведемо деяку оцінку його сложности.

Теорему 1. При обчисленні найбільшого загального дільника (a, b) з допомогою алгоритму Евкліда буде виконано трохи більше 5p операцій розподілу із залишком, де p є кількість цифр в десяткової записи меншого з чисел a і b.

Доказ. Поклавши r0 = a > b і визначимо r1, r2,…, rn — послідовність делителей, з’являються у виконання кроку 1 алгоритму Евкліда. Тоді r1 = b,…, 0 (ri+1 < ri, і = 0,1,…, n — 1. Нехай також u0 = 1, u1 = 1, uk+1 = uk+uk-1, k (1, — послідовність Фібоначчі. Індукцією по і від і = n — 1 до і = 0 легко доводиться нерівність ri+1 (un-i. Оскільки un (10(n-1)/5, тут маємо нерівності 10p > b = r1 (un (10(n-1)/5 і n < 5p+1.

Трохи підправивши алгоритм Евкліда, можна досить швидко вирішувати порівняння ax (1 (mod m) за умови, що (a, b) = 1. Це завдання рівносильна пошуку цілих рішень рівняння ax + by = 1.

2.4 Алгоритм рішення рівняння ax + by = 1

0. Визначимо матрицю E =

1. Обчислимо r — залишок від розподілу числа a на b, a = bq + r, 0 (r < b.

2. Якщо r = 0, то другий стовпець матриці Є дає вектор (x y) рішень уравнения.

3. Якщо r (0, то замінимо матрицю Є матрицей

4. Замінимо пару чисел (a, b) парою (b, r) і перейдём до кроку 1.

Якщо позначити через Еk матрицю Є, виникає своєю практикою алгоритму перед кроком 2 після k ділень із залишком (крок 1), то позначеннях з докази теореми 1 на той час виконується векторное рівність (a, b)(Ek = (rk-1,rk). Його легко довести індукцією по k. Оскільки числа a і b взаємно прості, маємо rn = 1, і це доводить, що алгоритм справді дає рішення рівняння ax + by = 1. Буквою n ми позначили кількість ділень із залишком, що у точності таку ж, як й у алгоритмі Евклида.

Полиномиальные алгоритми теоретично чисел — велика рідкість. Та й оцінки складності алгоритмів найчастіше спираються на будь-які не доведені, але правдоподібні гіпотези, зазвичай які стосуються аналітичної теорії чисел.

Для деяких завдань ефективні алгоритми взагалі відомі. Іноді в такі випадки усе ж таки можна запропонувати послідовність дій, яка, «якщо повезе», швидко призводить до необхідному результату. Існує клас про ймовірнісних алгоритмів, що дають правильний результат, але мають імовірнісного оцінку часу роботи. Зазвичай робота цих алгоритмів залежить від однієї чи навіть кількох параметрів. У разі вони працюють який досить довго. Але вдалий вибір параметра визначає швидке завершення роботи. Такі алгоритми, якщо безліч «хороших» значень параметрів велике, практично працюють досить ефективно, хоча й мають хороших оцінок сложности.

3. Полиномиальная арифметика

Розглянемо імовірнісний алгоритм, дозволяє ефективно знаходити рішення полиномиальных порівнянь простим модулю. Нехай p — просте число, яке передбачається великим, і f (x)(Z[x] - багаточлен, ступінь якої планується обмеженою. Завдання полягає у знаходженні рішень порівняння f (x) (0 (mod p). (1) Наприклад, можна говорити про рішення квадратичных порівнянь, якщо ступінь багаточлена f (x) дорівнює 2. Інакше кажучи, ми повинні відшукати на полі Fp = Z/pZ все елементи, задовольняють рівнянню f (x) = 0.

Відповідно до малої теоремі Ферма, все елементи поля Fp є однократными корінням багаточлена xp — x. Тому, зрозумівши найбільший загальний дільник d (x) = (xp — x, f (x)), ми знайдемо багаточлен d (x), безліч коренів що його полі Fp збігаються з безліччю коренів багаточлена f (x), причому всі ці коріння однократны. Якщо з’ясується, що багаточлен d (x) має нульову ступінь, т. е. лежать у полі Fp, це означатиме, що порівняння (1) немає решений.

Для обчислення багаточлена d (x) зручно спочатку обчислити багаточлен c (x)(xp (mod f (x)), користуючись алгоритмом, подібним описаного вище алгоритму спорудження до рівня (нагадаємо, що кількість p передбачається великим). Ну, а потім з допомогою аналога алгоритму Евкліда обчислити d (x) = (c (x) — x, f (x)). Усе це виконується за полиномиальное кількість арифметичних операций.

Отже, обговорюючи далі завдання перебування рішень порівняння (1) ми можемо припускати, що у кільці багаточленів Fp[x] справедливо рівність f (x) = (x — a1)(…((x — an), ai (Fp, ai (aj.

3. 1 Алгоритм перебування делителей багаточлена f (x) в кільці Fp[x] 1. Виберемо у спосіб елемент ((Fp. 2. Обчислимо найбільший загальний дільник g (x) = (f (x), (x + ()(p-1)/2 — 1). 3. Якщо багаточлен g (x) виявиться власним делителем f (x), то багаточлен f (x) розпадається на два множника і з кожним із них незалежно потрібно буде проробити усі фінансові операції, передбачені справжнім алгоритмом для багаточлена f (x). 4. Якщо з’ясується, що g (x) = 1 чи g (x) = f (x), слід можливість перейти до кроку 1 і, обравши нового значення (, продовжити виконання алгоритма.

Кількість операцій на кроці 2 оцінюється величиною O (ln p), якщо обчислення проводити оскільки це вказувалося вище під час перебування d (x). З’ясуємо де тепер, як довго доведеться вибирати числа (, перебувають у кроці 2 не буде знайдено власний дільник f (x).

Кількість рішень рівняння (t + a1)(p — 1)/2 = (t + a2)(p — 1)/2 в полі Fp не перевершує (p-3)/2. Це означає, що підмножина D (Fp, що складається з елементів (, які відповідають условиям

((+ a1)(p — 1)/ 2 (((+ a2)(p — 1)/ 2, ((-a1, ((-a2, не менш як (p — 1)/2 з елементів. З огляду на тепер, кожен ненульовий елемент b (Fp задовольняє одного з рівностей b (p — 1)/2 = 1, або b (p — 1)/2 = -1, укладаємо, що з ((D одна з чисел a1, a2 буде коренем багаточлена (x + () (p — 1)/2 — 1, а інше — немає. Для таких елементів (багаточлен, певний на кроці 2 алгоритму, буде власним делителем багаточлена f (x).

Отже, існує менш (p -1)/2 «вдалих» виборів елемента (, при яких кроці 2 алгоритму багаточлен f (x) розпадається у власних множника. Отже, при «випадковому» виборі елемента ((Fp, можливість, що багаточлен не розкладеться на множники після k повторень кроків алгоритму 1−4, не перевершує 2-k. Можливість зі зростанням k убуває нас дуже швидко. І це дійсно, практично цей алгоритм працює досить эффективно.

Зауважимо, що з оцінці ймовірності ми використовували лише 2 кореня багаточлена f (x). При n > 2 ця можливість, звісно, ще менше. Більше тонкий аналіз з допомогою оцінок А. Вейля для сум характерів показує, що ймовірність для багаточлена f (x) не розпастися на множники при одноразовому проході кроків алгоритму 1−4 не перевершує 2-n + O (p-½). Тут стала в O (.) залежить від n. Нині відомо елементарне доказ оцінки А. Вейля.

Якщо порівнянні (1) замінити простий модуль p складовим модулем m, то завдання перебування рішень відповідного порівняння стає набагато складнішою. Відомі алгоритми вирішення засновані на зведенні порівняння до сукупності порівнянь (1) за простими модулями — делителям m, і, отже, вони вимагають розкладання числа m на прості сомножители, що, як зазначалося, є дуже трудоёмкой задачей.

3.2 Твір та побудову до рівня багаточленів, заданих массивами

Домовимося представляти багаточлени масивами, индексированными, починаючи з 0, у яких елемент з індексом і означає коефіцієнт багаточлена ступеня i

type Polynome=array[1. Nmax] of Ring_Element;

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

for і:= 0 to degP do for j:= 0 to degQ do

R[i+j]: =R[i+j]+P[i](Q[i];

Вивчаючи попередній алгоритм, встановлюємо, що його складність як у числу перемножений, і сложений, дорівнює твору висот двох багаточленів: (deg P + 1)(degQ + 1), але нинішнього алгоритмі, який враховує випадок нульових коефіцієнтів, так можна трактувати висоту багаточлена і кількість всіх коефіцієнтів. Отже, можливо поліпшити попередній алгоритм, виключивши все непотрібні перемножения:

for і:= 0 to degP do if P[i] (0 then for j:= 0 to degQ do if Q[j] (0 then

R[i+j]: =R[i+j]+P[i]Q[i];

Очень просто обчислити складність алгоритму спорудження до рівня послідовними множеннями, якщо помітити, що коли і P — багаточлен ступеня d, то Pi — багаточлен ступеня id. Якщо позначити Cmul (n) складність обчислення Pn, то рекуррентное співвідношення Cmul (i + 1) = Cmul (i) + (d +1)(id +1) дає нам:

Cmul (n) = =

Що ж до спорудження до рівня з допомогою дихотомії (тобто. повторюваними возведениями в квадрат), обчислення трохи складніше: знаючи, обчислюємо з мультипликативной складністю. Як наслідок имеем:

Csqr (2l) = = =

=

Попередній висновок, що можна вивести ринок із попередніх обчислень, складається у користь дихотомічного спорудження до рівня: якщо n є ступінь двійки (гіпотеза ad hock), цей алгоритм ще витримує конкуренцію, навіть Якщо ця перемога набагато скромніший і у цьому контексті (n2d2/3 проти n2d2/2), ніж коли працюємо в Z/pZ (2log2 n проти n).

Але ми врахували коригувальні перемножения, що їх виконані, коли показник перестав бути ступенем двійки. Якщо n = 2l+1 — 1, потрібно додати послідовним возведениям в квадрат перемножения всіх отриманих багаточленів. Множення багаточлена ступеня (2i-1)d на багаточлен ступеня 2id вносить свій внесок з ((2i — 1) d + 1)(2i d + 1) умножений, які, будучи зібраними за всі коригувальним обчисленням, дають додаткову сложность:

= =

=

Нині можна укласти, що дихотомічне спорудження до рівня не завжди кращий способом для обчислення ступеня багаточлена з допомогою перемножений багаточленів. Кількість перемножений базисного кільця, які необхідні, Csqr (n), — насправді укладено між (

) і тобто. між n2d2/3 і 2n2d2/3, тоді як простий алгоритм вимагає завжди n2d2/2 перемножений. Зокрема, якщо вихідний багаточлен має ступінь, більшу чи рівну 4, спорудження в ступінь наївним методом потребує менших перемножений в базисному кільці, ніж бінарну спорудження до рівня, коли n має форму 2l — 1.

Можна досить просто довести, що й n має вигляд 2l +2l — 1 + з (висловлювання, які мають двоичное розкладання n), то метод обчислення послідовними перемножениями краще методу, котрий використовує спорудження в квадрат (цей останній метод вимагає коригувального рахунку ціною, по крайнього заходу, n2d2/9). Усе це доводить, що наївний спосіб є найкращим при цьому класу алгоритмів, по крайнього заходу, о пів случаев.

Справді, МакКарті [3] довів, що дихотомический алгоритм спорудження до рівня оптимальний серед алгоритмів, оперують повторними множеннями, якщо діють з щільними многочленами (антонім до розрідженим) по модулю m, чи з цілими та за умов оптимізації спорудження в квадрат для скорочення його складності наполовину (у разі складність справді падає приблизно до n2d2/6 + n2d2/3 = n2d2/2).

3.3 Невеликі оптимізації для творів многочленов

У принципі так обчислення твори двох багаточленів ступенів n і m відповідно вимагає (n +1)(m +1) елементарних перемножений. Алгоритм оптимізації спорудження в квадрат полягає просто застосуванні формули квадрата суммы:

что дає n +1 умножений на першому члена і n (n +1)/2 — на другому, чи цілому (n +1)(n +2)/2 умножений, що близько до половини передбачених умножений, коли n большое.

Для твори двох багаточленів першого ступеня P = aX + b і Q = cX + d досить легко знаходимо формули U = ac, W = bd, V = (a + b)(c + d) і PQ = =UX2 + (V — U — W) X +W, у яких виходять лише один три елементарних множення, але чотири складання. Можна рекурсивно застосувати той процес для множення двох багаточленів P і Q ступеня 2l — 1, представляючи їхнього як і застосовуючи попередні формули для обчислення PQ в залежність від A, B, З і D, де кожна твір AB, CD і (A + B)(C + D) обчислюється з допомогою рекурсивного застосування зазначеного методу (це метод Карацубы). Усе це дає мультипликативную складність ((2l) і аддитивную складність ((2l) такі, что:

((2l) = 3((2l — 1),…, ((2) = 3((1), ((1) = 1,

((2l) = 3((2l — 1) + 3(2l,…, ((2) = 3((1) + 6, ((1) = 1. У цьому останньої формулі член 3(2l є число елементарних сложений, необхідних, щоб зробити два складання багаточленів ступеня 2l — 1 — 1 (a + b і з + d) і двоє вирахування багаточленів ступеня 2l — 1 (U — V — W). Підсумовуючи кожне з цих висловів, знаходимо для n, що є ступенем двойки:

((n) = nlog3/log2 (n1,585 і ((2) =7 nlog3/log2 — 6n. На жаль, Україні цього принципу залишається теоретичним, і вкриваю його основі потрібно побудувати итерационный алгоритм, щоб отримати розумну ефективність (ціна управління рекурсією дуже велика).

3.4 Обчислення многочленов

Розглянемо спільне завдання обчислення багаточлена енну кількість ступеня u (x) = unxn + un — 1xn — 1 + … + u1x + u0, un (0,

(1)

3.4.1 Схема Горнера u (x) = (…(unx + un — 1) x + …)x + u0. (2) Усе це процес вимагає n умножений і n сложений.

Було запропоновано кілька узагальнень схеми Горнера. Погляньмо спершу, як обчислюється у разі, коли — комплексне число, а коефіцієнти речовинні. Комплексне складання і множення можна вочевидь зводити до послідовності звичайних операцій над речовими числами: речовинне + комплексне вимагає 1 складання, комплексне + комплексне вимагає 2 складання, речовинне (комплексне вимагає 2 множення, комплексне (комплексне вимагає 4 множення і 2 складання чи 3 множення і п’яти сложений. Отже, схема Горнера (2) вимагає 4n — 2 умножений і 3n — 2 сложений чи 3n — 1 умножений і 6n — 5 сложений для обчислення u (z), коли z комплексне. Ось інша процедура для обчислення u (x + iy): a1 = un, b1 = un — 1, r = x + x, p. s = x2 + y2; (3) aj = bj — 1 + raj -1, bj = un — j — saj -1, 1 < j (n. Легко довести індукцією по n, що u (z) = zan + bn. Ця схема вимагає 2N + 2 умножений і 2N + 1 сложений, отже при n (3 вона краще схеми Горнера.

Розглянемо процес розподілу багаточлена u (x) на багаточлен x — x0. У результаті такої розподілу ми маємо u (x) = (x — x0) q (x) + r (x); тут deg® < 1, тому r (x) є стала, котра від x і u (x0) = 0(q (x0) + r = r. Аналіз цього процесу розподілу показує, що обчислення майже ті ж, що у схемою Горнера визначення u (x0). Аналогічно, ми ділимо u (z) на багаточлен (z — z0)(z — z0) = z2 — 2x0z + x02 + y02, це були відповідні обчислення еквівалентні процедурі (3); ми маємо u (z) = (z — z0)(z — z0) q (z) + anz + bn; отже, u (z0) = anz0 + bn.

Взагалі, ми ділимо u (x) на, f (x) одержуючи u (x) = f (x) q (x) + r (x), то з рівності f (x0) = 0 слід u (x0) = r (x0); це спостереження веде до подальшим узагальнень правила Горнера. Ми можемо покласти, наприклад, f (x) = x2 — x02; це дозволить нам схему Горнера «другого порядку» u (x) = (…(u2(n/2 (x2 + u2(n/2 (- 2) x2 + u0 +

+((… u2(n/2 (- 1×2 + u2(n/2 (- 3) x2 + … +)x2u1) x.

(4)

3.4.2 Интерполяционная формула Ньютона і табулювання значень многочлена

Розглянемо спеціальний випадок обчислення багаточлена. Интерполяционный багаточлен Ньютона ступеня n, визначається формулою u[n](x) = (n (x — x0) (x — x1)…(x — xn — 1) +…+ (n (x — x0) (x — x1) + (1 (x — x0) + (0, (5) єдиний многочленом ступеня (n від x, котра приймає запропоновані значення y0, y1, …, yn в заданих n + 1 різних точках x0, x1, …, xn відповідно. Потому, як значення постійних (знайдено, интерполяционная формула Ньютона стає зручною для обчислень, оскільки ми можемо, узагальнивши правило Горнера, записати u[n](x) = ((…((n (x — xn — 1) + (n — 1)(x — xn — 2) + …)(x — x1) + (1)(

((x — x0) + (0. (6)

Тепер на, як перебувають постійні (у формулі Ньютона. Їх можна визначити, знаходячи «розділені різниці» і зводячи обчислення в таку таблицю (яка ілюструє випадок n = 3):

y0 (y1 — y0)/(x1 — x0) = y (1 y1 (y2 — y'1)/(x2 — x0) = y ((2 (y2 — y1)/(x2 — x1) = y (2 (y''3 — y''2)/(x3 — x0) = y (((3 y2 (y3 — y'2)/(x3 — x1) = y ((3 (y3 — y2)/(x3 — x2) = y (3 y3 (7) Можна довести, що (0 = y0, (1 = y'1, (2 = y'2, тощо. буд. Отже, для перебування величин можна використовувати наступна обчислювальна процедура (відповідна таблиці (7)):

Почати сіло, що встановити ((0, (1, …, (n) ((y0, y1, …, yn); потім для k = 1, 2, …, n (саме у такого порядку) встановити yj ((yj

— yj — 1)/(xj — xj — k) для j = n, n — 1, …, k (саме у такому порядке).

Якщо хочемо обчислити багаточлен u (x) ступеня n відразу багатьом значень x, їхнім виокремленням арифметичну прогресію (т. е. хочемо обчислити u (x0), u (x0 + h), u (x0 + 2h),…), то весь процес можна одержати після кількох перших кроків звести до одного лише додаванню через те факту, що n-я різницю від багаточлена є стала. 1. Знайти коефіцієнти (n, …, (1, (0 уявлення нашого багаточлена як интерполяционного багаточлена Ньютона u (x) = (n / n! hn (x — x0 — (n — 1) h)…(x — x0 — h)(x — x0) +…+

(2 / 2! h2(((x — x0 — h)(x — x0) + (1 / h2 (x — x0) + (0. (8)

(Це можна зробити, беручи повторні різниці, з точністю як і, як ми визначали вище постійні (в (5) (треба прийняти xj = x0 + jh), про те винятком, що це розподілу на xj — xj — k з обчислювальної процедури усуваються.) 2. Встановити x (x0. 3. Тепер значенням u (x) є (0. 4. Встановити (j ((j + (j + 1 для j = 0, 1, …, n — 1 (саме у такого порядку). Збільшити x на h і повернутися до крок 3.

4. Дискретне логарифмирование

Нехай p — просте число. Ще Эйлер знав, що мультипликативная група кільця циклична, т. е. є такі цілі числа що порівняння ax (b (mod p) (2) вирішується щодо x незалежно від b (Z, не делящимся на p. Числа і з цим властивістю називаються первообразными корінням, і кількість їх одно ((p — 1), де (- функція Эйлера. Ціле x, що задовольнить порівнянню (2), називається індексом чи дискретним логарифмом числа b.

Вище ми описали алгоритм, дозволяє по заданому числу x досить швидко вираховуватимуть ох mod p. Зворотний ж операція — обчислення по заданому b його дискретного логарифма, власне кажучи, є дуже складної в обчислювальному відношенні завданням. Саме ця властивість дискретного логарифма і використовують у його численних криптографічних цілях. Найбільш швидкі (з відомих) алгоритми вирішення цього завдання, засновані на так званому методі решета числового поля, вимагають виконання exp (c (ln p)1/3(ln ln p)2/3) арифметичних операцій, де з — деяка позитивна стала. Це можна порівняти складності найбільш швидких алгоритмів розкладання чисел на множники. Звісно, зазначена оцінка складності отримана за умови справедливості низки досить правдоподібних гипотез.

Ведучи мову про складності завдання дискретного логарифмирования, ми мали у вигляді «загальний випадок». Адже й велике ціла кількість легко то, можливо розкладено на прості сомножители, якщо ці сомножители невідь що великі. Відомий алгоритм, дозволяє швидко вирішувати проблему дискретного логарифмирования, якщо p — 1 є твором малих простих чисел.

Нехай q — просте число, подумки ділить р — 1. Означимо з (а (p — 1)/q (mod p), тоді класи відрахувань 1, з, с2, …, сq — 1 все різняться утворюють повне безліч рішень рівняння хq = 1 на полі Fp = Z/Zp. Якщо q не велика і ціла кількість d задовольняє порівнянню хq (1 (mod p), то показник k, 0 (k < q, котрій виконується d (ck (mod p), легко може бути знайдений, наприклад, з допомогою перебору. На цьому властивості грунтується вищезгадана алгоритм.

Припустимо, що р — 1 = qkh, (q, h) = 1. Алгоритм послідовно будує цілі числа uj, j = 0,1,…, k, котрим виконується сравнение

(1 (mod p). (3) Оскільки виконується порівняння (1 (mod p), те знайдеться ціла кількість u0, котрій ((mod p). За такої виборі порівняння (3) з j = 0, очевидно, виконується. Припустимо, що знайдено число uj, що задовольнить порівнянню (3). Тоді визначимо t з допомогою сравнения

(ct (mod p), (4)

и між іншим. Трапляються сравнения

((1 (mod p), (5) які означають справедливість (3) при j + 1.

При j = k порівняння означає з (2), що (1 (mod p). Ціле число, а є первообразный корінь по модулю р, тому маємо (x — uk) h (0 (mod p — 1) і x (uk (mod qk).

Якщо, де всі прості числа qj малі, то зазначена процедура дозволяє знайти відрахування x mod, і = 1,…, s, і, з допомогою китайської теореми про залишках, відрахування x mod p — 1, т. е. вирішити порівняння (2).

Що стосується звичайних логарифмів на полі дійсних чисел є спеціальне підставу e = 2,171 828…, що дозволяє досить швидко вираховуватимуть логарифми із довільною точністю. Наприклад, це робити з допомогою швидко сходящегося низки ln (1+x)/(1 — x) = 2(x + x3/3 + x5/5 + …), |x| < 1. (6) Логарифми по произвольному підставі з може бути враховано з допомогою тотожності logc x = ln x/ ln з. (7) Що стосується дискретних логарифмів немає підстави, яким логарифми обчислювалися так само швидко, як натуральні на полі дійсних чисел. Разом про те, остання формула, котра зв’язує логарифми з різними підставами, залишається справедливою і дозволяє вибирати підставу зручним способом. Єдине умова при цьому у тому, щоб логарифм нового підстави Log з був взаємно простий з p — 1. Тоді, у формулі (7) можливо розподіл по модулю р — 1. Зауважимо, що це основна умова буде виконано, як і лише коли з — первообразный корінь. З розширеній гіпотези Рімана слід, що найменший первообразный корінь по модулю р обмежений величиною O (log6 p). Тому надалі для простоти викладу ми припускати, що створення, а (2) невелика, саме, а = O (log6 p).

Оскільки полі Fp неповно, обчислення дискретних логарифмів неспроможна використовувати граничний перехід й грунтується на інших засадах. Насамперед, потрібний дискретний логарифм log b обчислюється не сам собою, а разом із сукупністю логарифмів інших чисел. Зауважимо, що кожне порівняння вида

((mod p), (8) де qi, ki, mi (Z призводить до співвідношенню між логарифмами

(k1 — m1) Log q1 + … + (ks — ms) Log qs (0 (mod p — 1). (9)

А якщо виконуються сравнения

a ((mod p — 1) b ((mod p),

то

r1Log q1 +…+ rsLog qs (1 (mod p — 1) (10) и

Log b (x1Log q1 +…+ xsLog qs (mod p — 1) (11) Маючи досить багато векторів k1,…, ks, m1,…, ms з вимогою (8), можна знайти рішення відповідної системи порівнянь (9), (10). Якщо цю систему має єдине рішення, то саме ним і буде набір логарифмів Log q1,…, Log qs. Потім із допомогою (11) можна знайти Log b.

Ми опишемо нижче реалізацію цієї ідеї, узяту із роботи [1]. Евристичні міркування дозволили авторам цієї роботи стверджувати, що запропонований ними алгоритм вимагає L1 + (, де L =, арифметичних операцій для обчислення Log b.

Положим

H = [ ] + 1, J = H2 — q. Тоді 0 < J < 2 + 1, як і легко перевірити, для будь-який пари цілих чисел с1, с2 виконується сравнение

(H + c1) (H + c2) (J + (c1 + c2) H + c1c2 (mod p). (12) Якщо числа ci невідь що великі, скажімо ci (L½ + (попри деякий (> 0, то права частина порівняння (12) не перевершує p½ + (/2. Можна довести, що випадково обраний натуральне число x < p½ + (/2 розкладається в твір простих чисел, менших з імовірністю, більшої, ніж L-½ — (/2.

Означимо через P. S = {q1,…, qs} сукупність всіх простих чисел q < L½, і навіть всіх простих чисел виду H + з при 0 < з < L½ + (. Тоді p. s = O (L½ + (). Будемо тепер перебирати випадково числа для кожної такий пари намагатися розкласти на множники відповідне вираз з правій частині (12). Для розкладання можна скористатися, наприклад, розподілом попри всі прості числа, менші, ніж L½. Перебравши все (L½ + ()2/2 = O (L1 + 2() зазначених пар с1, с2 ми знайдемо, як це випливає із зазначених вище ймовірнісних міркувань, не менее

L-½ — (/2 *O (L1 + 2() = O (L½ + 3(/2) (13) пар, котрим права частина порівняння (12) повністю розкладається на прості сомножители, менші L½. Порівняння (12), в такий спосіб, приймає вид (8). Так будується система рівнянь типу (9).

Нагадаємо, що кількість а, до нашого припущенню, істотно менше, ніж L½. Тому розкладається у твір простих чисел, які входять у безліч {q1,…, qs}, і усе веде до порівнянню (10).

Зауважимо, що його (13) знайдених порівнянь типу (9) перевершує число p. s. Отже, побудована система неоднорідних лінійних порівнянь щодо Log qi містить порівнянь більше, ніж невідомих. Звісно, безліч її рішень в тому бути нескінченним. Один із правдоподібних гіпотез у тому, що систему має усе ж єдине рішення, і, вирішивши її, можна визначити дискретні логарифми всіх чисел qi. У цьому завершується перший етап роботи алгоритму з [1].

Як відзначалося, кожна з чисел, котрі стоять у правій частині порівняння (12), не перевершує p½ + (/2. Тому розкладається у твір трохи більше O (ln p) простих сомножителей і, отже, кожна з порівнянь (9) побудованої системи утримує лише O (ln p) відмінних нуля коефіцієнтів. Матриця системи порівнянь буде розрідженій, що дозволяє застосовувати його рішення спеціальні методи з не меншою оцінкою складності, ніж звичайний гауссов метод винятку переменных.

Замість перебору всіх допустимих значень ci в [1] пропонується використовувати зване решето, отбрасывающее все пари цих чисел, для яких права частина (12) явно не розкладається у твір малих простих сомножителей. До кожного c1 і «кожної малої простий ступеня q «< L½ можна знайти рішення c2 < L½ лінійного сравнения

J + (c1 + c2) H + c1c2 (0 (mod q "). Організована правильним чином, цю процедуру одночасно відбирає все потрібні пари чисел c1, c2 і дає розкладання на прості сомножители правих частин порівнянь (12).

Отже, після першим етапом роботи алгоритму у нашій розпорядженні виявляються дискретні логарифми всіх чисел з багатьох P. S. Другий етап алгоритму зводить пошук дискретного логарифма числа b для пошуку логарифмів деякого безлічі чисел u, не переважаючих за величиною L2. Обираючи випадково число (трохи більше L¼ раз, можна, як свідчать імовірнісні міркування, знайти таке (, що відрахування a (b mod p розкладається у твір простих чисел, менших L2. Пусть

(mod p)

такое розкладання, де u1,…, ut — деякі прості числа з вимогою L½ < u < < L2. На пошук цього порівняння знадобиться O (L½)арифметических операцій. Через війну обчислення дискретного логарифма числа b зводиться до вирахування t дискретних логарифмів для чисел uj, 1 (j (t середнього размера.

Нарешті, на останньому етапі виробляється обчислення логарифмів всіх чисел uj. Нехай u — просте число з інтервалу умовою L½ < u < L2. Обозначим

G = [(p / u], I = HGu — p.

Для будь-яких цілих чисел c1, c2 < L½ + (виконується сравнение

(H + c1) (H + c2) u (I + (c1G+ c2H + c1c2) u (mod p). (14) Зазначимо, що права частину акцій цього порівняння не перевершує p½ L5/2 + (. Просіваючи все числа c1, c2 із зазначеного інтервалу, можна знайти такі, що числа G+ c2 і права частина порівняння (14) складаються з простих сомножителей, не переважаючих L½. Тоді порівняння (14) дозволяє обчислити Log u. Обчислення Log b при відомих вже значеннях Log q1 вимагає L½ + (арифметичних операций.

Є й інші способи побудови співвідношень (8). У [2] при цьому використовуються обчислення в полях алгебраїчних чисел. Як множників в співвідношення типу (8) використовуються як прості числа, а й прості ідеали, з невеличкий нормой.

Завдання обчислення дискретних логарифмів можна розглядати й у полях Fpn, які з pn елементів, в мультипликативных групах класів відрахувань (Z/mZ)*, в групах точок еліптичних кривих і загалом у довільних группах.

1. Введення у криптографію за загальною редакцією Ященко, М.: МЦНМО:

«Черо», 1999.

2. Алгебраїчна алгоритмика, Ноден П., Китте До., М.: «Світ», 1999.

1] Coppersmith D., Odlyzko A. M., Schroeppel R. Descrete logarithms in

GF (p) // Algorithmica. V. 1,1986. P. 1−15. 2] Lenstra A. K, Lenstra H. W. (jr.) The Development of the Number Field

Siev. Lect. Notes in Math. V. 1554. Springer, 1993. 3] McCarthy D. P. «The optimal algorithm to evaluate xn using elementary multiplication methods», Math. Comp., vol. 31, no 137, 1977, pp. 251 —

256.

----------------------- [pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

function DExp (x, n: LongInt): LongInt; label 25, 99; var з: LongInt; begin if n mod 2 (0 then з: = x else з: = 1; 25: n: = n divx 2; if n = 0 then goto 99; x:= x (x; if n mod 2 (0 then з: = c (x; goto 25; 99: DExp: = з; end;

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

ПоказатьСвернуть
Заполнить форму текущей работой