Регистрация Войти
Рейтинг:7
honzaik avatar Crypto

CSIDH - идеальные генераторы

флаг cn
honzaik

Я пытаюсь изучить алгоритм CSIDH. У меня есть некоторый начальный опыт работы с эллиптическими кривыми, и я следил за лекциями Эндрю Сазерленда (https://math.mit.edu/classes/18.783/2019/lectures.html), чтобы понять кольца эндоморфизмов и действие группы классов и то, как мы можем применить теорию сложных кривых к кривым над конечным полем. Мой опыт в теории чисел не так хорош, так что это может быть просто проблемой.

В CSIDH (стр. 13) упоминается, что мы главный идеал $(л)\mathcal{O}$ (куда $\mathcal{O}$ порядок в мнимом квадратичном поле) распадается на два идеала $\mathbb{l}$ и $\mathbb{\overline{l}}$ как в $(l)\mathcal{O}=\mathbb{l}\mathbb{\overline{l}}$ где также $\mathbb{l}, \mathbb{\overline{l}}$ генерируются $(l, \pi\pm 1)$.

Используя идеальное умножение, я получаю $$ \mathbb{l}\mathbb{\overline{l}} =(l, \pi + 1)(l, \pi -1) = (l^2, l(\pi -1), l(\pi + 1), \пи^2-1) $$ то есть элемент $\alpha \in\mathbb{l}\mathbb{\overline{l}}$ должен иметь вид $$ \alpha = al^2+bl(\pi-1)+cl(\pi+1)+d(\pi^2-1), \{a,b,c,d\} \subseteq \mathcal{O } $$ Как мне это получить $\альфа = xl$ для некоторых $x \in \mathcal{O}$? Это простое упрощение и использование предположения, что $\pi^2= 1 \mod l$ (т.е. характеристическое уравнение) как-то или есть более сложная причина?

Мой другой вопрос, где мы можем получить это $\mathbb{l}$, $\mathbb{\overline{l}}$ генерируются этими элементами?

Заранее спасибо. Также поможет указание на некоторые хорошие ресурсы. Я просматривал цитируемые документы, но трудно найти правильный источник.

95
1 + 2
Sam Jaques avatar
флаг us
Sam Jaques
Я добавлю дополнительный вопрос: мнимое квадратичное поле изоморфно $\mathbb{Q}[\sqrt{-p}]$; каков идеал в $\mathcal{O}_{\mathbb{Q}[\sqrt{-p}]}$, которому $\pi$ (эндоморфизм Фробениуса) изоморфен?
0
Ответить
флаг ne
Luca De Feo
@SamJaques В вопросе $Ï$ — это квадратный корень из $-p$, а не эндоморфизм Фробениуса. Комплексным умножением Фробениус отождествляется с одним из двух квадратных корней из $-p$. Ассоциированный идеал — это просто главный идеал $Ï\mathcal{O}$.
0
Ответить
Рейтинг:4
avatar Crypto
флаг ne
Luca De Feo

Чтобы ответить на ваш первый вопрос: это так просто. Перефразируя то, что вы написали, достаточно проверить, что $л$ делит все четыре образующих: $л^2$, $l(Ï-1)$, $l(Ï+1)$ и $Ï^2-1$. Для первых трех это очевидно, а для последнего просто напомню, что по определению $Ï^2 = -p$, и что CSIDH явно принуждает $l|(p+1)$. Это доказывает, что $(l) · (l,Ï-1)(l,Ï+1)$. Чтобы доказать другое включение, см. ниже.

Ваш второй вопрос по существу просит доказать, что $л,\бар{л}$ являются первичными идеалами. Самый простой способ сделать это — вычислить их нормы. Норма $(л,Ï-1)$ является НОД норм его элементов. Норма $л$ является $л^2$, а норма $Ï-1$ является $(Ï-1)(-Ï-1) = p+1$ (умножить на сопряженное). По конструкции $\gcd(l^2,p+1)=l$, так $(л,Ï-1)$ имеет норму $л$. Но $л$ является простым числом, поэтому $(л,Ï-1)$ должен быть первичным идеалом.

В заключение, вы уже знали, что $l\bar{l}â(l)$, но теперь и вы знаете, что нормы на левый и правый руль одинаковые, так что обязательно $л\бар{л}=(л)$, до единиц.

0 + 1
honzaik avatar
флаг cn
honzaik
Спасибо огромное. единственное, в чем я не уверен, так это в том, откуда берется «норма есть НОД норм ее элементов». Я немного поискал и нашел только теорему о том, что норма идеала в $\mathcal{O_K}$ есть НОД норм всех элементов (не только образующих).это только из-за особого случая из-за заказа или это относится к любому заказу? Другим способом может быть использование $(l)|(l,\pi -1)(l,\pi +1) \ подразумевает N((l))|N((l,\pi -1))N(( l,\pi +1))$, а так как $N((l))=l^2$, то либо обе имеют норму $l$, либо одна из них имеет норму $1$, что было бы противоречием, верно?
0
Ответить
флаг ne
Luca De Feo
То, что норма идеала есть НОД нормы его элементов, — одно из возможных определений нормы идеала. Причина, по которой я просто взял НОД норм образующих в своих вычислениях, заключается в том, что $n | N(a)$ и $n | N(b)$ подразумевает $n | Н(а+б)$. Таким образом, достаточно найти общие делители образующих, чтобы знать общие делители всех элементов.
1
Ответить
флаг ne
Luca De Feo
Но ваш аргумент тоже работает, если заметить, что сопряженные идеалы имеют одну и ту же норму.
1
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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