![][1]


Какая связь есть между умножением методом русских крестьян и современной криптографией? В отличие от обычно изучаемых процедур умножения, его можно запросто адаптировать под вычисление степеней, а не произведений; и в некоторых криптосистемах требуется вычисление именно степеней.

Должен сразу признаться, что статья не будет посвящена тому, как русским крестьянам удавалось обмениваться информацией втайне от своих помещиков.


# Умножение методом русских крестьян


Если вы не знали о нём раньше, то это довольно любопытный подход к умножению, который не требует запоминания таблиц умножения — для него достаточно способности удваивать и делить пополам целые числа. Не очень понятно, как он относится к русским крестьянам: похоже, так же, как «датская сдоба» к Дании. Этот метод был известен ещё [древним египтянам][2], которые явно жили намного раньше русских крестьян.

Общее описание метода просто, но не слишком информативно. Тем не менее, давайте начнём с него.
[Читать дальше →][3]

[1]: https://habrastorage.org/getpro/habr/post_images/524/cfb/926/524cfb926dfb6fa05b4260f4bfae3f90.png
[2]: https://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication
[3]: https://habrahabr.ru/post/344666/?utm_source=habrahabr&utm_medium=rss&utm_campaign=344666#habracut