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

Зато можно такую схему реализовать с возведением в степень вместо сложения (и получается не алгоритм RSA, хоть и визуально похожий). А именно: *) Публично объявлено большое [как положено, сотня-тысяча знаков) простое число P. *) У каждого из А и Б есть свои секретные ключи — [большие] числа a и b, взаимно простые с P-1. Раз a и P-1 взаимно-простые, то из алгоритма Евклида А знает такое R, что aR сравнимо с 1 по модулю P-1. И тогда по модулю P операции возведения в степень a и в степень R взаимно-обратны: для любого сообщения M выполнено (M^a)^R=M^(aR) = M, поскольку M^(P-1)=1, а aR=1 mod (P-1). Поэтому возведение в степень a можно счесть « А-шифровкой », а в степень R — « А-расшифровкой » Точно так же, Б знает такое S, что bS=1 mod (P-1), и возведения в степень b и в степень S обратны друг другу, и мы возьмём их как Б-шифрование и Б-расшифровку.

Так, есть простой шифр « прибавление секретного ключа K » [например, с приведением по публично объявленному модулю]. Он удовлетворяет первому условию — прибавления ключей K_A и K_B коммутируют — но не удовлетворяет второму: по сообщению и его зашифрованному образу атакующий мгновенно восстанавливает секретный ключ, и дальше расшифровывает все остальные сообщения.

Давайте уберём метафору и посмотрим, что же нужно, чтобы эта схема функционировала. Замок и ключ, это, конечно, шифры, а бриллиант — пересылаемое сообщение. И тут нужны две важные вещи: *) шифры должны коммутировать: мы взяли сообщение, сначала зашифровали его шифром А, а потом результат шифром Б; после этого « снимаем замок А » — применяем расшифровывающее отображение — и хотим получить сообщение, зашифрованное чисто шифром Б. *) знание для одного из шифров какой-то пары из исходного и зашифрованного сообщения не должно помогать атакующему: по открытому каналу передаются как «сообщение» А(бриллианта), так и его «результат Б-шифровки» Б(А(бриллианта)).

Так вот — первым делом А приходится прислать Б ящик с бриллиантом, закрытый на замок А. Но после этого Б — от обиды, что не может открыть — навешивает на него ещё и свой замок! И посылает обратно А ящик, закрытый уже на два замка, и А, и Б. Получив его, А со словами « это моё, это я заберу » снимает свой замок — остаётся ящик с бриллиантом, закрытый на замок Б. Он его пересылает Б, тот снимает свой замок и забирает бриллиант.

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

Скажем, А может отправить Б ящик с бриллиантом, закрытый на замок. И Б его получит. Но без ключа А получатель не сможет этот замок открыть — а задача пересылки ключа ничем не отличается от пересылки бриллианта.

Но сначала — старая красивая задача: в одной далёкой стране почта доставляет любую посылку по адресу, но всё, что из неё можно изъять без применения ломика с автогеном, исчезает. В этой стране живут два человека, А и Б, и А хочет переслать Б бриллиант. У каждого из них есть свой навесной замок (с ключом),а у А ещё и железный ящик с петлями, на который такой замок можно навесить — если ящик закрыть на замок, внутрь залезть никто не сможет. Но без ключа тогда открыть его нельзя. Вопрос: как А переслать Б бриллиант?

Сегодняшняя байка будет о применении эллиптических кривых в криптографии, как для защиты (что более известно), так и для «нападения»-факторизации (что, почему-то, известно заметно меньше, хотя алгоритм именной, называется алгоритмом Ленстры). (На всякий случай: рассказ по открытым источникам :) )

Ну и на этой истории я хочу на сегодня прекратить дозволенные речи.

(Про треугольные знали раньше, пятиугольные и выше — вопрос всё ещё открыт...)

Вот статья Иврия 1980 года — http://mi.mathnet.ru/faa1796 — а теорему о том, что таких четырёхугольных траекторий не бывает, доказали Глуцюк и Кудряшов в 2012 году: http://www.aimsciences.org/article/doi/10.3934/jmd.2012.6.287

...и вопрос открыт до сих пор. :)

Он пришёл. Задача оказалась чуть более сложной — но ещё через неделю точно приходите, всё будет. Потом эта неделя стала месяцем...

Так что он, недолго думая, пришёл на семинар Синая и спросил. И ему сказали, что ну конечно же, это правда, приходите через неделю на следующее заседание, всё докажем.

У него эта гипотеза возникла в связи с собственными значениями оператора Лапласа — в предположении, что таких открытых областей траекторий нет, он получил следующий член их асимптотики.

Гипотеза (В. Иврий, 1980). Нет, таких бильярдов нет.

А бывают ли такие "фокусирующие" бильярды (уже просто с гладкой границей, но вовсе не с многоугольной), у которых есть _открытое_ множество периодических траекторий? То есть если поставить шарик примерно в правильное место и ударить под примерно правильным углом — то траектория обязательно замкнётся?

А ещё одна открытая проблема, которую сегодня Глуцюк упоминал, это гипотеза Иврия. Вот если мы поставим точку прямо в центр круглого бильярда, то в какую бы сторону мы её не направили, траектория будет периодична. Или — если мы возьмём квадратный бильярд и запустим из любой точки траекторию под углом с рациональным коэффициентом наклона, опять-таки, траектория обязательно будет периодической.

Кстати, про прямоугольный треугольник — есть прекрасная задача про столкновения масс на прямой, превращающаяся в задачу о бильярде и в итоге (spoilers!) приводящая к появлению π в ответе. Вот тут есть ролик 3blue1brown об этом — https://www.youtube.com/watch?v=HEfHFsfGXjs — а я узнал об этом, если не ошибаюсь, в ЛШСМ-2004 от самого Гальперина, статью которого "Playing pool with π (the number π from a billiard point of view)" (https://www.maths.tcd.ie/~lebed/Galperin.%20Playing%20pool%20with%20pi.pdf ) 3blue1brown цитирует: