Математические байки

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

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

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

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

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

Кстати — ещё можно спросить, а как мы вообще берём пару из эллиптической кривой и точки на ней? Скажем, если мы сначала напишем уравнение кривой, 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) на ней.

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

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

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

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

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

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

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

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

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

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