<< Предыдущая

стр. 6
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

a=temp;
}
return b;
}
Работа алгоритма Евклида основана на том, что отображение
(а,Ь) н-)- (а (mod6), ft)
сохраняет наибольший обилий делитель. Неприятность состоит в
том, что компьютерам намного легче складывать и умножать числа,
чем вычислять остатки и частные. Поэтому реализация алгоритма
с приведенным выше отображением обычно не столь эффективна,
как хотелось бы. Однако найден ряд других подходяп];их отображе­
ний, которые также сохраняют НОД, но более экономичны с точки
зрения компьютера, например,
((а — 6)/2,6), если а и 6 нечетные;

(а, Ъ) у-^ ^ («/2, Ь), если а четное, а Ь нечетное;

(а, Ь/2), если а нечетное и Ъ четное.
Напомним, что компьютерам делить на 2 довольно легко, поскольку
в двоичной системе счисления эта операция равносильна простому
сдвигу разрядов^. Последнее отображение дает основу р^ля двоично­
го алгоритма Евклида, который обычно и реализуется в компьютер­
ных программах. По суш;еству, этот алгоритм использует последнее
отображение после того, как выделит из НОД максимально возмож­
ную степень двойки. Следуюш;ий пример на псевдокоде объясняет,
как работает этот алгоритм с данными натуральными числами а и 6.
^ Аналогично делению на 10 в десятичной системе счисления. — Прим. перев.
Глава 1. Сравнения, группы, конечные поля и вероятность

g=i ;
/* Выделение степени двойки из НОД */
while ((аУ.2==0) and (ЬУ.2==0))
{ а=а/2;
b=b/2;
g=2*g;

/* По кра1Йней мере одно из а и b сейчас нечетно •/
while (а != 0)
{ while ((а%2==0) {а=а/2;}
while (Ь7.2==0) {b=b/2;}
/* Сейчас как а так и b нечетны */
if (a>=b) then a=(a-b)/2;
else b=(b-a)/2;
}
Return g*b;

1.3.1.2. Расширенный алгоритм Евклида. С помощью алго­
ритма Евклида, вычисляя НОД (а, 7V), мы можем выяснить, обрати­
мо ли число а по модулю N. Однако мы до сих пор не знаем, как же
найти обратный к а элемент, даже если он существует. Напомним,
что алгоритм Евклида — это последовательное деление с остатком
П-2 = Qi-iri-i + п , г : = О, 1, . . . , т ,
=
где Го = а^ ri = b и Гт = НОД (а, 6). Сейчас мы преобразуем эти
формулы, выразив все остатки п через а и Ь.
Г2 = Го- qm =а- qib,
гз = ri- д2Г2 = Ь- q2{a - qib) ^ -q2a + (1 + qiq2)b,


П_2 = Si-20> + ti-2b,
Ti-i = Si-ia + U-ib,
n = Гг-2 — дг-1П-1 =
= а(5г_2 - qi˜lSi-i) + b{ti-2 - qi-lU-l),




Расширенный алгоритм Евклида по данным целым числам а и b
выдает Гт-, Sm^tm-, так что
Гт = НОД (а, Ь) ^ Sma + tmb.
1.3, Основные алгоритмы

Теперь мы готовы решить исходную задачу по определению обрат­
ного элемента для а по модулю АГ, если это в принципе возможно
сделать. Сначала мы применяем расширенный алгоритм Евклида к
числам а и N VL получаем такие числа d, s и t, что
d = EO^{a,N) =sa-\-tN,
Значит, d = sa + tN — sa (modTV). Теперь видно, что уравнение
ах = 1 (modiV) имеет решение только тогда, когда d = 1. При этом
решение имеет вид х = а˜^ = s.
В качестве примера вычислим обратный элемент к 7 по моду­
лю 19. Положим Го = 7, Г1 = 19 и проведем описанную процедуру.
Г2 = 5 = 19 - 2 • 7,
гз - 2 = 7 - 5 = 7 - (19 - 2 . 7) = - 1 9 + 3 • 7
Г4 = 1 = 5 - 2 . 2 = (19 - 2 . 7) - 2 . (-19 + 3 • 7) = 3 • 19 - 8 • 7.
Отсюда
1 = - 8 - 7 (mod 19),
так что
7"^ = - 8 = 11 (mod 19).

1.3.2. К и т а й с к а я т е о р е м а о б о с т а т к а х
Китайская теорема об остатках или КТО также является очень
древней находкой математики, возраст которой не менее 2000 лет.
Мы будем использовать КТО неоднократно, например, р^ля улучше­
ния процедуры расшифрования в криптосистеме RSA и в некоторых
других протоколах. Говоря неформально, КТО утверждает, что си­
стема уравнений
X = а (modJV),
{ X = b (mod М)
имеет единственное решение по модулю М • N тогда и только тогда,
когда М и N взаимно просты. Кроме того, она дает простой метод
поиска этого решения. Например система


I X = 4 (mod 7),
X = 3 (mod 5)
будет иметь решением ж = 18 (mod 35). Легко убедиться в истинно­
сти найденного ответа, поскольку 18 (mod 7) = 4 и 18 (mod 5) = 3.
Но как он был найден?
40 Глава 1. Сравнения^ группы, конечные поля и вероятность

Сначала мы покажем «на пальцах», как решить эту конкретную
задачу, а затем расскажем об обш;ем методе. Итак, у нас есть урав­
нения
X — А (mod7) и X = Ъ (mod5).
Если X удовлетворяет каждому из них, то для некоторого целого
числа и должны быть выполнены равенства:
х = 4:-\-7и и :r=:3(mod5).
Подставляя первое из соотношений во второе, получаем
4 + 7и = 3 (mod5).
Сделав преобразования, придем к уравнению
2и = 7и = 3-4 = 4 (mods).
Поскольку п о д (2,5) = ПОД (7,5) = 1, мы можем решить последнее
уравнение относительно и. Прежде всего вычислим 2˜^ (mod 5) = 3,
поскольку 2 - 3 = 6 = 1 (mod 5). Затем найдем значение
4 = 2-^-4 (mods) = 3-4 (modS) =2 (modS).
Теперь осталось подставить найденное значение и в выражение для
X и получить решение
х = А-\-7и = 4 + 7-2 = 18.

Система двух уравнений имеет настолько важное значение, что
мы приведем обш;ую формулу ее решения. Предположим, что числа
М и N взаимно просты и дана система


{ X = а (modTV),
X = b (modM).
Сначала определим
Т^М-^ (modTV),
что возможно сделать ввиду предположения о взаимной простоте
чисел М и N. Затем вычисляем
и= {Ь-а)Т (modTV).
Решение по модулю М • N задается формулой
X = а -{- иМ.
1.3. Основные алгоритмы

Чтобы убедиться в верности метода, сделаем проверку.
X (modM) = а + иМ (modM) = а,
=
X {moAN) = а + иМ (modAT) ^ а + (6 - а)ТМ (modiV) ==
- а + (Ь - а)М-^М (mod N) = b.
Вернемся к общему случаю КТО, посвященному системе из более
чем двух уравнений. Пусть mi, . . . , гПг и ai, . . . , а^ — целые числа,
причем все гПг попарно взаимно просты. Нужно найти такой элемент
X по модулю М = mim2 • • • тпг, что
X = Gi (mod ГПг) Д-^я^ всех г.
Китайская теорема об остатках гарантирует существование и един­
ственность решения и дает ответ:
г
X = ^aiMiyi (modM),
i=l
где
Mi = М/гПг, уг = Мг^ (modm,).
В качестве примера найдем число х по модулю М = 1001 =
= 7 • 11 • 13, такое что
X = 5 (mod?),
х^З (mod 11),
х = 10 (mod 13).
Руководствуясь методом, вычисляем
Ml - 143, у1 = 5,
М2 = 91, у2 - 4,
Мз = 77, Уг = 12.
Пользуясь формулой, получаем решение

X = yZ^i^^yi (fiaod'M) r=
г=1
= 715 • 5 + 364 • 3 + 924 • 10 (mod 1001) = 894.

1.3.3. С и м в о л ы Л е ж а н д р а и Я к о б и
Пусть р — простое число, большее 2. Рассмотрим отображение
Глава 1. Сравнения, группы, конечные поля и вероятность

сопоставляющее каждому элементу поля его квадрат. На множестве
ненулевых элементов поля ?р это отображение в точности «два-в-
один», т.е. если из ненулевого элемента а; G Fp можно извлечь ква­
дратный корень, то таких корней у него ровно 2 и, кроме того, ров­
но половина элементов из F* являются полными квадратами. Полные
квадраты в F* называются квадратичными вычетами по модулю
р. Множество всех квадратичных вычетов по модулю р является
подгруппой порядка {р—1)/2 в мультипликативной группе F*. Эле­
менты группы F*, из которых нельзя извлечь квадратный корень,
называются квадратичными невычетами.
Для выявления полных квадратов по простому модулю р вводит­
ся символ Леэюандра



Он равен О, если а делится на р, -f 1, если а — квадратичный вычет
по модулю р, и — 1, если а — квадратичный невычет.
Символ Лежандра легко вычисляется, например, по формуле

Q = а(Р-1)/2 (modp).

Однако использование этой формулы сопряжено с вычислениями
больших степеней и на практике предпочитают пользоваться за­
коном квадратичной взаимности

(Л = fP\ (_1)(р-1)(</-1)/2. (1.1)

Иначе говоря,

I "(f)? если р — ^ = 3 (mod4),
=
р' I (^ J в других случаях.

При вычислении символа Лежандра большую помощь оказывают
следующие дополнительные формулы:




(Л ^ (_1)(Р^-1)/8. (1.4)
1.3. Основные алгоритмы 43

Используя разложение на множители, вычислим символ Лежандра.




Через некоторое время мы изучим более эффективный алгоритм
вычисления символа Лежандра, не зависящий от возможности раз­
ложения числа на множители.
Извлечение квадратного корня из квадратичного вычета а по
модулю р — тоже несложная задача. Сейчас мы приведем метод ее
решения, называемый алгоритмом Шэнкса.
1. Выберем наугад такое п, что

= -1.
Р/
2. Пусть е, ^ — целые числа с нечетным д, удовлетворяющие со­
отношению р — 1 = 2^q.
3. Положим у = п^ (modp), г = е., х = а^^"^^/^ (modp).
4. Положим b = ах^ (modp), х = ах (modp).
5. Пока Ь 7^ 1 (modp) делать:
• найти наименьшее число т , такое что 6^"^ = 1 (modр),
• положить t = у^"^ "^ (modp), у — t^ (modp), г = т^
• положить X = xt (modp), b = by (modp).
6. Вывести X.
Если p = 3 (mod 4), то для извлечения корня из а можно исполь­
зовать формулу
X = а^Р^^^/^ (modp),
которая имеет неоспоримое преимущество перед общим алгоритмом
Шэнкса ввиду ее явности и эффективности. Формула дает правиль­
ный ответ потому, что
^2 ^ ^{р+1)/2 ^ ^(р-1)/2 . о ^ ( « у а = а.

Последнее равенство здесь верно ввиду предположения о том, что
а — квадратичный вычет, а значит, соответствующий символ Ле­
жандра равен 1.
Символ Лежандра определен только в случае простого знаме­
нателя. Если же знаменатель составной, то вводится символ Якоби^
Глава 1. Сравнения, группы, конечные поля и вероятность

обобщающий символ Лежандра. Пусть п — нечетно^ число, большее



Символ Якоби определяется через символы Лежандра простых де­
лителей числа п следующим образом

<< Предыдущая

стр. 6
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>