Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
10. Знаменатель дзета-функции равен (1 —T)(I — рТ) во всех случаях; в следующей таблице указаны числители для р = 5,7, 11, 13:
у7= X3-X 1 + 2Т + 5Т2 1 + 7Т2 1 + 11Т2 1-6Т+13Т2 у2 = X3 - 1 1 + 5Т2 1 - 4Т + 7Т2 1 + 1IT2 1 - 2Т + 13Т2
252
ОТВЕТЫ К УПРАЖНЕНИЯМ
11. В обоих случаях уравнение не имеет решений (х, у) в Fp. Поэтому единственной Fp-точкой является точка в бесконечности. Числители дзета-функций равны, соответственно, 1 - 2Т + 2Т2 и 1 - ЗТ + ЗТ2. Тогда NT = N((1 + і)г - 1) и, соответственно, N((1 -I- ui)r — 1), где Uj = (—1 -I- гЧ/з)/2.
§VI.2
1. Выбирать случайно элементы из Y4, пока не попадется такой д, что
2. Пусть і ? Г, соответствует т. а) Положить /(х) = х3 — х. Заметить, что в точности одно из значений /(х),/( —х) = —/(г) — квадрат. Положим у = /(х)(, + 1)/4. Показать затем, что либо (х, у), либо ( — х,у) — точка на кривой, б) Выбрать любой у и положить х = (j/2 + y/)(2_')/3 (если у = 0 или —1, то положить і = 0); показать, что (х,у) лежит на кривой.
3. а) Последовательность точек (х,у) — следующая: (562,576),(581,395), (484, 214), (501, 220), (1,0), (1, 0), (144, 565). б) ICANT (I can't).
4. а) Группа E (mod р) содержит нециклическую группу порядка 4 с тремя точками порядка 2. б) E (mod р) содержит точку порядка 2, следовательно, ее порядок четен.
5. Использовать формулы из примера 5 в § 1. а) Использовать сравнение по модулю 3, чтобы показать, что в обоих случаях (г четно и г нечетно) имеем 3|JVr. б) Если 4|г, то Nr = {2Г12 - I)2 = (2r/4 - 1)2(2Г/4 + I)2; Nr делится на (г/4)-битовое простое число тогда и только тогда, когда г/4 — простое число, для которого 27"/4 — 1 есть простое число Мерсенна; Nr делится на (г/4 -|- 1)-битовое простое число тогда и только тогда, когда г/4 = 2* и 22 +1 — простое число Ферма.
6. а) Fp-точки образуют собственную подгруппу Fpr-точек (по теореме Хассе), и эта подгруппа имеет более одного элемента (также по теореме Хассе). Таким образом, TV1- имеет собственный делитель, б) В обоих случаях пусть E задано уравнением j/2 + у = х3 — х + 1; легко проверить, что ни над F2, ни над F3 у кривой нет точек, кроме точки в бесконечности. Таким образом, рассуждения, проведенные в п. а), не применимы. Можно показать, что если р = 2, то N2 = 5, N3 — 13, Ni = 41, N7 = 113, TVn = 2113 (заметим, что дзета-функция равна (1 — 2Т + 2Т2)/((1 — T)(I — 2T)); для г простого Nr — простое число тогда и только тогда, когда так называемое «комплексное число Мерсенна» (1 + г)Т — 1 является простым гауссовым целым числом, или, что эквивалентно, тогд^и только тогда, когда 2Г + 1 — (2)2^г + 1^2 — простое число, где (^) — символ Лежан-дра); если р — 3, то N2 = 7, Ni = 271, N7 = 2269 (здесь дзета-функция равна (1 - ЗТ + ЗТ2)/((1 - T)(I - ЗТ))).
7. а) у2 + у = X3 -|- а, где а — любой элемент F4, не принадлежащий F2.
б) Дзета-функция равна (1 — 4Т + 4Т2)/((1 — T)(I — 4T)) и обратные элементы к обоим корням числителя равны 2; далее использовать замечание в конце §1.
в) Удвоенная точка (x,j/) — это (х4,?/4) (возведение в 4-ю степень есть «отображение Фробениуса», т.е. образующий группы Галуа F4>- над F4). г) «г-кратное» удвоение любой точки — это (х4 ,j/4 ) = (х,у), т.е. любая P Є ІЗ удовлетворяет соотношению 2ГР = Р.
8. а) Воспользоваться тем, что х принадлежит F2 в том и только том случае, когда X2 = х, а также тем, что (а + Ь)2 = а2 + Ь2 в поле характеристики 2. б) Отображение z —> 1 + z задает взаимно однозначное соответствие элементов с tr z = 0 и элементов с trz = 1. в) Выбрать случайным образом х Є F2r, затем подставить z = х3 + ах + Ь в g(z); если z оказывается среди тех 50% элементов,
ОТВЕТЫ К УПРАЖНЕНИЯМ
253
для которых tr г = 0, то получаем точку (x,g(z)) на кривой.
9. При работе с E по модулю р пользуются теми же формулами (4)-(5) из § 1. Точка в бесконечности получается тогда, когда складываются точки меньшей кратности кР = к\Р 4- АгР, где к\Р и к^Р — точки, которые после приведения по модулю р имеют одинаковые z-координаты и противоположные по знаку у-координаты. Это эквивалентно условиям 1)-2) в тексте упражнения.
10. Знаменатель точки SP делится на 23, поэтому P (mod 23) согласно упражнению 9 имеет порядок 8 на ? (mod 23). Однако из теоремы Хассе вытекает, что E (mod 23) имеет более восьми точек.
11. (676,182), (385,703), (595,454), (212,625), (261,87), (77,369), (126,100), (66,589), (551,606), (501,530), (97,91), (733,110), (63,313), (380,530).
§VI.3
1. а) 1 - 1/д. б) 1 — 1 /д.
3. а) Если га = 22 +1 — простое число, то любое а с (~) = — 1 обладает указанным свойством. Относительно а = 3,5,7 см. упражнение 15 к §11.2. С
„к-і
другой стороны, если р — собственный простои делитель га и если а = —1,
к к-1
то 22 ,а не 22 , является кратным порядка элемента а по модулю Pj, т.е. его
порядок равен 22 = га — 1 > р — 1, что невозможно, б) Предположим сначала, что га = 2Р — 1 есть простое число. Группа E (mod га) состоит из 2Р точек, см. упражнение 7 а) к § VI. 1. То, что эта группа — циклическая, следует из того, что имеется только две точки порядка 2: действительно, многочлен х3 + х имеет лишь один корень по модулю га. Отсюда следует, что любые из тех 50% точек, которые порождают E (mod га) (т.е. не получаются удвоением какой-либо точки), обладают свойствами 1)~2). Обратно, предположим, что га имеет собственный простой делитель (. Если бы P обладала свойствами 1)-2), то на E (mod /) порядок P делил бы 2Р, но не 2Р~1, т.е. он был бы равен 2Р. Но тогда 2Р = га + 1 было бы делителем порядка группы E (mod I), что противоречит теореме Хассе, утверждающей, что этот порядок не превосходит /-+¦ 2^/1+ 1. Для порождения случайных точек на E (mod га) выберем случайным образом х Є Z/raZ. Если окажется, что 6 = х3 + х есть квадрат по модулю га, то полагаем у = б(п + 1)/4, и тогда у2 = Ь ¦ (>(n-1)/2 = X3 + X (см. замечание 1 в конце § И. 2).
