Скалярное умножение на эллиптической кривой

[B@R5uk]

Вот, кой-чего интересного стало получаться. Правда, групп, которые имеют ранк 3, что-то не видать:

Используется синтаксис Text

Group structure: C_3 x C_3
Elliptic curve y^2 = x^3 + 2 over GF(7)

Group structure: C_3 x C_3
Elliptic curve y^2 = x^3 + 3 over GF(13)

Group structure: C_4 x C_4
Elliptic curve y^2 = x^3 + 5 over GF(13)

Group structure: C_4 x C_4
Elliptic curve y^2 = x^3 + 8 over GF(13)

Group structure: C_3 x C_3
Elliptic curve y^2 = x^3 + 10 over GF(13)

Group structure: C_3 x C_6
Elliptic curve y^2 = x^3 + 7x over GF(13)

Group structure: C_3 x C_6
Elliptic curve y^2 = x^3 + 8x over GF(13)

Group structure: C_3 x C_6
Elliptic curve y^2 = x^3 + 11x over GF(13)

Group structure: C_4 x C_4
Elliptic curve y^2 = x^3 + x over GF(17)

Group structure: C_4 x C_4
Elliptic curve y^2 = x^3 + 4x over GF(17)

Group structure: C_4 x C_4
Elliptic curve y^2 = x^3 + 13x over GF(17)

Group structure: C_4 x C_4
Elliptic curve y^2 = x^3 + 16x over GF(17)

Group structure: C_3 x C_9
Elliptic curve y^2 = x^3 + 5 over GF(19)

Group structure: C_3 x C_9
Elliptic curve y^2 = x^3 + 16 over GF(19)

Group structure: C_3 x C_9
Elliptic curve y^2 = x^3 + 17 over GF(19)

Group structure: C_3 x C_6
Elliptic curve y^2 = x^3 + 2x + 12 over GF(19)

Group structure: C_3 x C_6
Elliptic curve y^2 = x^3 + 3x + 12 over GF(19)

Group structure: C_3 x C_6
Elliptic curve y^2 = x^3 + 8x + 18 over GF(19)

Group structure: C_3 x C_6
Elliptic curve y^2 = x^3 + 10x + 8 over GF(19)

Group structure: C_3 x C_6
Elliptic curve y^2 = x^3 + 12x + 18 over GF(19)

Group structure: C_3 x C_6
Elliptic curve y^2 = x^3 + 13x + 8 over GF(19)

Group structure: C_3 x C_6
Elliptic curve y^2 = x^3 + 14x + 12 over GF(19)

Group structure: C_3 x C_6
Elliptic curve y^2 = x^3 + 15x + 8 over GF(19)

Group structure: C_3 x C_6
Elliptic curve y^2 = x^3 + 18x + 18 over GF(19)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 4x + 7 over GF(29)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 4x + 22 over GF(29)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 5x + 1 over GF(29)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 5x + 28 over GF(29)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 6x + 13 over GF(29)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 6x + 16 over GF(29)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 9x + 9 over GF(29)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 9x + 20 over GF(29)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 13x + 5 over GF(29)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 13x + 24 over GF(29)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 22x + 6 over GF(29)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 22x + 23 over GF(29)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 28x + 4 over GF(29)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 28x + 25 over GF(29)

Group structure: C_6 x C_6
Elliptic curve y^2 = x^3 + 1 over GF(31)

Group structure: C_6 x C_6
Elliptic curve y^2 = x^3 + 2 over GF(31)

Group structure: C_6 x C_6
Elliptic curve y^2 = x^3 + 4 over GF(31)

Group structure: C_6 x C_6
Elliptic curve y^2 = x^3 + 8 over GF(31)

Group structure: C_5 x C_5
Elliptic curve y^2 = x^3 + 11 over GF(31)

Group structure: C_5 x C_5
Elliptic curve y^2 = x^3 + 13 over GF(31)

Group structure: C_6 x C_6
Elliptic curve y^2 = x^3 + 16 over GF(31)

Group structure: C_5 x C_5
Elliptic curve y^2 = x^3 + 21 over GF(31)

Group structure: C_5 x C_5
Elliptic curve y^2 = x^3 + 22 over GF(31)

Group structure: C_5 x C_5
Elliptic curve y^2 = x^3 + 26 over GF(31)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + x + 11 over GF(31)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 2x + 21 over GF(31)

Group structure: C_3 x C_9
Elliptic curve y^2 = x^3 + 3x + 20 over GF(31)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 4x + 26 over GF(31)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 5x + 11 over GF(31)

Group structure: C_3 x C_9
Elliptic curve y^2 = x^3 + 6x + 10 over GF(31)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 7x + 26 over GF(31)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 8x + 13 over GF(31)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 9x + 13 over GF(31)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 10x + 21 over GF(31)

Group structure: C_3 x C_9
Elliptic curve y^2 = x^3 + 11x + 18 over GF(31)

Group structure: C_3 x C_9
Elliptic curve y^2 = x^3 + 12x + 5 over GF(31)

Group structure: C_3 x C_9
Elliptic curve y^2 = x^3 + 13x + 20 over GF(31)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 14x + 13 over GF(31)

Group structure: C_3 x C_9
Elliptic curve y^2 = x^3 + 15x + 20 over GF(31)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 16x + 22 over GF(31)

Group structure: C_3 x C_9
Elliptic curve y^2 = x^3 + 17x + 9 over GF(31)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 18x + 22 over GF(31)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 19x + 21 over GF(31)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 20x + 26 over GF(31)

Group structure: C_3 x C_9
Elliptic curve y^2 = x^3 + 21x + 5 over GF(31)

Group structure: C_3 x C_9
Elliptic curve y^2 = x^3 + 22x + 9 over GF(31)

Group structure: C_3 x C_9
Elliptic curve y^2 = x^3 + 23x + 9 over GF(31)

Group structure: C_3 x C_9
Elliptic curve y^2 = x^3 + 24x + 18 over GF(31)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 25x + 11 over GF(31)

Group structure: C_3 x C_9
Elliptic curve y^2 = x^3 + 26x + 10 over GF(31)

Group structure: C_3 x C_9
Elliptic curve y^2 = x^3 + 27x + 18 over GF(31)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 28x + 22 over GF(31)

Group structure: C_3 x C_9
Elliptic curve y^2 = x^3 + 29x + 5 over GF(31)

Group structure: C_3 x C_9
Elliptic curve y^2 = x^3 + 30x + 10 over GF(31)

Group structure: C_4 x C_12
Elliptic curve y^2 = x^3 + 1 over GF(37)

Group structure: C_3 x C_9
Elliptic curve y^2 = x^3 + 9 over GF(37)

Group structure: C_4 x C_12
Elliptic curve y^2 = x^3 + 10 over GF(37)

Group structure: C_4 x C_12
Elliptic curve y^2 = x^3 + 11 over GF(37)

Group structure: C_3 x C_9
Elliptic curve y^2 = x^3 + 12 over GF(37)

Group structure: C_3 x C_9
Elliptic curve y^2 = x^3 + 16 over GF(37)

Group structure: C_3 x C_9
Elliptic curve y^2 = x^3 + 21 over GF(37)

Group structure: C_3 x C_9
Elliptic curve y^2 = x^3 + 25 over GF(37)

Group structure: C_4 x C_12
Elliptic curve y^2 = x^3 + 26 over GF(37)

Group structure: C_4 x C_12
Elliptic curve y^2 = x^3 + 27 over GF(37)

Group structure: C_3 x C_9
Elliptic curve y^2 = x^3 + 28 over GF(37)

Group structure: C_4 x C_12
Elliptic curve y^2 = x^3 + 36 over GF(37)

Group structure: C_6 x C_6
Elliptic curve y^2 = x^3 + x over GF(37)

Group structure: C_3 x C_15
Elliptic curve y^2 = x^3 + 2x + 14 over GF(37)

Group structure: C_3 x C_15
Elliptic curve y^2 = x^3 + 2x + 23 over GF(37)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 3x + 1 over GF(37)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 3x + 36 over GF(37)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 4x + 1 over GF(37)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 4x + 36 over GF(37)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 5x + 3 over GF(37)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 5x + 34 over GF(37)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 6x + 7 over GF(37)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 6x + 30 over GF(37)

Group structure: C_6 x C_6
Elliptic curve y^2 = x^3 + 7x over GF(37)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 8x + 7 over GF(37)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 8x + 30 over GF(37)

Group structure: C_6 x C_6
Elliptic curve y^2 = x^3 + 9x over GF(37)

Group structure: C_6 x C_6
Elliptic curve y^2 = x^3 + 10x over GF(37)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 11x + 10 over GF(37)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 11x + 27 over GF(37)

Group structure: C_6 x C_6
Elliptic curve y^2 = x^3 + 12x over GF(37)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 13x + 3 over GF(37)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 13x + 34 over GF(37)

Group structure: C_3 x C_15
Elliptic curve y^2 = x^3 + 14x + 6 over GF(37)

Group structure: C_3 x C_15
Elliptic curve y^2 = x^3 + 14x + 31 over GF(37)

Group structure: C_3 x C_15
Elliptic curve y^2 = x^3 + 15x + 14 over GF(37)

Group structure: C_3 x C_15
Elliptic curve y^2 = x^3 + 15x + 23 over GF(37)

Group structure: C_6 x C_6
Elliptic curve y^2 = x^3 + 16x over GF(37)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 17x + 4 over GF(37)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 17x + 33 over GF(37)

Group structure: C_3 x C_15
Elliptic curve y^2 = x^3 + 18x + 8 over GF(37)

Group structure: C_3 x C_15
Elliptic curve y^2 = x^3 + 18x + 29 over GF(37)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 19x + 3 over GF(37)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 19x + 34 over GF(37)

Group structure: C_3 x C_15
Elliptic curve y^2 = x^3 + 20x + 14 over GF(37)

Group structure: C_3 x C_15
Elliptic curve y^2 = x^3 + 20x + 23 over GF(37)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 21x + 11 over GF(37)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 21x + 26 over GF(37)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 22x + 4 over GF(37)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 22x + 33 over GF(37)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 23x + 7 over GF(37)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 23x + 30 over GF(37)

Group structure: C_3 x C_15
Elliptic curve y^2 = x^3 + 24x + 8 over GF(37)

Group structure: C_3 x C_15
Elliptic curve y^2 = x^3 + 24x + 29 over GF(37)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 25x + 11 over GF(37)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 25x + 26 over GF(37)

Group structure: C_6 x C_6
Elliptic curve y^2 = x^3 + 26x over GF(37)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 27x + 10 over GF(37)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 27x + 27 over GF(37)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 28x + 11 over GF(37)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 28x + 26 over GF(37)

Group structure: C_3 x C_15
Elliptic curve y^2 = x^3 + 29x + 6 over GF(37)

Group structure: C_3 x C_15
Elliptic curve y^2 = x^3 + 29x + 31 over GF(37)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 30x + 1 over GF(37)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 30x + 36 over GF(37)

Group structure: C_3 x C_15
Elliptic curve y^2 = x^3 + 31x + 6 over GF(37)

Group structure: C_3 x C_15
Elliptic curve y^2 = x^3 + 31x + 31 over GF(37)

Group structure: C_3 x C_15
Elliptic curve y^2 = x^3 + 32x + 8 over GF(37)

Group structure: C_3 x C_15
Elliptic curve y^2 = x^3 + 32x + 29 over GF(37)

Group structure: C_6 x C_6
Elliptic curve y^2 = x^3 + 33x over GF(37)

Group structure: C_6 x C_6
Elliptic curve y^2 = x^3 + 34x over GF(37)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 35x + 4 over GF(37)

Group structure: C_4 x C_8
Elliptic curve y^2 = x^3 + 35x + 33 over GF(37)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 36x + 10 over GF(37)

Group structure: C_3 x C_12
Elliptic curve y^2 = x^3 + 36x + 27 over GF(37)
 

[Without Name]

B@R5uk
А вы по какому учебнику изучаете теорию групп? Тоже хочу так разбираться в ней.

[B@R5uk]

Если честно, то толком ни по какому. Я официально нигде её не учил. В смысле, в универе (в котором я не доучился) у нас не было курса теории групп или абстрактной алгебры или чего-то подобного (хотя теорфизикам она нужна). В линале только было упоминание определения, и всё. Знакомиться я начал с группами самостоятельно как раз из-за желания вникнуть что к чему в этих самых эллиптических кривых и еже с ними. Они рассматриваться над полями, которые являются группами по умножению и по сложению, поэтому надо было сначала понять, что это за фрукт такой: группа. Первая книжка, которую я более-менее внимательно осваивал была Гроссман И., Магнус В. - Группы и их графы. Потом меня увлекло это всё дело с графами и подгруппами, и их структурой и про поля я забыл. И я больше численно копался в них, чем что-то осваивал по книжкам, хотя накачал и пробовал читать кучу всего. Последняя книжка, которую я и сейчас почитываю — это Dummit D.S., Foote R.M. - Abstract algebra (2004, Wiley). Там всё более менее строго, но не слишком заумно. С задачами, с примерами, по делу и с комментариями. Хотя, учитывая её объём (под тыщу страниц), я едва 5% от неё "освоил" и может ещё напорюсь на что-нибудь, что мне не "по зубам".

