А вообще, когда мы делим в кольце вычетов по модулю 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, поэтому вероятность и математическое ожидание тут совпадают.

Так вот, несложно убедиться, что математическое ожидание пропорционально её длине. Потому что — если разбить иголку на несколько частей, то матожидание числа пересечений для всей иголки равно сумме матожиданий для частей (потому что каждая отдельная часть при бросании всей иголки тоже приземляется случайным образом; разные части зависимы, конечно, но аддитивности матожидания это не мешает).

Поэтому для прямой иголки число пересечений это аддитивная функция от её длины L — то есть c*L для некоторой константы c (если считать, что расстояние D между линиями фиксировано).
А любую (гладкую) иголку можно разбить на много-много маленьких почти-прямых кусочков, и их будет столько же, сколько и для прямой иголки такой же длины — а значит, и матожидание будет таким же.

Итак, матожидание числа пересечений для кривой длины L равно c*L — где c от кривой не зависит. Осталось его найти.

Так вот, давайте возьмём в качестве кривой иглы — окружность диаметра, равного расстоянию между линиями!