Последовательность эллиптической делимости - Elliptic divisibility sequence

В математике последовательность эллиптической делимости (EDS) это последовательность целых чисел удовлетворяющее нелинейному рекурсивному соотношению, возникающему из полиномы деления на эллиптические кривые. EDS были впервые определены, а их арифметические свойства изучены Морган Уорд^[1] в 1940-е гг. Они привлекали к себе только спорадическое внимание примерно до 2000 года, когда EDS были рассмотрены как класс нелинейных повторений, которые более поддаются анализу, чем большинство подобных последовательностей. Такая управляемость обусловлена, прежде всего, тесной связью между EDS и эллиптическими кривыми. В дополнение к внутреннему интересу, который EDS имеет к теории чисел, EDS имеет приложения и в других областях математики, включая логика и криптография.

Определение

A (невырожденный) последовательность эллиптической делимости (EDS) представляет собой последовательность целых чисел $(W п) п \geq 1$ определяется рекурсивно четырьмя начальными значениями $W 1$ , $W 2$ , $W 3$ , $W 4$ , с $W 1 W 2 W 3$ ≠ 0 и с последующими значениями, определяемыми по формулам

{ displaystyle { begin {align} W_ {2n + 1} W_ {1} ^ {3} & = W_ {n + 2} W_ {n} ^ {3} -W_ {n + 1} ^ {3} W_ {n-1}, qquad n geq 2, W_ {2n} W_ {2} W_ {1} ^ {2} & = W_ {n + 2} W_ {n} W_ {n-1} ^ {2} -W_ {n} W_ {n-2} W_ {n + 1} ^ {2}, qquad n geq 3, конец {выровнено}}}

Можно показать, что если $W 1$ разделяет каждый из $W 2$ , $W 3$ , $W 4$ и если дальше $W 2$ разделяет $W 4$ , то каждый член $W п$ в последовательности целое число.

Свойство делимости

EDS - это последовательность делимости в том смысле, что

{ displaystyle m mid n Longrightarrow W_ {m} mid W_ {n}.}

В частности, каждый член в EDS делится на $W 1$ , soEDS часто нормализованный иметь $W 1$ = 1 путем деления каждого члена на начальный член.

Любые три целых числа $б$ , $c$ , $d$ с $d$ делится на $б$ привести к нормализованному EDS при настройке

{ displaystyle W_ {1} = 1, quad W_ {2} = b, quad W_ {3} = c, quad W_ {4} = d.}

Неочевидно, но можно доказать, что условие $б$ | $d$ достаточно, чтобы гарантировать, что каждое завершение последовательности является целым числом.

Общая рекурсия

Основным свойством последовательностей эллиптической делимости является то, что они удовлетворяют общему рекурсивному соотношению

{ displaystyle W_ {n + m} W_ {nm} W_ {r} ^ {2} = W_ {n + r} W_ {nr} W_ {m} ^ {2} -W_ {m + r} W_ {mr } W_ {n} ^ {2} quad { text {для всех}} quad n> m> r.}

(Эта формула часто применяется с $р$ = 1 и $W 1$ = 1.)

Неособые ЭЦП

В дискриминант нормализованной ЭЦП - количество

{ displaystyle Delta = W_ {4} W_ {2} ^ {15} -W_ {3} ^ {3} W_ {2} ^ {12} + 3W_ {4} ^ {2} W_ {2} ^ { 10} -20W_ {4} W_ {3} ^ {3} W_ {2} ^ {7} + 3W_ {4} ^ {3} W_ {2} ^ {5} + 16W_ {3} ^ {6} W_ {2} ^ {4} + 8W_ {4} ^ {2} W_ {3} ^ {3} W_ {2} ^ {2} + W_ {4} ^ {4}.}

ЭЦП - это неособый если его дискриминант отличен от нуля.

Примеры

Простым примером ЭЦП является последовательность натуральных чисел 1, 2, 3,…. Другой интересный пример: (последовательность A006709 в OEIS ) 1, 3, 8, 21, 55, 144, 377, 987,… состоящий из каждого второго члена в Последовательность Фибоначчи, начиная со второго срока. Однако обе эти последовательности удовлетворяют линейной рекуррентности, и обе являются сингулярными EDS. Примером неособого ЭЦП является (последовательность A006769 в OEIS )

{ Displaystyle { begin {align} & 1, , 1, , - 1, , 1, , 2, , - 1, , - 3, , - 5, , 7, , - 4, , - 23, , 29, , 59, , 129, & - 314, , - 65, , 1529, , - 3689, , - 8209, , - 16264, точки. конец {выровнено}}}

Периодичность ЭЦП

Последовательность $(А п) п \geq 1$ как говорят периодическийесли есть номер $N \geq 1$ так что $А п + н$ = $А п$ для каждого $п$ ≥ 1. Если невырожденный ЭЦП $(W п) п \geq 1$ периодичен, то один из его членов обращается в нуль. Наименьший $р$ ≥ 1 с $W р$ = 0 называется ранг явления ЭЦП. Глубокая теорема Мазура^[2]означает, что если ранг появления EDS конечен, то он удовлетворяет $р$ ≤ 10 или $р$ = 12.

Эллиптические кривые и точки, связанные с EDS

Уорд доказывает, что связанный с неособым EDS ( $W п$ ) - эллиптическая кривая $E$ /Q и точка $п$ ε $E$ (Q) такие, что

{ displaystyle W_ {n} = psi _ {n} (P) qquad { text {для всех}} ~ n geq 1.}

Здесь ψ $п$ это $п$ полином деления из $E$ ; корни ψ $п$ ненулевые пункты порядка $п$ на $E$ . Есть сложная формула^[3]за $E$ и $п$ с точки зрения $W 1$ , $W 2$ , $W 3$ , и $W 4$ .

