Полиномы деления

редактировать

В математике полиномы деления обеспечивают способ вычисления кратных точек на эллиптических кривых и изучать поля, порожденные точками кручения. Они играют центральную роль в изучении подсчета точек на эллиптических кривых в алгоритме Шуфа.

Содержание

1 Определение
2 Свойства
3 См. Также
4 Ссылки

Определение

Набор многочленов деления представляет собой последовательность многочленов от $Z [x, y, A, B] {\ displaystyle \ mathbb {Z} [ x, y, A, B]}$ ${\ mathbb {Z} } [x, y, A, B]$ с $x, y, A, B {\ displaystyle x, y, A, B}$ $x, y, A, B$ свободными переменными, которые рекурсивно определяются :

ψ 0 = 0 {\ displaystyle \ psi _ {0} = 0}

\ psi _ {{0}} = 0

ψ 1 = 1 {\ displaystyle \ psi _ {1} = 1}

\ psi _ {{1}} = 1

ψ 2 = 2 y {\ displaystyle \ psi _ {2} = 2y}

\ psi _ {{2}} = 2y

ψ 3 = 3 x 4 + 6 A x 2 + 12 B x - A 2 {\ displaystyle \ psi _ {3} = 3x ^ {4} + 6Ax ^ {2 } + 12Bx-A ^ {2}}

\ psi _ {{3}} = 3x ^ {{4}} + 6Ax ^ {{2}} + 12Bx-A ^ {{2}}

ψ 4 = 4 y (x 6 + 5 A x 4 + 20 B x 3 - 5 A 2 x 2 - 4 AB x - 8 B 2 - A 3) { \ displaystyle \ psi _ {4} = 4y (x ^ {6} + 5Ax ^ {4} + 20Bx ^ {3} -5A ^ {2} x ^ {2} -4ABx-8B ^ {2} -A ^ {3})}

\ psi _ {{4}} = 4y (x ^ {{6}} + 5Ax ^ {{4}} + 20Bx ^ {{3}} - 5A ^ {{2}} x ^ {{2}} - 4ABx-8B ^ {{2}} - A ^ {{3}})

⋮ {\ displaystyle \ vdots}

\ vdots

ψ 2 m + 1 = ψ m + 2 ψ m 3 - ψ m - 1 ψ m + 1 3 для m ≥ 2 {\ displaystyle \ psi _ {2m + 1} = \ psi _ {m + 2} \ psi _ {m} ^ {3} - \ psi _ {m-1 } \ psi _ {m + 1} ^ {3} {\ text {for}} m \ geq 2}

\ psi _ {{2m + 1}} = \ psi _ {{m + 2 }} \ psi _ {{m}} ^ {{3}} - \ psi _ {{m-1}} \ psi _ {{m + 1}} ^ {{3}} {\ text {for}} m \ geq 2

ψ 2 m = (ψ m 2 y) ⋅ (ψ m + 2 ψ m - 1 2 - ψ м - 2 ψ м + 1 2) для m ≥ 3 {\ displaystyle \ psi _ {2m} = \ left ({\ frac {\ psi _ {m}} {2y}} \ right) \ cdot (\ psi _ {m + 2} \ psi _ {m-1} ^ {2} - \ psi _ {m-2} \ psi _ {m + 1} ^ {2}) {\ text {for}} m \ geq 3}

\ psi _ {{2m}} = \ left ({\ frac {\ psi _ {{m}}} {2y}} \ right) \ cdot (\ psi _ {{m + 2}} \ psi _ {{m-1 }} ^ {{2}} - \ psi _ {{m-2}} \ psi _ {{m + 1}} ^ {{2}}) {\ text {for}} m \ geq 3

Многочлен $ψ n {\ displaystyle \ psi _ {n}}$ $\psi_n$ называется многочленом n деления.

Свойства