-- 11.03.2025, 00:31 --

Вон в соседней теме пункт 5.2. «Теория групп» — большой список литературы. Не знаю как на счёт осваивоемости, но что-нибудь наверняка подойдёт.

Другое дело, что применительно к криптографии это мало поможет, кроме общего развития и возможности взглянут на проблемы "со стороны". Практическая часть криптографии — это в первую очередь алгоритмы и оценки их быстродействия и эффективности, а во вторую — готовые библиотеки. Для теории тут мало места.

[B@R5uk]

Ке-ке. Гугл следит за нами всеми. Только что мне ютубчик подкинул свежее научпоп видео на тему эллиптических кривых, в котором освещена интересная проблема. Что мне в первую очередь показалось интересным, и что имеет непосредственное отношение к моему небольшому численному "исследованию" выше, — это то, что ранк эллиптической кривой над полем рациональных чисел может быть довольно большим. Текущий рекорд равен 29. Однако, ранк кубики над полем рациональных чисел — это, не строго говоря, размерность или количество линейно независимых бесконечных направлений в группе (потому что поле рациональных чисел бесконечное). Я же выше рассматривал конечные поля, более того, поля с простым основанием (а не степенью простого), и у меня получался максимум ранк 2. В связи с этим встаёт вопрос: неужели в конечном случае группа точек эллиптической кривой не может иметь ранк больше 2? В своём тесте я рассматривал поля по основанию до 103 включительно и таковых не нашёл.

[dgwuqtj]

Вообще для эллиптической кривой $E$ над алгебраически замкнутым полем характеристики $p$ группа $E[m] = \{x \in E \mid m x = 0\}$ изоморфна $\mathrm C_m^2$, если $m \perp p$, и $0$ либо $\mathrm C_m$, если $m = p^k$. В характеристике $0$ это особенно очевидно, $E$ — это просто тор $\mathbb C / \Lambda$ для некоторой решётки $\Lambda$ (как риманова поверхность). Если кривая определена над конечным полем $\mathbb F_q$, то её точки над этим полем — это некоторая конечная подгруппа $E$, ну и понятно, что у неё не больше двух образующих.

[B@R5uk]

dgwuqtj в сообщении #1678143 писал(а):

ну и понятно, что у неё не больше двух образующих.

Почему? Группа в подгруппу может схлопываться сохраняя ранк (или даже увеличивая, если исходная группа была неабелева).

И я правильно понял, что группа точек кубики над некоторым конечным полем полностью определяется той же группой, только над полем рациональных чисел?

[dgwuqtj]

Если $A$ конечная абелева $p$-группа, то её ранг — это $\dim(\mathrm{Hom}(\mathbb F_p, A))$, он же $\dim(\mathbb F_p \otimes A) = \dim(A / p A)$, это следует из классификации. Первая формула говорит, что ранг подгрупп не больше ранга $A$, а вторая — то же самое про ранг факторгрупп (что и так очевидно, впрочем). У произвольной конечной абелевой группы ранг — это максимум рангов её $p$-компонент.

Кубики над $\mathbb Q$ вообще не определяют ничего над конечными полями. Вот если дана кубика над $\mathbb Z$, её можно взять по модулю $p$ и получить кубику над $\mathbb F_p$.

[Without Name]

B@R5uk в сообщении #1677887 писал(а):

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

Отличается. Для обеспечения того же уровня безопасности, который дает RSA с числами длиной тысячи бит, нужны числа меньшей длины, а значит, это экономия памяти во встраиваемых системах.

[Without Name]

Кроме того, существуют идеи для постквантовой криптографии на основе изогений эллиптических кривых. Эллиптическая криптография это не просто очередная идея криптосистем с открытым ключом.
Если человеку меньше 40 лет, есть смысл заняться постквантовой криптографией. Возможно, когда мы перейдем в эру квантовых компьютеров, то сможем хотя бы понимать, как все это работает.