// ТББ уже вышла? Кажется нет, надо убирать отсылку!
Так вот, алгоритм Толи, конечно, прост и неплох, но ему нужно примерно n^1.53 операций. Если то, что написано в этой не понятно где спертой и, кстати, не понятно почему вусмерть отцензуренной книжке -- правда, то это еще одна пощечина Гуру. А ведь оно похоже, похоже, таки работает, хотя там одно место еще надо бы прорешать...
Соловьев замечтался и не заметил, как с последним его словами лицо полковника Кузнецова начало наливаться багрянцем.
// Персонажи вымышленные
-- Достали! Достали, дурень! А ты не думал, где они это достали, а?
-- Но это как-бы не наше де...
-- Не наше дело? Да, вопросы задавать не твое дело! А ты не думал, что если эти алгоритмы где-то достали, то их где-то придумали?! Что где-то в Лэнгли или еще черт знает где сидит такая группа криптографов и математиков, которая эти все гениальные штуки придумывает и, заметь, -- не публикует! Они бурят науку на какую-то спец-службу, а мы об этом узнаем от каких-то варягов, которые сперли у кого-то со стола закрытую монографию и сидят, дырки для ордена вертят! Причем нам дали только выдранный из середины кусок! Уцензуренный в ноль! Почему об этом не узнали мы? Где радиоперехваты? Где шифрограммы? Где следы этих очень стойких шифров? Да даже на посольской линии их нет!
// Кузнецов намекает на вскрытие и перехват сообщений от американского посольства в МИД, идущих по специальному, защищенному кабелю. Аналогичный случай, но с советским представительством, был в Берлине, в 1953 году -- операция "Золото". Считается, что тоннель-подкоп обнаружили до официального скандала и гнали по этому кабелю дезинформацию и маловажные данные.
-- Эээ...
-- Бэ! Задумался, наконец! Оно хоть работает, Вася? Это не деза?
-- Да вроде нет, Александр Васильевич...
-- Вроде?! Опять твое "вроде"! Ты мне точно скажи! Срока тебе -- неделя!
У Соловьева оставалось семь дней, чтобы понять, как этот чертов алгоритм работает так быстро и почему "+1", а не "-1" по модулю _так_ важно для этого чертового быстрого умножения с помощью преобразования Фурье.
// Быстрое умножение с помощью преобразования Фурье, о котором идет речь тут было опубликовано Шёнхаге и Штрассеном в 1971 году. Умножение двух целых чисел выполняется за O(n log n log log n) операций. В 2007 году Мартин Фюрер опубликовал работу, в которой умножение выполняется "почти" за O(n log n) -- O(n log n 2^O(log* n)).//
