Итак, точки на эллиптической кривой можно складывать. Причём — и это важно — эта операция рациональная: если у нас есть координаты двух складываемых точек (и уравнение самой кривой), то координаты суммы через них выражаются как рациональные функции, безо всяких там корней. Потому что нахождение третьего корня кубического уравнения при известных первых двух делается через теорему Виета про коэффициент при x^2, и там нужно только складывать/вычитать/делить, но не извлекать корни.

(Кстати, удвоение точки тоже оказывается "рациональной" операцией — единственное, что нужно сказать, это что прямая PQ в этом случае заменяется на касательную к кривой.)

А раз все операции рациональные — значит, всё то же самое можно делать и над конечными полями. (Давайте на всякий случай вынесем за скобки поля характеристик 2 и 3 — чтобы не контролировать, не могли ли двойки и тройки где-нибудь пробраться в знаменатели наших выражений)...

(Продолжая вчерашнее:)
Ну и теперь понятно, как через эллиптические кривые устроить протокол Диффи-Хеллмана. Пусть у нас публично объявлена эллиптическая кривая над большим конечным полем и точка P на ней. Для создания общего секретного ключа А и Б выбирают по большому числу a и b и вычисляют aP и bP соответственно. После этого А посылает Б точку aP (открыто), а Б посылает А точку bP (тоже открыто). И А вычисляет a(bP), а Б – b(aP), и вот они получили общий секретный ключ abP. Ура!

Да — естественно, поскольку степень a (я буду писать именно «степень», а не «множитель», потому что хочу думать о точках эллиптической кривой как о группе, пусть и коммутативной) большая, то aP вычисляется не как P+P+…+P сложением a раз, а так же, как любая другая большая степень в группе — чередой удвоений (2^100 P =2 (2(…(2 P))) ), разложением a в двоичную запись и сложением соответствующих удвоений.

Собственно, если бы степень a была столь маленькой, что можно было бы до неё «досчитать» просто сложением P+P+…+P, то это же мог бы проделать и атакующий — складывать P, пока не увидит совпадающий с переданным по открытому каналу результатом aP. И всё, атакующий знает секрет a.

(см.: https://en.wikipedia.org/wiki/Elliptic-curve_Diffie%E2%80%93Hellman#Key_establishment_protocol )

Естественно, что за всем этим стоит ещё безумное количество деталей — в которые я вдаваться не буду; оставлю тут только ещё две ссылки:
https://en.wikipedia.org/wiki/Curve25519 — одна конкретная эллиптическая кривая. Вот прямо явно выписанная:

https://en.wikipedia.org/wiki/Dual_EC_DRBG — а это к тому, что выбор публичной точки/кривой это вопрос тонкий... Цитата из Брюса Шнайдера, https://www.schneier.com/blog/archives/2013/12/nsa_spying_who.html :

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

Вот. Несмотря на все эти тонкости — по крайней мере, как в принципе работают эллиптические кривые "на стороне общающихся", мы посмотрели.
А теперь давайте вернёмся к другой математике, к обещанному в самом начале методу Ленстры : к эллиптическим кривым на стороне нападающего в классической задаче разложения на множители.

Итак, пусть у нас есть большое число N, и пусть для простоты оно есть произведение двух простых, N=pq.

Китайская теорема об остатках учит нас, что кольцо вычетов по модулю N это не поле -- но декартово произведение двух полей, вычетов по модулю p и по модулю q. И "эллиптическая кривая", которую мы зададим каким-нибудь уравнением, будет декартовым произведением того, что это уравнение задаёт по модулю p и по модулю q.

Пусть у нас есть такая кривая и точка Q на ней.

Причём кривую мы будем брать вида y^2=P(x) -- с нулём на "вертикальной бесконечности".

Давайте умножать точку Q на разные множители -- в групповом смысле, возводить её в степень, причём не 2-3-4, а с большим количеством разных делителей. Если бы у нас и впрямь была группа -- то мы бы в какой-то момент ("выбрав" все делители порядка Q) пришли бы в нейтральный элемент -- то есть улетели бы на бесконечность.

Но у нас такая картина происходит с одной кривой mod p, и с другой mod q.

Что, если мы уже исчерпали порядок Q по одному модулю, но не по другому?

Формула для суммы точек рациональная -- там есть знаменатель: