1 сем / it_ebook1

ЭE 205 CD 157 9D 221 DD 252 FC 1069 042D |

98

Приложение Д. Элементы теории чисел

Каноническим разложением числа m называется разложение его на простые сомножители в виде m = pα1 1 pα2 2 · · · pαkk , где p1, p2, . . . , pk

— все различные простые делители числа m, а α1, α2, . . . , αk — целые положительные числа.

Функцией Эйлера называется, отображение ϕ: N → N,

ϕ(m) = pα1 1−1(p1 − 1)pα2 2−1(p2 − 1) · · · pαkk−1(pk − 1),

это весьма трудоемкий способ. Получим решения искомого уравнения через формулу для решения эквивалентного уравнения ax − my = 1.

По алгоритму Евклида для получения НОД двух заданных чисел нужно одно число делить на другое, затем делить делитель на получаемый остаток до тех, пока остаток не станет равным нулю. Последний больший нуля остаток будет искомым НОД.

Для чисел a и m последовательность шагов алгоритма Евклида выглядит как

a = mq0 + a1, m = a1q1 + a2, a1 = a2q2 + a3,

. . .

an−2 = an−1qn−1 + an, an−1 = anqn,

a

где a1, a2, . . . , an — остатки. Разложение m в цепную дробь по после-

99

Обозначим за Pk/Qk дробь, получаемую из приведенной цепной дроби отбрасыванием членов с индексами, большими k. Например, P0/Q0 = q0, P1/Q1 = q0+1/q1 = (q0q1+1)/q1 и т.д. Числитель, Pk, и знаменатель, Qk, можно вычислять рекуррентно по следующим формулам:

P−2 = 0, P−1 = 1, Q−2 = 1, Q−1 = 0;

при k > 0 Pk = qkPk−1 + Pk−2, Qk = qkQk−1 + Qk−2.

По определению Pn = a и Qn = m. Кроме того,

Fn = PnQn−1−Pn−1Qn = (qnPn−1+Pn−2)Qn−1−Pn−1(qnQn−1+Qn−2) = = −Pn−1Qn−2 +Pn−2Qn−1 = −Fn−1 = · · · = Fn−2 = · · · = (−1)n+1F−1 = = (−1)n+1(P−1Q−2 − P−2Q−1) = (−1)n+1

или

(−1)n+1PnQn−1 − Pn−1(−1)n+1Qn = 1,

что означает

a(−1)n+1Qn−1 − m(−1)n+1Pn−1 = 1,

т.е. x = (−1)n−1Qn−1 и y = (−1)n−1Pn−1.

Процесс получения числителей и знаменателей удобно оформить в виде таблицы:

Таким образом, корни уравнения ax ≡ 1 (mod m) вычисляются

100

Таким образом, искомый x равен 151925.

Гипотеза. Задача разложения целого числа с заданным числом разрядов на множители является труднорешаемой*.

На сегодняшний день существуют весьма быстрые алгоритмы для проверки данного числа на простоту, но для разложения 200-значного числа на множители лучшим современным компьютерам по лучшим современным алгоритмам может потребоваться миллиарды лет.

Эта гипотеза лежит в основе методов Диффи-Хеллмана.

* Задача называется труднорешаемой, если время ее решения зависит от объема входных данных по экспоненциальному закону и не может быть сведено к полиномиальному

101

Приложение Е. Используемые обозначения

P (A) — вероятность события A.

P (A/B) — вероятность события A, если известно, что событие B произошло. Условная вероятность.

P (A, B) — вероятность одновременного наступления событий A и

B.

N — множество натуральных чисел.

Z2 — множество из 0 и 1 — {0, 1}. R — множество вещественных чисел. R2 — числовая плоскость.

P

i xi — сумма xi по всем возможным значениям индекса i.

P

i,j xij — сумма xij по всем возможным значениям пар индексов

i и j.

Cnk — биномиальный коэффициент в формуле бинома Ньютона

или число возможных разных выборок k элементов из множества из n

a − b делится на n нацело.

f: A → B — функция f с областью определения A и областью, содержащей все значения f, B.

f ◦ g — композиция функций f и g, т.е. (f ◦ g)(x) = f(g(x)).

(X, +, ×) — поле над множеством X с аддитивной операцией + и мультипликативной операцией ×.

102

Приложение Ж. Список литературы

1.Биркгоф Г., Барти Т. Современная прикладная алгебра — М.: Мир, 1976.

2.Блейхер Р. Теория и практика кодов, контролирующих ошибки —

М.: Мир, 1986.

3.Борн Г. Форматы данных — Киев: Торгово-издательское бюро

BHV, 1995.

4.Букчин Л. В., Безрукий ю. Л. Дисковая подсистема IBM-совме- стимых персональных компьютеров — М.: МИКАП, 1993.

5.Винер Н. Кибернетика — М.: Наука, 1983.

6.Воробьев Н. Н. Признаки делимости — М.: Наука, 1988.

7.Глушков В. М. Основы безбумажной информатики — М.: Наука, 1987.

8.Джордж Ф. Основы кибернетики — М.: Радио и Связь, 1984.

9.Кенцл Т. Форматы файлов Internet — СПб: Питер, 1997.

10.Нельсон М. Верификация файлов //“Журнал д-ра Добба” 1/93.

11.Нефедов В. Н., Осипова В. А. Курс дискретной математики —

М.: МАИ, 1992.

12.Нечаев В. И. Элементы криптографии — М.: Высшая школа, 1999.

13.Мастрюков Д. Алгоритмы сжатия информации //“Монитор”

7/93–6/94.

14.Питерсон Р., Уэлдон Э. Коды, исправляющие ошибки — М.: Мир, 1976.

15.Перспективы развития вычислительной техники: в 11 кн.: Справочное пособие/Под ред. ю. М. Смирнова. Кн. 9. — М.: Высшая школа, 1989.

16.Розанов ю. А. Лекции по теории вероятностей — М.: Наука, 1986.

17.Титце У., Шенк К. Полупроводниковая схемотехника — М.: Мир, 1983.

18.Чисар И., К¨ернер Я. Теория информации — М.: Мир, 1985.

19.Шеннон К. Работы по теории информации и кибернетики — М.:

Издательство иностранной литературы, 1963.

20.Яглом А., Яглом И. Вероятность и информация — М.: Наука, 1973.

21.Введение в криптографию /Под общей редакцией В. В. Ященко.

—М.: МЦНМО—ЧеРо, 2000.

22.HTML 4.01 Specification /Edited by D. Ragget, A. L. Hors, I. Jacobs

—W3C: http://www.w3c.org/TR/REC-html401-19991224, 1999.

23.The Unicode Standard, Version 3.0 — Addison Wesley Longman Publisher, 2000, ISBN 0-201-61633-5.

103

Приложение З. Предметный указатель

104

105

106

Приложение И. Именной указатель

107