На практике задается $y 2 = x 3 + A x + B {\ displaystyle y ^ {2} = x ^ {3} + Ax + B}$ $y ^ {2} = x ^ {3} + Ax + B$ , а затем $ψ 2 m + 1 ∈ Z [x, A, B] {\ displaystyle \ psi _ {2m + 1} \ in \ mathbb {Z} [x, A, B]}$ $\ psi _ {{2m + 1}} \ in {\ mathbb {Z}} [x, A, B]$ и $ψ 2 m ∈ 2 Y Z [x, A, B] {\ displaystyle \ psi _ {2m} \ in 2y \ mathbb {Z} [x, A, B]}$ $\ psi _ {{2m}} \ in 2y {\ mathbb {Z}} [x, A, B]$ .
Многочлены деления образуют общую последовательность эллиптической делимости над кольцом $Q [x, y, A, B] / (y 2 - x 3 - A x - B) {\ displaystyle \ mathbb {Q} [x, y, A, B] / (y ^ {2} -x ^ {3} -Ax-B)}$ ${\ mathbb {Q}} [x, y, A, B] / (y ^ { 2} -x ^ {3} -Ax-B)$ .
Если эллиптическая кривая $E {\ displaystyle E}$ $E$ дается в форме Вейерштрасса $y 2 = x 3 + A x + B {\ displaystyle y ^ {2} = x ^ {3} + Ax + B}$ $y ^ {2} = x ^ {3} + Ax + B$ над некоторым полем $K {\ displaystyle K}$ $K$ , т.е. $A, B ∈ K {\ displaystyle A, B \ in K}$ $A, B \ in K$ , можно использовать эти значения $A, B {\ displaystyle A, B}$ $A, B$ и рассмотреть полиномы деления в координатном кольце $E { \ Displaystyle E}$ $E$ . Корни $ψ 2 n + 1 {\ displaystyle \ psi _ {2n + 1}}$ $\ psi _ {{2n + 1}}$ - это $x {\ displaystyle x}$ $x$ -координаты точки $E [2 n + 1] ∖ {O} {\ displaystyle E [2n + 1] \ setminus \ {O \}}$ $E [2n + 1] \ setminus \ { O \}$ , где $E [2 n + 1 ] {\ displaystyle E [2n + 1]}$ $E [2n + 1]$ - это $(2 n + 1) th {\ displaystyle (2n + 1) ^ {\ text {th}}}$ $(2n + 1) ^ {{{\ text {th}}}}$ кручение подгруппа из $E {\ displaystyle E}$ $E$ . Точно так же корни $ψ 2 n / y {\ displaystyle \ psi _ {2n} / y}$ $\ psi _ {{2n}} / y$ - это координаты $x {\ displaystyle x}$ $x$ . из точек $E [2 n] ∖ E [2] {\ displaystyle E [2n] \ setminus E [2]}$ $E [2n] \ setminus E [2]$ .
Дана точка $P = (x P, y P) { \ displaystyle P = (x_ {P}, y_ {P})}$ $P = (x_ {P }, y_ {P})$ на эллиптической кривой $E: y 2 = x 3 + A x + B {\ displaystyle E: y ^ {2 } = x ^ {3} + Ax + B}$ $E: y ^ {2} = x ^ {3} + Ax + B$ над некоторым полем $K {\ displaystyle K}$ $K$ , мы можем выразить координаты n, кратного $P {\ displaystyle P}$ $P$ в терминах полиномов деления:

n P = (ϕ n (x) ψ n 2 (x), ω n (x, y) ψ n 3 (x, у)) знак равно (Икс - ψ N - 1 ψ N + 1 ψ N 2 (x), ψ 2 N (x, y) 2 ψ N 4 (x)) {\ displaystyle nP = \ left ({\ frac { \ phi _ {n} (x)} {\ psi _ {n} ^ {2} (x)}}, {\ frac {\ omega _ {n} (x, y)} {\ psi _ {n} ^ {3} (x, y)}} \ right) = \ left (x - {\ frac {\ psi _ {n-1} \ psi _ {n + 1}} {\ psi _ {n} ^ { 2} (x)}}, {\ frac {\ psi _ {2n} (x, y)} {2 \ psi _ {n} ^ {4} (x)}} \ right)}

nP = \ left ({\ frac {\ phi _ {{n}} (x)} {\ psi _ {{n}} ^ {{2}} (x)}}, {\ frac {\ omega _ {{n}}) (x, y)} {\ psi _ {{n}} ^ {{3}} (x, y)}} \ right) = \ left (x - {\ frac {\ psi _ {{n-1}) } \ psi _ {{n + 1}}} {\ psi _ {{n}} ^ {{2}} (x)}}, {\ frac {\ psi _ {{2n}} (x, y) } {2 \ psi _ {{n}} ^ {{4}} (x)}} \ right)

где

ϕ N {\ Displaystyle \ phi _ {n}}

\ phi _ {{n}}

ω n {\ displa ystyle \ omega _ {n}}

\ omega _ {n}

определяется следующим образом:

ϕ n = x ψ n 2 - ψ n + 1 ψ n - 1, {\ displaystyle \ phi _ {n} = x \ psi _ {n} ^ {2} - \ psi _ {n + 1} \ psi _ {n-1},}

\ phi _ {{n}} = x \ psi _ {{n}} ^ {{2}} - \ psi _ {{n + 1}} \ psi _ {{n-1}},

ω n = ψ n + 2 ψ n - 1 2 - ψ n - 2 ψ n + 1 2 4 г. {\ displaystyle \ omega _ {n} = {\ frac {\ psi _ {n + 2} \ psi _ {n-1} ^ {2} - \ psi _ {n-2} \ psi _ {n + 1 } ^ {2}} {4y}}.}

\ omega _ {{n}} = {\ frac {\ psi _ {{n + 2}} \ psi _ {{n-1}} ^ {{2}} - \ psi _ {{n-2}} \ psi _ {{n + 1}} ^ {{2}}} {4y}}.

