А раз все операции рациональные — значит, всё то же самое можно делать и над конечными полями. (Давайте на всякий случай вынесем за скобки поля характеристик 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 по одному модулю, но не по другому?

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

Когда мы убегаем на бесконечность (как раз сваливаясь в нейтральный элемент группы) -- он обращается в ноль.

А вообще, когда мы делим в кольце вычетов по модулю n, мы вычисляем алгоритмом Евклида обратный элемент к знаменателю D (после чего соотношение aD-bn=1 как раз и говорит, что 1/D = a по модулю n).