Ещё более впечатляющий успех — состоящее из 240 цифр (795 бит!) число RSA-240 было разложено на множители в ноябре 2019: https://caramba.loria.fr/dlp240-rsa240.txt
Вдогонку к предыдущему рассказу, вспомнились "25 этюдов о шифрах" (https://math.ru/lib/files/pdf/misc/25etudes.pdf ) — полученная когда-то давным-давно в качестве приза на какой-то олимпиаде. :)
Метода Ленстры там нет — но вот протокол Диффи-Хеллмана через степени есть (раздел 3.6):
Метода Ленстры там нет — но вот протокол Диффи-Хеллмана через степени есть (раздел 3.6):
Сегодняшняя байка совсем простая и короткая — это рассказ про иглу Бюффона. Допустим, у нас есть "лист в линейку" — на плоскости проведены параллельные прямые с расстоянием 1 между соседними, — и мы кидаем случайным образом на этот лист иголку единичной длины. С какой вероятностью она зацепит одну из линий?
Ответ: 2/π.
А если расстояние между линиями равно D, а длина иголки L, и L<D, то вероятность равна 2L/πD.
А если расстояние между линиями равно D, а длина иголки L, и L<D, то вероятность равна 2L/πD.
Не то, чтобы это было сложно посчитать (там один простой интеграл) — но интересно, что ответ можно получить вообще без выкладок!
А именно: давайте кидать кривую иголку произвольной формы — но смотреть уже не на вероятность пересечения, а на математическое ожидание их количества.
Для прямой короткой иголки ничего не изменится: пересечений может быть либо 0, либо 1, поэтому вероятность и математическое ожидание тут совпадают.
Так вот, несложно убедиться, что математическое ожидание пропорционально её длине. Потому что — если разбить иголку на несколько частей, то матожидание числа пересечений для всей иголки равно сумме матожиданий для частей (потому что каждая отдельная часть при бросании всей иголки тоже приземляется случайным образом; разные части зависимы, конечно, но аддитивности матожидания это не мешает).
Поэтому для прямой иголки число пересечений это аддитивная функция от её длины L — то есть c*L для некоторой константы c (если считать, что расстояние D между линиями фиксировано).
А любую (гладкую) иголку можно разбить на много-много маленьких почти-прямых кусочков, и их будет столько же, сколько и для прямой иголки такой же длины — а значит, и матожидание будет таким же.
А любую (гладкую) иголку можно разбить на много-много маленьких почти-прямых кусочков, и их будет столько же, сколько и для прямой иголки такой же длины — а значит, и матожидание будет таким же.
Итак, матожидание числа пересечений для кривой длины L равно c*L — где c от кривой не зависит. Осталось его найти.
Так вот, давайте возьмём в качестве кривой иглы — окружность диаметра, равного расстоянию между линиями!
Значит, матожидание равно 2. Ну а длина этой кривой — L=πD. Отсюда c=2/(πD).
И тем самым уже для любой кривой длины L матожидание числа пересечений равно 2L/πD.
Эта история, которую я узнал из лекции Ингрид Добеши (https://www.youtube.com/watch?v=Z19uz6Bol3I&feature=youtu.be&t=160 ) на ICM-2018 в Рио — не совсем про математику, а про её применение в искусстве.
Там было несколько сюжетов, но один из них — про холсты картин и преобразование Фурье. И мне кажется, это очень крутая история. (Я её пересказывал некоторое время назад, но в более узком кругу, и поскольку очень эту историю люблю — позволю себе повторить и тут.)
Там было несколько сюжетов, но один из них — про холсты картин и преобразование Фурье. И мне кажется, это очень крутая история. (Я её пересказывал некоторое время назад, но в более узком кругу, и поскольку очень эту историю люблю — позволю себе повторить и тут.)
YouTube
Mathematicians helping Art Historians and Art Conservators — Ingrid Daubechies — ICM2018
Mathematics can help Art Historians and Art Conservators in studying and understanding art works, their manufacture process and their state of conservation. ...
Картины пишут на холстах, на ткани (хорошо, не только — но забудем про все остальные варианты). Причём эту ткань обрабатывают свинцовыми белилами — чтобы она впитывала краску чуть менее сильно. А свинцовые белила (и потому и нити холста) хорошо видны на рентгене: