Научная литература
booksshare.net -> Добавить материал -> Математика -> Коблиц Н. -> "Курс теории чисел и криптографии" -> 104

Курс теории чисел и криптографии - Коблиц Н.

Коблиц Н. Курс теории чисел и криптографии — Москва: Научное изд-во ТВП, 2001. — 254 c.
Скачать (прямая ссылка): theory-chisel-kriptographii.djvu
Предыдущая << 1 .. 98 99 100 101 102 103 < 104 > 105 106 107 108 109 110 .. 125 >> Следующая


Эллиптические кривые — редукция по модулю п. До конца этого параграфа мы будем обозначать через п нечетное составное число и через р (пока неизвестный) простой делитель п. Будем считать, что р > 3. Пусть т — целое число и xi,x2 — два рациональных числа со знаменателями, взаимно простыми с т; будем писать Xi = X2 (mod m), если числитель разности xi — X2, записанной в виде несократимой дроби, делится на т. Для любого рационального числа Xi со знаменателем, взаимно простым с т, существует такое однозначно определенное целое х2 между 0 и т — 1 («наименьший неотрицательный вычет»), что Xi = X2 (mod т). Иногда мы будем обозначать наименьший неотрицательный вычет как хг (mod т).

2 3

Пусть даны уравнение вида у = х + ах + 6, а, 6 Є Z, и удовлетворяющая ему точка P = (х,у). На практике эллиптическая кривая E вместе с точкой P будут порождаться некоторым «случайным» образом. Например, можно выбрать три случайных целых числа а,х,у из

2 3

некоторой области и положить затем 6 = у — х —ах. Будем предполагать, что кубический многочлен X3 + ах -+ 6 имеет различные корни,

3 2

т. е. что Aa +276 ф 0; это условие выполняется почти всегда, если коэффициенты выбираются описанным выше случайным образом. Для

простоты мы предполагаем также в дальнейшем, что 4а + 276 не

з

имеет с п общих множителей; другими словами, что х + ах + 6 не имеет кратных корней по модулю р для любого простого делителя р числа п. Практически, выбрав а, 6, мы можем проверить это, найдя НОД (Aa3 + 27Ь2,п). Если это число больше 1, то либо n|(4a3 + 27б2) (и тогда нам следует выбрать другие а и 6), либо мы уже обнаружили нетривиальный делитель п (и тогда задача решена). Итак, мы будем

3 2

предполагать, что НОД (4а + 276 , n) = 1.

Пусть нам нужно найти кратную кР для точки P методом повторного удвоения, изложенным в § VI. 2. Есть много различных способов сделать это за O(logAr) шагов, каждый из которых — либо удвоение точки, либо сложение двух различных точек. Можно, например, записать к в двоичной системе счисления: к = а0 + ai2 + • • • + am_i2m_1

220

ГЛ. VI. ЭЛЛИПТИЧЕСКИЕ КРИВЫЕ

и затем последовательно удваивать Р, прибавляя 23P к уже накопленной сумме, если соответствующий бит uj равен 1. Можно также разложить к в произведение простых чисел Z15Z2,... (расположенных, скажем, в неубывающем порядке) и затем последовательно вычислять Z1P, Z2(Z1P) и т.д. Здесь каждая точка IjPj, где Pj = lj_xlj_2 ¦hP, вычисляется повторным удвоением с использованием двоичной записи чисел Ij.

Пусть выбран какой-либо из таких приемов вычисления кратных кР. Будем рассматривать точку P и все ее кратные по модулю п. Это означает, что мы полагаем P (mod п) = (х (mod п),у (mod п)) и всякий раз при вычислении кратной точки кР мы фактически вычисляем лишь вычеты ее координат по модулю п. Все вычисления при удвоении и сложении точек можно проводить по модулю п, если выполнено нетривиальное условие: все знаменатели должны быть взаимно просты с п.

Предложение VI. 4.1. Пусть E — эллиптическая кривая с

2 3 3 2

уравнением у = X + ах + 6, где a,b ? Z и НОД (4а + 276 , п) = 1. Пусть P1 и P2 — две точки на Е, у которых знаменатели координат взаимно просты с п, и P1 ф -P2. Тогда P1 + P2 ? E имеет координаты, у которых знаменатели взаимно просты с п, в том и только том случае, когда у п нет простого делителя р, для которого сумма точек P1 (mod р) и P2 (mod р) на эллиптической кривой E (mod р) была бы равна точке в бесконечности О (mod р) ? E (mod р). Здесь E (mod р) обозначает эллиптическую кривую[над Fp, полученную приведением по модулю р коэффициентов уравнения у2 = х3 + ах + Ь.

Доказательство. Пусть все точки P1 = (х\, ^1), P2 = (х2, у2) и Pi + P2 ? E поначалу имеют координаты со знаменателями, взаимно простыми с п. Требуется доказать, что для любого простого делителя р числа п сумма P1 (mod р) + P2 (mod р) ф О (mod р). Если Xi ф х2 (mod р), то в соответствии с описанием закона сложения на E (mod р) мы сразу же заключаем, что P1 (mod р) + P2 (mod р) ф О (mod р). Теперь предположим, что х\ = X2 (mod р). При P1 = P2 координаты точки P1 + P2 = 2P1 определяются формулой (5) из §1, и 2P1 (mod р) находится по той же формуле с заменой каждого члена его вычетом по модулю р. Нам нужно показать, что знаменатель 2^1 дроби в правой части (5) не делится на р. Но если бы он делился на р, то 3x1 + а делилось бы на р (так как знаменатель ж-координаты точки 2P1 на р не делится). Тогда Х\ был бы корнем по модулю р как мно-

3 2

гочлена X + ах + 6, так и его производной Зх + а, что противоречит нашему предположению об отсутствии кратных корней по модулю р у этого многочлена. Теперь пусть P1 ф P2. Так как X2 = Х\ (mod р)

§ 4. РАЗЛОЖЕНИЕ HA МНОЖИТЕЛИ

221

и X2 ф Xi, мы можем записать ж2 = X1 + ргх, где г ^ 1 выбрано так, что ни числитель, ни знаменатель х не делятся на р. По предположению знаменатели координат точки P1 + P2 не делятся на р, поэтому из формулы (4) в § 1 следует, что у2 имеет вид уі + р у. С другой стороны,

2/2 = Oi + pTxf + a(xi + ртх) + b
Предыдущая << 1 .. 98 99 100 101 102 103 < 104 > 105 106 107 108 109 110 .. 125 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed