Газонокосилка помогает красть велосипеды

Если мы забываем пароль, то естественное желание — потратить на взлом минимум времени. Когда, например, велосипедный замок отказывается открываться, первой в голову приходит мысль перебрать «методом тыка» все варианты. Однако группа математиков из России и Франции нашла способ сэкономить время и усилия, прибегнув к «методу газонокосильщика».

Математики утверждают: правильней начать с одной случайной комбинации, а потом последовательно прокручивать каждое колесико с цифрами от начала до конца. Точно так же принято поступать с газоном — вооружившись машинкой, последовательно проходить дорожки, не сползая на соседние. Строгий расчет, в котором задействованы контурные интегралы в комплексной плоскости, а сам процесс представляется случайными блужданиями по односвязному графу, — показывает, что так экономится до половины времени, уходящего на перебор вариантов.

Источник: Kabatiansky G., Oshanin G. Finding passwords by random walks: How long does it take? // arXiv:0909.1051.