ar
Feedback

لا تقع ضحية للمخادعين! تيليمتريو يكتشف ويُميّز هذه القنوات 👉 إذا كنت تريد رؤية العلامة، اشترك

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

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

الذهاب إلى القناة على Telegram

Рассказы про разную математику. Архив: http://dev.mccme.ru/~merzon/mirror/mathtabletalks/

إظهار المزيد
4 360
المشتركون
لا توجد بيانات24 ساعات
+97 أيام
+3930 أيام
أرشيف المشاركات
photo content
05 مارس 2020, 11:39

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

photo content
04 مارس 2020, 02:57

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

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

photo content
27 فبراير 2020, 01:47

И это ещё не самый большой успех факторизации (ибо метод Ленстры не самый быстрый, а для больших чисел лишь третий с конца ) —
27 فبراير 2020, 01:47

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

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

Вот такая прекрасная история — эллиптические кривые приводят к тому, что поскладывав точки на эллиптической кривой, мы «естественным образом» натыкаемся на делитель n.
26 فبراير 2020, 23:45

И когда мы по модулю p убегаем на бесконечность, а по модулю q нет — знаменатель по модулю p ноль, а по модулю q нет. И алгоритм Евклида вместо 1 выдаёт нам p — то есть мы нашли на делитель n. Ура!
26 فبراير 2020, 23:40

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

Когда мы убегаем на бесконечность (как раз сваливаясь в нейтральный элемент группы) -- он обращается в ноль.
26 فبراير 2020, 23:39

photo content
26 فبراير 2020, 23:39

Формула для суммы точек рациональная -- там есть знаменатель:
26 فبراير 2020, 23:39

Что, если мы уже исчерпали порядок Q по одному модулю, но не по другому?
26 فبراير 2020, 08:25

Но у нас такая картина происходит с одной кривой mod p, и с другой mod q.
26 فبراير 2020, 08:24

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

Причём кривую мы будем брать вида y^2=P(x) -- с нулём на "вертикальной бесконечности".
26 فبراير 2020, 08:02

Пусть у нас есть такая кривая и точка Q на ней.
26 فبراير 2020, 07:58