Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Определение 5.24 (Первообразный корень). Мультипликативный порождающий элемент группы (Fpn)* называется первообразным корнем поля Fp«.
Глава 5. Алгебраические основы 205
Теорема 5.12. Пусть п — положительное целое число, а п — 1 = тхт2 ...Гк — полное разложение числа п — 1 на простые множители (некоторые простые множители могут повторяться). Следовательно число п является простым тогда и только тогда, когда существует положительное целое число а <п такое, что а™-1 = l(modп) и а(п~1)/'4 j?l(mod п) при г = 1,2,..., к.
Доказательство. (=Ф-) Если число п — простое, то по теореме 5.11 группа (?п)* — циклическая и содержит порождающий элемент, который является (п — 1)-м корнем единицы. Обозначим этот корень буквой а. Число а удовлетворяет условиям теоремы.
(<=) Пусть целое число а < п удовлетворяет условиям теоремы. Тогда числа а, а2,..., а11"1 являются решениями уравнения zn-1 — 1 = 0(mod п). Для любого числа I ^ г < j ^ п — 1 должно выполняться условие агфа?'(modп). Предположим противоположное: а?~г = l(modn) для некоторых чисел г, j, удовлетворяющих условию 0 < j — г < п — 1. Тогда по определению 5.9 выполняется условие ord(a)|z — j\n — 1, что противоречит условию теоремы. Как известно, {а} — мультипликативная группа, состоящая из п — 1 элементов (относительно умножения по модулю п). Количество элементов этой группы не превышает ф(п). Следовательно, ф(п) = п — 1. Таким образом, по определению функции Эйлера число п — простое (определение 5.11). ?
В теореме 5.12 предполагается, что существует эффективный алгоритм нахождения первообразного корня по модулю простого числа р, т.е. порождающего элемента группы Z* (алгоритм 5.1).
Алгоритм 5.1. Случайный первообразный корень по модулю простого числа ВВОД: р: простое число; gj, q2, ¦ ¦ ¦, Як- все простые множители числа р — 1. ВЫВОД: д: случайный первообразный корень по модулю простого числа.
PrimitiveRoot(p, q\, q2,..., Як)-
1. Извлечь дЕи[2,р— 1].
2. for (г = 1,г+ +,к) do
if (g(P-1)/* = l(modp)) return(PrimitiveRoot(p,q\,q2,...,%)).
3. return(g).
По теореме 5.2.4 в группе Z* существует ровно ф{р — 1) элементов порядка р — 1. Они являются порождающими элементами группы. Следовательно, количество рекурсивных вызовов алгоритма 5.1 удовлетворяет условию [198]
206
Часть II. Математические основы
Поскольку количество простых множителей числа р — 1 не превосходит logp, временная сложность алгоритма имеет порядок Os((l°gp)4 log logp).
5.5 Группы, построенные по точкам на эллиптической кривой
В современной криптографии важную роль играют группы, построенные по точкам эллиптических кривых (elliptic curves). Применение этих групп в криптографии с открытым ключом впервые было предложено Миллером (МШег) [203] и Коблицем (Koblitz) [166].
В криптографии рассматриваются эллиптические кривые, определенные на конечных алгебраических структурах, например, на конечных полях. Для простоты изложения будем изучать только простые поля Fp, характеристика которых больше трех. В этом случае эллиптическая кривая представляет собой множество точек Р = (х, у) следующего уравнения:
Е : у2 = х3 + ах + 6(modp), (5.5.1)
где числа а и b являются константами в поле Fp(p > 3), удовлетворяющими условию 4а3+27Ь2 ф O(modp)1. Для того чтобы точки множества Е образовывали группу, в него включается точка О. Этот дополнительный элемент называется бесконечно удаленной точкой (point at infinity) и представляется в виде
0 = (ж, со).
Множество Е можно представить так.
Е = {Р = (х, у) | х, у е Fp — решения уравнения (5.5.1)} U {О}. (5.5.2)
Это множество точек образует группу с операцией, которую удобно обозначить символом "+". Смысл этой операции будет раскрыт позднее.
Обозначим через f(x) кубический полином, стоящий в правой части уравнения (5-5.1). Если полином f(x) является приводимым над полем Fp, то для того, чтобы элемент ? 6 Fp был нулем полинома /(ж) (те. /(?) = 0(modp)), точка (?, 0) должна принадлежать множеству Е. В свое время мы покажем, что относительно групповой операции "+" эти точки имеют порядок 2. Поскольку f(x) — кубический полином, существует по крайней мере три таких точки (одна или три в зависимости от приводимости полинома f(x) над полем Fp — см. упражнение 5.13).
'Подробное объяснение см. в определении 5.25.
Глава 5. Алгебраические основы
207
Все другие точки, отличающиеся от О, можно получить из точек п е Fp, таких что числа /(77) ф 0(modp) являются квадратичными вычетами в поле Fp (т.е. квадратами по модулю р (раздел 6.5)). Для каждой такой точки 77 существуют два разных решения у (каждый квадратичный вычет в поле Fp имеет два квадратных корня по модулю р — см. следствие 6.2). Поскольку величина /(77) является константой, эти два корня равны y/f (77) и — y/f (77). Итак, две точки решения, соответствующие элементу 77, можно обозначить как (77, y/f (77)) и (77, — y/f (77)).
Итак, на кривой Е[?р) лежат точки О, (?,0), (77, y/f (77)) и (77, -л//(«))> где элементы ? и 77 из поля Fp удовлетворяют условиям /(?) = 0(modp) и /(77) — квадратичный вычет в поле Fp.
