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

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

ОГЛАВЛЕНИЕ

Следующая >>


.^) \V\) \Р2/ \Vk)
Символ Якоби можно вычислять так же, как и символ Лежандра,
опираясь на тождество, выведенное из закона квадратичной взаим­
ности:

о- 2 у fn ( m o d a i ) \ ^_j^(ai-i)(n-i)/4^

где а = 2^а\ и а\ нечетно. Полезно помнить еще несколько формул,
справедливых при нечетном п:

- ) = ^•
п
( ! ) = (-')'"""".

(v)=(-•)'"-"'•
Все это дает нам быстрый алгоритм вычисления символа Якоби и,
соответственно, символа Лежандра, как его частный случай, без
утомительного разложения на множители. Единственно, что нужно
сделать, это выделить максимальную степень двойки:



Напомним, что символ Лежандра f ^ j сообщает нам, является
ли а полным квадратом по модулю простого числа р. Увы, сим­
вол Якоби (^) ничего не утверждает о возможности извлечения
квадратного корня из а по модулю составного числа п. Если а в
действительности квадрат по модулю п, то символ Якоби будет ра­
вен -Ы. Однако из равенства (^) = +1 нельзя сделать вывод о том,
что а — полный квадрат. Несмотря на благоприятное равенство,
квадратный корень из а может не извлекаться!
Пусть п ^ 3 — нечетное число. Обозначим через Qn подмноже­
ство полных квадратов в {Ъ/пЪУ:
Qn = {х^ (modn)l X е (Z/nZ)*}.
1,3. Основные алгоритмы

С другой стороны, пусть Jn обозначает подмножество элементов в
{Ъ/пЪу.^ чей символ Якоби равен 1, т.е.

Jn = {xe{Zlnzy\ (^) = i}-
Таким образом, множество всех псевдо-квадратов^ — это разность
Jn\Qn- Криптографов интересуют два относительно простых част­
ных случая: когда п простое число или произведение двух простых
чисел.
- Если п — простое число, то


• #<5„ = (п - 1)/2.
- Если п = pq — произведение двух простых, то


• #Qn = #{Jn - Qn) = {р- Щд - 1)/4.
Как мы еще увидим, множества Jn и Qn сыграют заметную роль в
ряде криптографических алгоритмов и протоколов, особенно когда
п — произведение двух простых чисел.
В заключение параграфа выясним, как извлечь корень из числа
по модулю составного п = р • q. Предположим, нам надо найти ква­
дратный корень из а по модулю п. Вообще говоря, разложение числа
п на простые множители может быть неизвестно, но, допустим, мы
его знаем. Будем также считать, что а действительно полный ква­
драт по модулю п, т. е.
^а\ (а\

Сначала мы извлечем корень из а по модулю р и обозначим его
через Sp. Затем извлечем корень из а по модулю q и назовем его Sq.
Наконец, для вычисления искомого корня мы применяем китайскую
теорему об остатках к системе
X =^ Sp ( m o d p ) ,
(1.5)
X = Sq ( m o d ^ ) .

Вычислим, например, корень из а = 217 по модулю п = 221 = 13 • 17.
Квадратные корни из а по модулям 13 и 17 соответственно равны
513 = 3 и 517 = 8. Опираясь на китайскую теорему об остатках.
^То есть квадратичных невычетов, чей символ Якоби равен 1. — Прим. перев.
Глава 1. Сравнения, группы, конечные поля и вероятность

получаем s = 42, Проверим правильность найденного решения пря­
мыми вычислениями:
^2 = 422 = 217 (mod221).
На самом деле, суш;ествуют еще три разных квадратных корня из
числа 217 по модулю п = 221, поскольку п имеет два простых де­
лителя. Чтобы их отыскать, достаточно применить КТО к трем
системам вида (1.5) с
sn = 8;
513 = 10,
sn = 9;
s\z = 3,
=9
S13 = 10, Sn
и получить полный ответ:
42, 94, 127, 179.

1.4. Вероятность
в какой-то момент нам потребуется понимание основ элементарной
теории вероятностей. Сейчас мы кратко дадим теоретические све­
дения и разберем несколько примеров. Для большинства читателей
изложенный здесь материал знаком по учебе в ВУЗе.
Случайной величиной называется переменная X, принимающая
свои значения с некоторой вероятностью. Если переменная X при­
нимает значение s с вероятностью 0,01, мы будем писать
р(Х = 5) = 0,01.
Предположим, например, что Т — случайная величина, представля­
ющая результат подбрасывания симметричной монеты. Так как по­
явление орла или решки равновероятны, то

р{Т = орел) = - , р{Т = решка) = - .
в качестве другого примера рассмотрим английский текст и
обозначим через Е случайную величину, принимающую буквенные
значения. Статистический анализ большого количества информа­
ции позволяет оценить относительные вероятности появления той
или иной буквы в тексте:
р{Е=^а) = 0,082,


р{Е = е) = 0,127,
p{E^z) =0,001.
1.4- Вероятность

Если X — дискретная случайная величина^, то множество вероят­
ностей всех ее значений называют распределением вероятностей^
а функцию р{Х — х\ сопоставляющую значению переменной соот­
ветствующую вероятность — плотностью распределения вероят­
ностей, В общем случае имеют место следующие свойства:
р{Х = х)^0, ^ р ( Х = х) = 1.
X


Классический пример, иллюстрирующий теорию вероятностей,
связан со стандартной колодой в 52 карты. Следуя традиции, рас­
скажем о нем и мы. Обозначим через V случайную величину появле­
ния карты определенного достоинства при сдаче, через S — масть
карты, а через С — ее цвет. Тогда

р{С — красный) — - ,

р{у ^ туз треф) = —,

p{S = трефа) = - .

Пусть X и Y — две случайные величины с распределением веро­
ятностей р{Х = х) и p{Y = у). Вероятность одновременного ра­
венства X = X и У = у называется совместной вероятностью
р{Х = x,Y = у). Так, если X = С и? = S,TO

р{С = красньщ S = трефа) — О, р{С = красныщ S = бубна) = - ,

р{С — красньщ S = черва) = - , р{С = красныщ S — пика) — О,

р{С — черныщ S = трефа) = - , р{С = черный^ S = бубна) = О,

р{С = черный^ S = черва) = О, р{С = черный^ S = пика) = - .
Две случайные величины X и Y называются независимыми^ если
для всех возможных значений х и у имеет место равенство
р{Х = x,Y = y)=p{X = x)- p{Y = у).
Таким образом, случайные величины С и 5 не являются независи­
мыми. В качестве примера независимых величин рассмотрим экс­
перимент, во время которого подбрасываются две правильные мо­
неты последовательно друг за другом. Пусть Ti — итог подбрасы­
вания первой монеты, а Т2 — второй. Поскольку в силу физических
^То есть ее множество значений конечно или счетно. — Прим. перев.
Глава 1. Сравнения, группы, конечные поля и вероятность

законов результат подбрасывания первой монеты никак не может
сказаться на подбрасывании второй, можно предположить, что Т\
и Т2 — независимые случайные величины. Это подтверждается со­
вместным распределением вероятностей:

p{Ti = орел^Т2 = орел) — - , p{Ti = орел,Т2 = решка) = - ,

p(Ti = ретка^Т2 = орел) = - , p{Ti = решка^Т2 = решка) = -.


1.4.1. Теорема Байеса
Условной вероятностью р{Х = x\Y = у) случайных величин X
и Y называется вероятность того, что переменная X принимает
значение гг, если известно, что Y = у.
Возвращаясь к примеру с колодой карт, имеем
p{S = пика\С = красный) = О
и
p(^V — туз пик\С = черный) = •—.
26
Первое равенство следует из того, что пика имеет черный цвет и
указанные события не могут произойти одновременно. Во втором
случае условие С = черный ограничивает выбор карты ровно напо­
ловину, и поскольку у нас есть только один туз пик среди 26 воз­
можных карт, соответствующая вероятность равна ^ .
Сформулируем одну из самых значимых теорем элементарной
теории вероятностей

Теорема 1.7. (Теорема Байеса.) Если р{У = у) > О, то
р{Х = х)-р{? = у\Х = х)
р{Х = x\Y = у)
р{У = у)
p{X=^x,Y = y)
р{У = у) '

Применим теорему Байеса к нашему примеру с картами.
p{S = пика^ С = красный)
p{S = пика\С = красный) =
р{С = красный)
р-'
= 0.1-1 =0.
1.4- Вероятность 49

р{у = туз пик^ С = черный)
p{V = туз пик\С = черный) =
р{С = черный)
-' 2 1
А-J_
52 \2j 52 ˜ 26"
Для независимых случайных величин имеем
p{X = x\Y = y)=p{X = x),
Т. е. значение величины X не зависит от того, чему равна случайная
величина У.

1.4.2, П а р а д о к с д н е й р о ж д е н и я
Еще один полезный результат из элементарной теории вероятно­
стей, который нам потребуется в дальнейшем, называется парадок­
сом дней рождения. Допустим, в ящике находятся m шариков разно­
го цвета. Из ящика не гляд^я достают один шарик, записывают его
цвет, возвращают его в ящик и тянут снова. Вероятность того, что
после п вытаскиваний нам попадется хотя бы два шарика одного
цвета, равна


где
т^"") = т{т - 1){т - 2) • • • ( т - п + 1).
Если m достаточно большое, то ожидаемое число шариков, которые
нам придется просмотреть до первого совпадения, равно yj^-
Чтобы понять причину названия парадокса, оценим вероятность
совпадения дней рождений двух людей из некоторой группы. Мно­
гие наивно полагают, что такая вероятность крайне мала, считая
практически невозможным совпадение чьей-то даты рождения с его
собственной. Однако, воспользовавшись выписанной формулой, лег­
ко убедиться, что вероятность совпадения дат рождений у двух лю­
дей из 23 равна
365(2'»

На самом ]\^дл(д вероятность совпадения быстро возрастает с ростом
количества людей, из которых производится выборка. Так она равна
0,706, если выбираем среди 30 человек, и 0,999 999 6, если среди 100.

К р а т к о е с о д е р ж а н и е главы

- Группа — это множество с ассоциативной операцией и едини­
цей, все элементы которого обратимы. Арифметика остатков
Глава 1. Сравнения, группы, конечные поля и вероятность

вместе с операцией сложения по определенному модулю доста­
вляет примеры групп. Хотя с умножением необходимо быть
осторожным, мы можем определить группу и относительно
умножения по модулю.
Кольцо — это множество с двумя операциями, обладающими
теми же свойствами, что умножение и сложение натуральных
чисел. Остатки от деления на целое число — пример кольца.
Поле — это коммутативное кольцо, в котором каждый ненуле­
вой элемент обладает мультипликативным обратным. Кольцо
вычетов по модулю простого числа — пример поля.
Обратить элемент в кольце вычетов можно на основе расши­
ренного алгоритма Евклида.
Система линейных уравнений в арифметике остатков может
быть решена с помощью китайской теоремы об остатках.
Полные квадраты по модулю простого числа выявляются сим­
волом Лежандра. Квадратные корни можно эффективно извле­
кать по алгоритму Шэнкса.
Полные квадраты и квадратные корни по модулю составного
числа п могут быть эффективно вычислены, если известны все
делители числа п.
Теорема Байеса позволяет вычислять условные вероятности.

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

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

ОГЛАВЛЕНИЕ

Следующая >>