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

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

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

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

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

И когда мы по модулю p убегаем на бесконечность, а по модулю q нет — знаменатель по модулю p ноль, а по модулю q нет. И алгоритм Евклида вместо 1 выдаёт нам p — то есть мы нашли на делитель n. Ура!

Вот такая прекрасная история — эллиптические кривые приводят к тому, что поскладывав точки на эллиптической кривой, мы «естественным образом» натыкаемся на делитель n.

Кстати — ещё можно спросить, а как мы вообще берём пару из эллиптической кривой и точки на ней? Скажем, если мы сначала напишем уравнение кривой,
y^2=x^3+ax+b,
то неясно, как на ней искать точки. Если выбрать x и пытаться извлечь квадратный корень по модулю n из правой части — так это задача более-менее той же огромной сложности (потому что по модулю n=pq разных квадратных корней 4, а не 2, и найти для m^2 два других корня, кроме (m,-m), равносильно разложению n на множители).
Но есть простой ответ: можно, как тот ковбой из анекдота, сначала стрелять, а потом уже рисовать круги вокруг попаданий. Берём любые (x,y,a), и полагаем b:=y^2-x^3-ax. Готово, у нас есть и эллиптическая кривая, и точка (x,y) на ней.

Кстати — как утверждает эта (https://members.loria.fr/PZimmermann/records/top50.html ) таблица рекордов, самое большое число (с большими делителями), разложенное на множители с помощью эллиптических кривых, состоит из 83 цифр (и является одним из сомножителей в разложении 7^337+1).

И это ещё не самый большой успех факторизации (ибо метод Ленстры не самый быстрый, а для больших чисел лишь третий с конца ) —

Ещё более впечатляющий успех — состоящее из 240 цифр (795 бит!) число RSA-240 было разложено на множители в ноябре 2019: https://caramba.loria.fr/dlp240-rsa240.txt

Вдогонку к предыдущему рассказу, вспомнились "25 этюдов о шифрах" (https://math.ru/lib/files/pdf/misc/25etudes.pdf ) — полученная когда-то давным-давно в качестве приза на какой-то олимпиаде. :)
Метода Ленстры там нет — но вот протокол Диффи-Хеллмана через степени есть (раздел 3.6):

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

Ответ: 2/π.
А если расстояние между линиями равно D, а длина иголки L, и L<D, то вероятность равна 2L/πD.

Не то, чтобы это было сложно посчитать (там один простой интеграл) — но интересно, что ответ можно получить вообще без выкладок!

А именно: давайте кидать кривую иголку произвольной формы — но смотреть уже не на вероятность пересечения, а на математическое ожидание их количества.

Для прямой короткой иголки ничего не изменится: пересечений может быть либо 0, либо 1, поэтому вероятность и математическое ожидание тут совпадают.