Существует альтернативное определение EDS, которое напрямую использует эллиптические кривые и дает последовательность, которая с точностью до знака почти удовлетворяет рекурсии EDS. Это определение начинается с эллиптической кривой $E$ /Q задается уравнением Вейерштрасса и точкой неторсии $п$ ε $E$ (Q). Один пишет $Икс$ -координаты кратных $п$ в качестве

{ displaystyle x (nP) = { frac {A_ {n}} {D_ {n} ^ {2}}} quad { text {with}} ~ gcd (A_ {n}, D_ {n}) ) = 1 ~ { text {and}} ~ D_ {n} geq 1.}

Тогда последовательность ( $D п$ ) также называется последовательность эллиптической делимости. Это последовательность делимости, и существует целое число $k$ так что подпоследовательность (± $D нк$ )_{$п$ ≥ 1} (с соответствующим выбором знаков) - ЭЦП в более раннем понимании.

Рост EDS

Позволять $(W п) п \geq 1$ быть неособым EDSt, который не является периодическим. Тогда последовательность возрастает квадратично экспоненциально в том смысле, что существует положительная постоянная $час$ такой, что

{ displaystyle lim _ {n to infty} { frac { log | W_ {n} |} {n ^ {2}}} = h> 0.}

Номер $час$ это каноническая высота точки на эллиптической кривой, связанной с EDS.

Простые числа и примитивные делители в EDS

Предполагается, что неособая СЭД содержит лишь конечное число простых чисел^[4]Однако все, кроме конечного числа членов неособой EDS, допускают примитивный простой делитель.^[5]Таким образом, для всех, кроме конечного множества $п$ , есть простое число $п$ такой, что $п$ разделяет $W п$ , но $п$ не разделяет $W м$ для всех $м$ < $п$ . Это утверждение является аналогом Теорема Жигмонди.

EDS над конечными полями

EDS над конечным полем F_$q$или, в более общем смысле, над любым полем - это последовательность элементов этого поля, удовлетворяющая рекурсии EDS. EDS над конечным полем всегда периодичен и, следовательно, имеет ранг видения. $р$ . Срок действия ЭЦП закончился F_$q$ тогда имеет вид $rt$ , куда $р$ и $т$ удовлетворить

{ displaystyle r leq left ({ sqrt {q}} + 1 right) ^ {2} quad { text {and}} quad t mid q-1.}

Точнее есть элементы $А$ и $B$ в F_$q$^* такой, что

{ displaystyle W_ {ri + j} = W_ {j} cdot A ^ {ij} cdot B ^ {j ^ {2}} quad { text {для всех}} ~ i geq 0 ~ { текст {и все}} ~ j geq 1.}

Ценности $А$ и $B$ связаны сТейт-спаривание точки на соответствующей эллиптической кривой.

Применение ЭЦП

Бьорн Пунен^[6]применил EDS к логике. Он использует существование примитивных делителей в EDS на эллиптических кривых ранга один, чтобы доказать неразрешимость Десятая проблема Гильберта над некоторыми кольцами целых чисел.

Кэтрин Штанге^[7]применил EDS и их обобщения более высокого ранга, названные эллиптические сети криптографии. Она показывает, как можно использовать EDS для вычисления стоимости Пары Вейля и Тейта на эллиптических кривых над конечными полями. Эти пары имеют множество применений в криптография на основе пар.

Дальнейший материал

Г. Эверест, А. ван дер Поортен, И. Шпарлински, Т. Уорд. Повторяющиеся последовательности, том 104 Математические обзоры и монографии. Американское математическое общество, Провиденс, Род-Айленд, 2003. ISBN 0-8218-3387-1. (Глава 10 посвящена EDS.)
Р. Шипси. Последовательности эллиптической делимости. Кандидатская диссертация, Голдсмит-колледж (Лондонский университет), 2000 г.
К. Штанге. Эллиптические сети. Кандидатская диссертация, Университет Брауна, 2008 г.
С. Сварт. Последовательности, относящиеся к эллиптическим кривым. Кандидатская диссертация, Роял Холлоуэй (Лондонский университет), 2003 г.

внешняя ссылка

[Ward-1] Морган Уорд, Мемуары об эллиптических последовательностях делимости, Амер. J. Math. 70 (1948), 31–74.

[Mazur-2] Б. Мазур. Модульные кривые и идеал Эйзенштейна, Inst. Hautes Études Sci. Publ. Математика. 47:33–186, 1977.

[SilvermanStephens-3] Эта формула принадлежит Уорду. См. Приложение к Дж. Х. Сильверману и Н. Стивенсу. Знак последовательности эллиптической делимости. J. Ramanujan Math. Soc., 21(1):1–17, 2006.

[Einsiedler-4] М. Эйнзидлер, Дж. Эверест и Т. Уорд. Простые числа в последовательностях эллиптической делимости.LMS J. Comput. Математика., 4: 1–13 (электрон.), 2001.

[Silverman-5] Дж. Х. Сильверман. Критерий Вифериха и abc-гипотеза.J. Теория чисел, 30(2):226–237, 1988.

[6] Б. Пунен. Использование эллиптических кривых ранга один к неразрешимости десятой проблемы Гильберта о кольцах целых алгебраических чисел. В Алгоритмическая теория чисел (Сидней, 2002), том 2369 г. Конспект лекций по вычислительной технике. Sci., страницы 33–42. Спрингер, Берлин, 2002.

[Stange-7] К. Штанге. Спаривание Тейта через эллиптические сети. В Криптография на основе пар (Токио, 2007 г.), том 4575 из Конспект лекций по вычислительной технике. Sci. Спрингер, Берлин, 2007.

[1]

[2]

[3]

[4]

[5]

[6]

[7]