Рейтинг:1

В чем смысл $F_{p^k}$ и эллиптической кривой над ней $E(F_{p^k})$?

флаг cn

В криптографии, основанной на спаривании, будет конечное поле $F_{p^k}$ куда $р$ это простое число и $к$ является целым числом. Эллиптическая кривая строится на этом конечном поле как $E(F_{p^k})$.

Например, пусть $Е$ быть эллиптической кривой $Y^2 = X^3 + аХ + б $ над $ F_{q^k}$. Каково значение $ F_{q^k}$ здесь? Я понимаю только простые поля ($F_q$ где q — простое число).

kelalaka avatar
флаг in
В Википедии есть введение о [Конечных полях](https://en.wikipedia.org/wiki/Finite_field), и это широкая тема (в [math.se] уже есть 4К вопросов(https:// math.stackexchange.com/questions/tagged/finite-fields) Если вы собираетесь узнать больше о Finite Field, вам следует пройти курс или прочитать книгу об этом.
Рейтинг:3
флаг cn

Вы можете считать, что это $F_q[X]/(P(X))$ с $P$ ан неприводимый многочлен степени $к$ в $F_q[X]$.

Это означает, что видимые элементы поля являются полиномами, и когда вы выполняете сложение или умножение, вы вычисляете их по модулю. $P$.

Пример игрушки: Предположим $д=2=к$. Мы можем взять $P=X^2 + X + 1$ который неприводим в $\mathbb{Z}_2$.

Все элементы имеют вид: $\alpha_0 + \alpha_1 X$.

Позволять $\alpha_0 + \alpha_1 X, \beta_0 + \beta_1 X$ два элемента поля. $\alpha_0 + \alpha_1 X + \beta_0 + \beta_1 X= (\alpha_0 + \beta_0) + (\alpha_1 + \beta_1) X$

$(\alpha_0 + \alpha_1 X) \cdot (\beta_0 + \beta_1 X)= (\alpha_0\beta_0) + (\alpha_1\beta_0 + \alpha_0\beta_1) X + \alpha_1\beta_1X^2$. И потому что $Х^2=Х+1$, он равен $(\alpha_0 + \alpha_1 X) \cdot (\beta_0 + \beta_1 X)= (\alpha_0\beta_0+ \alpha_1\beta_1) + (\alpha_1\beta_0 + \alpha_0\beta_1 + \alpha_1\beta_1) X$.

Чтобы вычислить инвертирование $(\alpha_0 + \alpha_1 X)$, надо решить систему: $(\alpha_0x_0+ \alpha_1x_1)=1$ и $ (\alpha_1x_0 + (\alpha_0+ \alpha_1)x_1)=0$.

xiaojiuwo avatar
флаг cn
Спасибо, не могли бы вы привести пример, который может просто объяснить $F_{q}[X]$
Ievgeni avatar
флаг cn
@xiaojiuwo Стало понятнее?
Рейтинг:1
флаг ng

Конечное поле $(\mathbb F,+,\cdot)$ это конечное множество $\mathbb F$ с двумя внутренними законами $+$ и $\cdot$, такой, что $(\mathbb F,+)$ является коммутативным группа с нейтральным отмеченным $0$, и $(\mathbb F-\{0\},\cdot)$ является коммутативной группой с нейтральными отмеченными $1$, а умножение является дистрибутивным относительно дополнение, которое $\forall A,B,C\in\mathbb F$ он держит $A\cdot(B+C)=(A\cdot B)+(A\cdot C)$.

Можно показать, что все конечные поля с одинаковым числом элементов являются изоморфный, то есть мы можем отображать одно в другое с помощью биекция $\mathcal F$ такой, что $\mathcal F(A+B)=\mathcal F(A)+\mathcal F(B)$ и $\mathcal F(A\cdot B)=\mathcal F(A)\cdot \mathcal F(B)$. Таким образом, мы можем говорить о в конечное поле $\mathbb F$ с $q$ элементы. Это часто отмечается $\mathbb F_q$.

Можно показать, что любое конечное поле имеет число $q$ элементов формы $q=p^k$ для некоторого простого $р$ и немного $k\in\mathbb N^*$.

Когда $к=1$, поле $(\mathbb F_p,+,\cdot)$ это просто кольцо целых чисел по модулю $р$, это $(\mathbb Z_p,+,\cdot)$.

Для произвольного $k\in\mathbb N^*$, мы можем думать о поле $(\mathbb F_{p^k},+,\cdot)$ как множество многочленов степени до $к-1$ и коэффициенты в $\mathbb Z_p$. То есть полиномы для абстрактной переменной $х$ с одним коэффициентом $\mathbb Z_p$ для каждого из $к$ термины $х^я$ с $i\in\{0,1\ldots,k-1\}$. Дополнение в $\mathbb F_{p^k}$ есть сложение многочленов. Умножение в $\mathbb F_{p^k}$ представляет собой умножение полиномов с последующей редукцией по модулю конкретного редукционного полинома. $ Р (х) $ степени точно $к$, и непреодолимый.

Эквивалентно, мы можем думать о $\mathbb F_{p^k}$ как набор $p^k$ кортежи $к$ элементы $\mathbb Z_p$, отмеченный $(а_0,а_1\ldots,а_{к-1})$. Дополнение определяется$$(a_0,a_1\ldots,a_{k-1})+(b_0,b_1\ldots,b_{k-1})=(a_0+b_0,a_1+b_1\ldots,a_{k-1}+ б_{к-1})$$с более поздними дополнениями, внесенными в $\mathbb Z_p$, то есть с редукцией по модулю $р$. Если кортеж $А$ имеет $a_i=1$ и все остальные термины $0$, и кортеж $В$ имеет $b_j=1$ и все остальные термины $0$, потом, когда $i+j<k$ кортеж $С$ за $А\cточка Б$ имеет $c_{i+j}=1$ и все остальные термины $0$. Когда $i+j=k$, кортеж $С$ за $А\cточка Б$ постоянный кортеж $(r_0,r_1,\ldots,r_{k-1})$ независим от $я$ и $j=k-i$. Этот кортеж таков, что многочлен $R(x)=x^k-r_{k-1}\,x^{k-1}\ldots-r_1\,x-r_0$ с коэффициентами в $\mathbb Z_p$ является непреодолимый, подразумевая $r_0\ne0$. Этот постоянный кортеж $(r_0,r_1\ldots,r_{k-1})$, или, что то же самое, многочлен $ Р (х) $, в сочетании с ранее изложенными правилами и свойствами $+$ и $\cdot$, полностью определяет умножение и является нейтральным $(1,0\ldots,0)$.

Мы можем вычислить кортеж $(c_0,c_1\ldots,c_{k-1})$ за $(a_0,a_1\ldots,a_{k-1})\cdot(b_0,b_1\ldots,b_{k-1})$ следующее:

  • $(c_0,c_1\ldots,c_{k-1}):=(0,0\ldots,0)$

  • за $я$ от $к-1$ вплоть до $0$

    • $м:=с_{к-1}$
    • за $j$ от $к-1$ вплоть до $1$
      • $c_j:=m\cdot r_j+a_i\cdot b_j+c_{j-1}$
    • $c_0:=m\cdot r_0+a_i\cdot b_0$

    с вычислениями в последних двух строках, перенесенными в $\mathbb Z_p$, то есть по модулю $р$.

флаг ve
Я просто хочу добавить небольшое замечание: в контексте криптографии на основе пар $k$ обычно является степенью внедрения. т.е. это наименьшее $k$ такое, что $n | q^k-1$, где $n$ — количество точек в группе эллиптических кривых. Важно выбирать кривые с малыми значениями $k$, иначе вычисление пар будет слишком дорогим.

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.