ЧЕБЫШЕВСКИЙ СБОНИК Том 11 Выпуск 1 (2010) Труды VII Международной конеренции Алгебра и теория чисел: современные проблемы и приложения, посвященной памяти проессора Анатолия Алексеевича Карацубы О НЕКОТОЫХ СВОЙСТВАХ ЭЛЛИПТИЧЕСКОЙ КИВОЙ В ФОМЕ ЯКОБИ А. Ю. Нестеренко (г. Москва) nesterenko_a_ymail.ru Пусть p > 3 простое число и ? 6? 0, 1 (mod p). ассмотрим эллиптическую кривую, заданную в орме Якоби однородным сравнением E? : y 2z ? x(x ? z)(x ? ?z) (mod p). (1) Основным результатом предлагаемой работы является доказательство следующего результата. Теорема 1. Пусть значения ?1, ?, 1 ? ? являются квадратичными выче- тами по модулю простого числа p. Тогда порядки групп точек эллиптических кривых E? , E 1 , E1?? , E 1 , E ? , E ??1 , (2) 1?? ? ??1 ? совпадают. Данный результат известен и его доказательство может быть найдено, например, в книге [2?. Метод доказательства основывается на вычислении в явном виде и сравнении j -инвариантов кривых из (2). Предлагаемый нами подход к доказательству теоремы основан на других принципах. Мы показываем, что порядок группы точек эллиптической кривой (1) совпадает с порядком группы точек эллиптической кривой, заданной системой сравнений u21 + u22 ? 1 (mod p), S? := (3) ?u21 + u23 = 1 (mod p), где ? 6? 0, 1 (mod p). Далее мы предъявляем в явном виде элементарные изоморизмы между кривыми S? , S1 , ? S1?? , S 1 1?? , S ? ??1 , S ??1 , ? (4) откуда следует, что порядки групп точек кривых (4) совпадают, из чего следует доказательство сормулированной теоремы 1. Докажем следующее утверждение О НЕКОТОЫХ СВОЙСТВАХ ЭЛЛИПТИЧЕСКОЙ КИВОЙ ЯКОБИ 203 Теорема 2. Для порядков рассматриваемых групп эллиптических кривых S? и E? выполнено равенство |S? | = |E? |. ты. Для доказательство теоремы 2 нам потребуются вспомогательные результаЛемма 1. Пусть p нечетное простое число, тогда выполнены следующие равенства p?1 X если p ? 1 6 | m, (mod p). если p ? 1 | m, u=0 p?1 2 X u + bu + c ? 1, если p 6 |d, = p ? 1, если p|d, p u=0 m u ? 0, ?1, где d = b2 ? 4c дискриминант многочлена u2 + bu + c. Доказательство. См. [4?, гл. II, џ10, п.4, утверждение III. Лемма 2. Пусть m натуральное, ? отличное от нуля и единицы целое число. Тогда у многочленов (x ? 1)m (x ? ?)m и (1 ? x)m (1 ? ?x)m коэициенты при xm совпадают и равны Dm (?) = (?1) m m X (Ckm )2 ?k , (5) k=0 где Ckm = m! биномиальный коэициент. k!(m ? k)! Доказательство. Из равенств (x ? 1)m (x ? ?)m = ! m ! m X X (?1)m?i Cim xi (?1)m?j Cjm ?m?j xj = i=0 j=0 = 2m X X (?1)2m?k Cim Cjm ?m?j xk , k=0 i+j=k m следует, учетом равенства Cim = Cm?i , что коэициент при xm многочлена (x ? 1)m (x ? ?)m равен X (?1) i+j=m m Cim Cjm ?m?j = (?1) m m X i=0 (Cim )2 ?i = Dm (?). 204 А. Ю. НЕСТЕЕНКО Аналогично, из равенств (1 ? x)m (1 ? ?x)m = (x ? 1)m (?x ? 1)m = ! m ! m X X (?1)m?i Cim xi (?1)m?j Cjm ?j xj = i=0 j=0 = 2m X X (?1)2m?k Cim Cjm ?j xk , k=0 i+j=k получаем, что коэициент многочлена (1 ? x)m (1 ? ?x)m равен Dm (?). Теорема 3 (Хассе). Пусть p > 3 простое число и f (x) многочлен третьей степени, не имеющий кратных кратных корней по модулю p. Тогда порядок группы точек эллиптической кривой E : y 2 ? f (x) (mod p) удовлетворяет неравенству ? |E| = p + 1 + t, где |t| < 2 p. Доказательство. См. [4?, гл. II, џ10, п.6. или [1?, глава 10. Очевидным следствием теоремы Хассе является следующее утверждение. Лемма 3. Пусть p > 3 простое число и f (x) многочлен третьей степени, не имеющий кратных кратных корней по модулю p, тогда p?1 X f (x) ? < 2 p. p x=0 Перейдем к доказательству сормулированной нами теоремы 2. Для порядка группы точек эллиптической кривой E? , заданной уравнением (1), выполнено равенство |E? | = 1 + p?1 X x=0 1+ x(x ? 1)(x ? ?) p ?1+ ? p?1 X x p?1 2 x=0 (x ? 1) p?1 2 (x ? ?) p?1 2 (mod p). P p?1 i Положим m = и обозначим h(x) = (x?1)m (x??)m = 2m i=0 hi x . Тогда, 2 используя первое утверждение леммы 1 и утверждение леммы 2, получим p?1 X x=0 m m m x (x ? 1) (x ? ?) = 2m X 2m X x=0 i=0 ?? hi xm+i ? X p?1|m+i, i=0,...,2m hi ? ?hm ? ?D p?1 (?) (mod p). 2 О НЕКОТОЫХ СВОЙСТВАХ ЭЛЛИПТИЧЕСКОЙ КИВОЙ ЯКОБИ 205 Сопоставляя последние два сравнения, получаем |E? | ? 1 ? D p?1 (?) 2 (6) (mod p). Теперь рассмотрим систему сравнений (3). Для |S? | выполнено равенство |S? | = N1 + N? , где N1 число конечных точек, а N? число бесконечно удаленных точек, равное количеству решений системы u21 + u22 ? 0 (mod p), ?u21 + u23 ? 0 (mod p). Верно равенство ?? ?1 ?? ? ?1 N? = 1 + 1+ =1+ + + . p p p p p (7) Для числа N1 конечных точек выполнено равенство p?1 X 1 ? u2 1 ? ?u2 1+ = N1 = 1+ p p u=0 X X p?1 p?1 p?1 X 1 ? u2 1 ? ?u2 (1 ? u2 ) (1 ? ?u2 ) =p+ + + = p p p u=0 u=0 u=0 = p + Q1 + Q2 + Q3 . Применяя второе утверждение леммы 1 получаем равенства p?1 X 1 ? u2 p?1 ?1 X u2 ? 1 ?1 Q1 = = =? , p p p p u=0 u=0 p?1 p?1 X 1 ? ?u2 ?? X u2 ? ??1 ?? Q2 = = =? , p p u=0 p p u=0 откуда следует равенство N1 = p ? ?1 p ? ?? p + Q3 . Суммируя выражения для N? и N1 , получаем выражение для |S? | ? |S? | = p + 1 + + Q3 . p (8) (9) 206 А. Ю. НЕСТЕЕНКО P p?1 i Вспомним, что m = , и обозначим g(u) = (1 ? u)m (1 ? ?u)m = 2m i=0 gi u . 2 Учитывая первое утверждение леммы 1 и утверждение второй леммы, запишем для суммы Q3 сравнение Q3 = p?1 X (1 ? u2 ) (1 ? ?u2 ) u=0 p = ? p?1 X u=0 p?1 2m X X 1 ? u2 gj u2j u=0 j=0 ?? X 1 ? ?u2 m (mod p) = (mod p) ? gj p?1|2j, j=0,...,2m m (mod p) ? ?gm ? g2m (mod p). Из определения многочлена g(u) следует, что p?1 ? m 2 g2m = ? = ? ? (mod p). p ? (mod p). Подставляя полученное сравнение в Тогда Q3 ? ?D p?1 (?) ? 2 p равенство (9) и сравнивая его с (6), получим |S? | ? 1 ? D p?1 (?) ? |E? | (mod p). 2 Пока мы доказали утверждение более слабое, чем сормулированное в условии теоремы 2. Из теоремы Хассе тривиально следует, что |E? | не превосходит величины в 2p. Из равенства (9) и определения Q3 также следует, что |S? | не превосходит величины в 2p. Следовательно, значения |E? | и |S? | либо совпадают, либо отличаются ровно на величину p. Обозначим |E? | = p + 1 + t, тогда из теоремы Хассе и сравнения (6) следует, что ? |t| 6 2 p, |t| ? D p?1 (?) (mod p) 2 Оценим сверху величину |Q3 |. Сделаем замену переменных u= x x?1 или u= u , u?1 которая не определена в точке x = u = 1. Поскольку 1 ? u2 (1 ? 2x)(x2 (1 ? ?) ? 2x + 1) , 1 ? ?u2 = (x ? 1)4 (10) (11) О НЕКОТОЫХ СВОЙСТВАХ ЭЛЛИПТИЧЕСКОЙ КИВОЙ ЯКОБИ 207 то Q3 = p?1 X (1 ? u2 ) (1 ? ?u2 ) u=0 (1 ? u2 ) (1 ? ?u2 ) = = p p u=0, u6=1 X p?1 p?1 X (1 ? 2x) ((1 ? ?)x2 ? 2x + 1) f (x) ? = ? , p p p x=0 x=0, x6=1 p?1 X где f (x) = ((1 ? ?)x2 ? 2x + 1) (1 ? 2x) многочлен1 третьей степени. Воспользовавшись леммой 3 получаем неравенство p?1 ? X f (x) ? (12) 6 2 p, p + Q3 = p x=0 из которого, учитывая (9), (10), получим неравенство ? ? ||S? | ? |E? || = + Q3 + t 6 4 p. p Следовательно значения |E? | и |S? | совпадают. Теорема 2 доказана. Для построения отображений между кривыми из (4) нам потребуется рассмотреть конечное расширение поля из p элементов. Определим элементы i, ?1 , ?2 как решения сравнений i2 ? ?1 (mod p), ?21 ? ? (mod p), ?22 ? 1 ? ? (mod p). В случае, если одно из значений ?1, ?, 1?? не является квадратичным вычетом по модулю p, то соответствующий элемент принадлежит расширению поля из p элементов. Используя введенные обозначения, в явном виде предъявим отображения, задающие взаимно однозначное соответствие между точками эллиптической кривой S? и точками кривых из (4). S1 : ? v1 = ?1 u2 , v2 = ?2 u4 , v3 = ?2 u1 , v4 = u3 , S1?? : v1 = u3 , v2 = i?1 u2 , v3 = ?1 ?2 u1 , v4 = ?2 u4 , S 1 : v1 = u3 , v2 = ?1 u1 , v3 = i?1 ?2 u2 , v4 = u4 , 1?? u3 S ? : v1 = u2 , v2 = u1 , v3 = , v4 = u4 , ??1 ?2 S ??1 : v1 = i?1 u2 , v2 = u3 , v3 = ?2 u1 , v4 = ?2 u4 , ? 1 Корни многочлена f (x) равны 1 1? 1? 2 , 1+ ? , 1? ? . При ? 6= 0, 1 все корни различны. 208 А. Ю. НЕСТЕЕНКО В случае, когда значения ?1, ?, 1 ? ? являются квадратичными вычетом по модулю p, приведенные отображения определены над конечным полем из p элементов и переводят рациональные точки кривой S? в рациональные точки кривых из (4). Следовательно, порядки групп точек этих кривых совпадают. Из последнего замечания и утверждения теоремы 2, вытекает доказательство сормулированной в начале статьи теоремы 1. СПИСОК ЦИТИОВАННОЙ ЛИТЕАТУЫ [1? ельонд А.О., Линник Ю.В. Элементарные методы в теории чисел. М.:Физматгиз, 1962. 272 с. [2? Ленг С. Эллиптические ункции. М.:Наука, 1984. 312 . [3? Нестеренко А.Ю. О числе решений одной системы сравнений // Депонировано во ВИНИТИ. ќ 454-в2009. 2009. 17 стр. [4? Хассе . Лекции по теории чисел. М.:ИЛ, 1953. 527 . Московский педагогический государственный университет Поступило 13.05.2010
Автор
1/--страниц