Использование соотношения между $ψ 2 m {\ displaystyle \ psi _ {2m}}$ $\ psi _ {{2m}}$ и $ψ 2 m + 1 {\ displaystyle \ psi _ {2m + 1}}$ $\ psi _ {{2m + 1}}$ , наряду с уравнением кривой, функции $ψ n 2 {\ displaystyle \ psi _ {n} ^ {2}}$ $\ psi _ {{n}} ^ {{2}}$ , $ψ 2 ny, ψ 2 n + 1 {\ displaystyle {\ frac {\ psi _ {2n}} {y}}, \ psi _ {2n + 1}}$ ${\ frac {\ psi _ {{2n}}} {y}}, \ psi _ {{2n + 1}}$ , $ϕ n {\ displaystyle \ phi _ {n}}$ $\ phi _ {{n}}$ все в $K [x] {\ displaystyle K [x]}$ $K [x]$ .

Пусть $p>3 {\ displaystyle p>3}$ $p>3$ быть простым и пусть $E: y 2 = x 3 + A x + B {\ displaystyle E: y ^ {2} = x ^ {3} + Ax + B}$ $E: y ^ {2} = x ^ {3} + Ax + B$ быть эллиптической кривой над конечное поле $F p {\ displaystyle \ mathbb {F} _ {p}}$ $\ mathbb {F} _ {p}$ , т.е. $A, B ∈ F p {\ displaystyle A, B \ in \ mathbb { F} _ {p}}$ $A, B \ in {\ mathbb {F}} _ {p}$ . $ℓ {\ displaystyle \ ell}$ $\ ell$ -to группа rsion из $E {\ displaystyle E}$ $E$ поверх $F ¯ p {\ displaystyle {\ bar {\ mathbb {F}}} _ {p}}$ ${\ bar {{\ mathbb {F}}}} _ {p}$ изоморфен $Z / ℓ × Z / ℓ {\ displaystyle \ mathbb {Z} / \ ell \ times \ mathbb {Z} / \ ell}$ ${\ mathbb {Z}} / \ ell \ times {\ mathbb {Z}} / \ ell$ if $ℓ ≠ p {\ displaystyle \ ell \ neq p}$ $\ ell \ neq p$ и $Z / ℓ {\ displaystyle \ mathbb {Z} / \ ell}$ ${\ mathbb {Z}} / \ ell$ или ${0} {\ displaystyle \ {0 \}}$ $\ {0 \}$ , если $ℓ = p {\ displaystyle \ ell = p}$ $\ ell = p$ . Следовательно, степень $ψ ℓ {\ displaystyle \ psi _ {\ ell}}$ $\ psi _ {\ ell}$ равна либо $1 2 (l 2 - 1) {\ displaystyle {\ frac {1} {2}} (l ^ {2} -1)}$ ${\ frac {1} {2}} (l ^ {2} -1)$ , $1 2 (l - 1) {\ displaystyle {\ frac {1} {2}} (l-1)}$ ${\ frac {1} {2}} (l -1)$ , или 0.

Рене Шуф заметил, что работа по модулю $ℓ {\ displaystyle \ ell}$ $\ ell$ полинома деления позволяет работать со всеми $ℓ {\ displaystyle \ ell }$ $\ ell$ -точки кручения одновременно. Это широко используется в алгоритме Шуфа для подсчета точек на эллиптических кривых.

См. Также

алгоритм Шуфа

Ссылки

A. Энге: Эллиптические кривые и их приложения в криптографии: Введение. Kluwer Academic Publishers, Dordrecht, 1999.
Н. Коблиц: курс теории чисел и криптографии, выпускные тексты по математике. № 114, Springer-Verlag, 1987. Второе издание, 1994 г.
Мюллер: Die Berechnung der Punktanzahl von elliptischen kurvenüber endlichen Primkörpern. Дипломная работа. Universität des Saarlandes, Saarbrücken, 1991.
G. Musiker: алгоритм Шуфа для подсчета точек на $E (F q) {\ displaystyle E (\ mathbb {F} _ {q})}$ $E (\ mathbb {F} _ {q})$ . Доступно по адресу http://www-math.mit.edu/~musiker/schoof.pdf
Schoof: эллиптические кривые над конечными полями и вычисление квадратного корня mod p. Математика. Comp., 44 (170): 483–494, 1985. Доступно на http://www.mat.uniroma2.it/~schoof/ctpts.pdf
R. Schoof: Подсчет точек на эллиптических кривых над конечными полями. J. Theor. Nombres Bordeaux 7: 219–254, 1995. Доступно на http://www.mat.uniroma2.it/~schoof/ctg.pdf
L. К. Вашингтон: Эллиптические кривые: теория чисел и криптография. Chapman Hall / CRC, New York, 2003.
J. Сильверман: Арифметика эллиптических кривых, Springer-Verlag, GTM 106, 1986.