Михаил Масленников – Занимательная криптография. Часть 1 (страница 2)
Генерал хохотал весь вечер, к концу совсем расслабился, пил с π и с 100 на брудершафт, потом его повели к очаровательным запятым из ведомства числа 1 – в общем, жизнь удалась. Наутро, не желая оставаться в долгу, генерал заявил, что никогда не забудет этого банкета и в память о нем назовет какое-нибудь оружие.
Так в армии появился пистолет.
Но были в МНЧ и диссиденты: числа, не вступившие в партию, и вообще, не желавшие ни с кем делиться, кроме Царя. В народе их называли еще простыми числами. Строго говоря, и всеми уважаемые числа 2, 3 и 5 тоже были простыми диссидентами, но благодаря куче поклонников – других чисел из МНЧ, которые с ними делились, – Царь считал их «своими» диссидентами и никаких репрессий к ним не применял. А вот числу 13 не повезло. Оно жило рядом с честным-пречестным числом 12 и постоянно пыталось отучить его от алкоголизма. Как бы не так! Число 12 написало кляузу в Контору, после чего отдел Пропаганды Царя-Батюшки объявил число 13 причиной всех бед и несчастий в МНЧ и обозвал его «чертовой дюжиной».
Так и жили тысячу лет в МНЧ, умножались и делились, стремясь достигнуть светлой цели, записанной в Программе правящей партии – бесконечности, но никак не могли этого сделать. А когда провозглашается что-то заведомо недостижимое, то в конце концов народ начинает выражать свое недовольство: умножаемся, делимся, а все без толку, бесконечности так и нет. Решив стравить пар народного недовольства, партийные вожди однажды провозгласили перестройку: «Давайте делиться с остатком!». Мол побесятся натуральные числа, наиграются, и все вернется к прежним умножению и делению, когда никаких тебе остатков, все – общее.
А народ в МНЧ был такой, что палец ему в рот не клади – руку по локоть откусят. Раз провозгласила правящая партия деление с остатком, то все сразу смекнули, что остаток-то – штука неплохая. Главное, чтобы он в 0 не обратился, как было в прежней, доперестроечной жизни. И вот ведь что еще негодяи придумали – конечные группы. До того всем числам на всех политзанятиях только и внушали: наша цель – бесконечность, а тут – упала дисциплина, перестали слушать партийных пропагандистов, а на улицах стали появляться антиправительственные листовки: наша цель – конечная группа. Сам такую листовку раз видел на площади прямо около Конторы. Прихватил ее с собой, вот она.
Наша цель – конечная группа!
Всем! Всем! Всем!
Натуральные числа! Не слушайте пропагандистов из партии честных чисел – никакие они не честные! Врут они нам, что наша цель – бесконечность, не достигнуть ее ни через 100, ни через 1000 лет, сколько бы мы ни умножались и делились. Наша цель – конечная группа!
Вам забивают голову этой мистической бесконечностью, а мы расскажем вам, как быстро создать реальную конечную группу.
Нет бесконечности!!!
Контора сперва хотела принять радикальное решение: показать всем этим вольнолюбцам настоящую бесконечность, обратив их в лагерную пыль. Но хитрое число 2 надоумило Контору не делать глупостей – не 37 год на дворе, надо действовать тоньше и с выгодой для себя. Надо просто подсунуть горлопанам подходящий модуль. Например, честного-пречестного алкоголика – число 12.
Идет как-то на нетвердых ногах число 3, а навстречу ему прямо сияет честное-пречестное число 8.
– Давай вступим в конечную группу по модулю 12.
– Давай!
Вступили. Перемножились. Раньше такое сколько раз вытворяли и в Контору за это никто не попадал. А тут как только привели результат по модулю 12, глазом не успели моргнуть, как он уже в Конторе.
Ну что, сынки, помогло вам ваше деление с остатком?
Возмутились числа: что такое, в конечной группе могут быть делители нуля! Не делители, а осведомители – поправили их в Конторе.
Приуныли натуральные числа. Неужели опять – все по-старому, наша цель – бесконечность? А нельзя ли как-то получить конечную группу без конторских осведомителей?
День думали, два, а на третий вспомнили о простых числах, тех, которые ни с кем не делятся. Взяли, к примеру, соседа числа 12 – бедное и затравленное число 13. И, о чудо! Кто с кем в его конечной группе ни умножался по модулю 13, а результат в Контору так и не попал! Не верите? Проверьте сами.
И стали в МНЧ очень популярны числа, которые не хотели ни с кем делиться. Как только выберут такое число модулем, так в его конечной группе законность и порядок, все арифметические операции выполняются четко и правильно, без всяких чуровых и делителей-осведомитлей числа 0. Старик Евклид придумал способ, как не только умножаться, но и делиться в такой конечной группе, причем как умножаться, так и делиться стали абсолютно все, от мала до велика, кто на кого захочет. Кроме, естественно, числа 0, которому в этой группе места уже не было.
Контора была в ярости. Это кто ж теперь в модулях ходит? Без 0 в конце, беспартийные, непьющие, без юбилейных медалей! По-обычному ни с кем не делятся – простые! Да таких простых – раз два – и обчелся! А как же светлое будущее – бесконечность? С кем его строить-то будем, если все простые скоро закончатся?
Не закончатся – ответил Конторе старик Евклид в своих «Началах».
На всякий случай в Конторе решили поставить все конечные группы на учет под буквой Z, от слова zero – агентурной клички числа 0: Z/2 – группа по модулю 2, Z/3 – группа по модулю 3 и так далее. А натуральные числа, для конспирации, чтобы не употреблять раздражающее Контору выражение «делиться в конечной группе» заменили его на благородное «решать сравнение первой степени по модулю».
Группа Z/2 была совсем неинтересной и состояла из одного Царя-Батюшки – числа 1.
Группа Z/3 состояла из Царя и партийного Вождя – числа 2. Забавные превращения там получались. Партийный вождь, перемножившись сам с собой, превращался в Царя. Ну это еще можно понять, такие превращения бывали не только у натуральных чисел. А вот Царь-то, Царь – хорош гусь! Поделившись на партийного Вождя, сам становился партийным Вождем! Такие чудеса происходили только в этой VIP-группе, в других группах и народу было поболее, и умножение-деление повеселее.
Вскоре из конечных групп стали создавать нечто вроде ночных клубов для отдыха трудящихся чисел: «Семеро козлят», «Футбольная команда», «Чертова дюжина», «17 мгновений весны» и прочая, прочая, прочая.
Натуральные числа были рады их появлению. Особенно рад был Царь-Батюшка. Сидит, бывало, в своем дворце целыми днями один-одинешенек, и поделиться-то не с кем, ни на кого он не делился. А тут, в конечной группе – делись с кем хочешь, хоть до утра. И число 2 меньше стало внимания уделять своей партии – надоели, зануды. Пойдут, бывало, Царь вместе с партийным Вождем в weekend в какие-нибудь «Мгновения» душу отвести, наделиться всласть на всю трудовую неделю вперед, а там уже и число 3 (меньше пить стало!) и 5 (без медалек!) и 12, подружившееся с 13, все веселые, друг с другом делятся. Да и вообще, все сразу же перевернулось с ног на голову, какие тут партии и партбилеты! Без особых проблем число 2 согласилось на переименование своей партии в множество, а тут еще запятая из Администрации Царя, перепечатывая Указ о деполитизации в МНЧ и думая о чем-то своем, девичьем, пропустила одну букву, и вместо Ума, Чести и Совести нашей эпохи – Партии Честных Чисел – получилось самое обыкновенное множество четных чисел.
Но все это было несерьезно, развлекалочки какие-то. Серьезные дела начались в МНЧ с появлением там персональных компьютеров. Первым по достоинству оценило их появление число 2. Оно ведь было не только хитрым, но и умным числом. Вместо прикрытой за ненадобностью Партии Честных Чисел число 2 создало очень нужную для компьютеров двоичную систему счисления и теперь каждое число из МНЧ имело свое двоичное представление на компьютере. В МНЧ появились и такие немыслимые раньше слова, как информационные технологии, информационная безопасность, электронно-цифровая подпись, RSA. А вот RSA как раз и стал таким алгоритмом, в котором без простых чисел обойтись никак невозможно. Только простые числа p и q для RSA нужны большие – ведь они же секретный ключ! Думало – думало об этом число 2 и решило, что длина простого числа в RSA, как правило, должна быть 512 или 1024 бит. Пол-литра и литр – по-своему расшифровало эти значения число 3.
И брошен был клич: все на поиски больших простых чисел, пол-литровых и литровых, ибо без них не будет в МНЧ ни Internet Banking, ни электронной коммерции, ни современной цивилизации, а будем только вечно к бесконечности стремиться. А простые числа – скромные, тихо сидят себе по своим конечным группам, никаких явных признаков у них нет. Как их отыскать в многотриллионном множестве натуральных чисел?
Задачу эту поручили Конторе. Ну а Контора – что с нее взять – выполнила это поручение так, как умела.
Переписали в Конторе все простые числа до 256 и поехали по отдаленным уголкам необъятного множества натуральных чисел. Случайно заезжают в какую-нибудь глухомань и хватают там первого попавшегося пол-литрового аборигена.
– Говори, падла, с кем делишься?
– Что Вы, что Вы, гражданин начальник, ни с кем не делюсь.