В то время пока я собирался на ланч, мой ко-воркер Дейв окликнул меня: «Хэй, Алекс, а ты не хочешь заниматься улучшениями навыков своего программирования?». Я задумался. Это было интересное предложение, но я склонялся ответить отказом: «Сейчас я занимаюсь развитем навыков говорения на языках, дружище!». Ладно, шучу. Утро началось с того, что я добрался до почты и заполучил в руки копеечный китайский Кубик, случайно заказанный на али. К обеду я проштудировал мануал сборки и обновил мышечную память, а к вечеру пришло осознание, что я наигрался. Будущее кубика было ясным: он будет пылиться на полке, раз или два в неделю может быть я буду его собирать, чтобы привести мысли в порядок или отвлечься, но не более того. Соревнование в механической скорости сборки? Non merci, уж лучше скворечники делать…

Ситуацию, как всегда, спасли мысли об автоматизации. После недолгого изучения я узнал рекогнисцировку. Для начала, число Бога уже давно найдено и равно 20. Правда задача сборки от этого не упрощается, т.к. использовать граф кратчайших путей для всех возможных конфигураций кубика не очень спортивно и немножко накладно по ресурсам. Алгоритм Бога предполагает под собой некое разумное количество использованной памяти, и в то же время обязан обеспечить минимально возможное число модификаций. Так вот, такого алгоритма еще нет. Есть ряд алгоритмов, позволяющих заметно ускорить сборку по сравнению с традиционными шаблонными методоми, но повторять кем-то уже проложенный (математически) путь мне показалось скучным. Если кому интересно, вот хороший анализ Далее есть традиционные шаблонные методы. Идея здесь в послойной сборке снизу вверх с использованием формул. Формула — последовательность модификаций Кубика, приводящая к таким-то целевым модификациям, и таким-то побочным. Соответственно, побочные модификации почти всегда падают на еще не собранные слои. Различаются шаблонные методы уровнем детализации шаблонов. Всякого рода спидкуберы знают все мыслимые шаблоны для большого количества частных случаев, что позволяет отыграть лишнюю 0.1 секунду с каждой модификации на соревнованиях. Пример, на что еще можно потратить жизнь.

Итак, я постепенно формировал для себя задачу. В итоге, формулируется она так: за кратчайшее реальное время необходимо написать решалку для Кубика Рубика.

Что мы знаем о Кубике? Число его состояний описывается как

(8! × 3^7) × (12! × 2^11)/2 = 43 252 003 274 489 856 000

.

Я знаю что есть Ссылки, но я считаю что эти видео обязаны быть опубликоваными здесь.

В популярном компиляторе gcc, а конкретнее — в его оптимизаторе, была обнаружена очередная ошибка, приводящая к Runtime error в процессе выполнения программы. При включённой опции компилятора O2, оптимизатор неверно обрабатывает определённый шаблон программы, что приводит к фатальным последствиям.

24 февраля 1968 года советская дизель-электрическая подводная лодка К-129 с базы на Камчатке вышла на боевое дежурство. Она была снабжена торпедами и ракетами подводного старта с разделяющимися ядерными боеголовками. Её задачей было сменить находившуюся на дежурстве другую подводную лодку, и дежурить в нейтральных водах Тихого океана течении трёх месяцев. В случае приказа о начале войны, именно она должна была выпустить все боеголовки по крупнейшей тихо-океанской базе США.
8 марта в назначенное время она не вышла на очередной сеанс связи. С одной стороны, это не было особой причиной для паники, ведь многие факторы могли помешать передать сигнал. Но сигнал так и не поступил.

Начало описываемых событий относится к 70-ым годам прошлого века. Тогда уже был проведён подводный кабель, соединяющий Владивосток и Петропавловск-Камчатский, по которому шла шифрованная (и не только) переписка внутри Советского Союза. В какой-то момент он и был обнаружен Американскими атомными подводными лодками: они начали зависать над кабелем и перехватывать проходящую информацию. Затем эта информация передавалась в соответствующие структуры, где её с интересом анализировали. Дело в том, что именно на Камчатке проходили различные испытания ракет, и таким образом кроме шифрованных сообщений, передавались и срочные открытые сообщения («отклонение 3 метра», etc).
Проблема заключалась в том, что у атомных подводных лодок всегда были другие цели, и зависать на одном месте по несколько дней — не самое эффективное их применение. Тогда Агентство Национальной Безопасности, вложив огромные деньги, разработали и реализовали по истине уникальный проект под названием «Кокон».

В 1982 году была создана RSA Data Security Inc. тремя парнями Рональдом Ривестом, Ади Шамиром и Леонардом Адлеманом, которые в 1977 году опубликовали свою идею алгоритма. В результате обороты продаж этой компании составили $900 миллионов, принеся создателям и огромные деньги, и признание мировой общественности. Но были и другие люди…

Я думаю эта история будет интересна многим, в том числе людям, не связанным с математикой.

В 1976 году Уитфилд Диффи и Мартин Хеллман опубликовали свою статью «Новые направления в криптографии» с революционными идеями шифрования с использованием открытого ключа. А затем, три учёных Рональд Райвест, Ади Шамир и Леонард Адлеман в августе 1977 опубликовали в статью в журнале Scientific American, где они подробно описали свой алгоритм, использующий вычисления в кольце целых чисел. Как многим известно, идея алгоритма заключается в существовании условно-одностронней функции — обычного умножения на множестве простых чисел большой длины
(f:PxP->P*P), обратить которую вычислительно сложно. Иными словами, зная n = p*q (где p и q — простые числа), узнать p и q (или факторизовать число n) при большом n представляется ресурсоёмкой задачей.
В этом же номере, известный математик и учёный Мартин Гарднер по согласию авторов алгоритма, опубликовал математическую задачу, получившую название RSA-129. В ней он написал пару чисел (n, e) — открытый ключ, где длина числа n составляла 129 десятичных знаков, а e было равным 1007, и само зашифрованное сообщение. Дешифровавшему сообщение он обещал вознаграждение в $100, которые он положил в банк под 2% годовых. По подсчётам аналитиков, для разложения такого огромного числа на множители при существавших алгоритмах факторизации и мощности тех компьютеров, потребуется 20.000 лет непрерывной работы (Рон Ривест предполагал 40 квадрильён лет для числа в 125 знаков). Но ситуация изменилась…