Pull to refresh

Comments 11

Чисто из любопытства…

Возьмем полный русский алфавит (33 буквы) и пробел.

В качестве статистики будем применять не статистику частоты букв, а статистику буквосочетаний. Чтобы сразу отсеивать невозможные буквосочетания, хотя бы.

Удастся ли за счет этого существенно снизить число финалистов?
буквосочетания можно использовать только вместо просмотра глазами полученного массива перестановок.
проверка же сделана для каждой строки матрицы независимо — а потому мы при переборе получаем буквы с интервалом в 7 между ними.

разумеется, таблицы сочетаний в тексте с интервалом в 7 букв посчитать можно, но смысла я большого в этом не вижу.
… По этой причине его невозможно распараллелить (кстати, его и не оптимизировать при всём желании), но метод динамичен и должен привести к верному результату (в теории). 

Что же на практике? CUDA же без него! Будь у меня своя ферма титанов (хотя бы штучек 10), шифр Хилла был бы разорван в клочья менее, чем за минуту. Концепция параллельных вычислений на CUDA, как стая голодных пираний, не даёт шанса остаться криптостойким этому методу шифровани…
вам не кажется что тут явное противоречие?

Имелось в виду не про мой метод, а про метод разделяй и властвуй. Способ который привел я на КУДА оптимизируем

Доля вырожденных матриц, IMHO, слишком мала, чтобы их исключение как-то серьёзно повлияло на трудоёмкость полного перебора
Очень легко показать, что мера множества вырожденных матриц равна нулю, если рассмотреть их собственные значения. Среди n собственных значений должен попасться хотя бы один ноль и очевидно, что среди всех векторов размерности n, мера подмножества векторов у которых в некоторой позиции стоит ноль также равна нулю.

Но это конечно же в пространстве R^(m,n), но точно такие же рассуждения можно применить для матриц из целых чисел.
Данный ряд букв полностью удовлетворял критерию фи-теста, но частотность букв не являлась правдоподобной. Иными словами буква «в» могла встретиться так же часто, как в натуральном тексте встречается буква «о», а «о» могла и вовсе не встретиться, но при этом свойство ИС сохранялось. Мне не удалось дать этому математическое объяснение.

Фишка в том, что умножение по модулю 31 на любое число является перестановкой. И вообще, для любого числа кроме 0, найдётся обратный элемент. Например, 2*16 = 1 mod 31, т.е 2^{-1} = 16 mod 31.
Если есть решение типа a*b = c, то так же есть решения (a*2) * (b * 2^{-1}) = c, (a * 3) * (b * 3^{-1}) = c и т.д.


Так что можно ускорить поиск — если нашёлся вектор "a", проходящий фи-тест, можно попробовать ещё 29 векторов: 2a, 3a,… 30a. Возможно, в каком-нибудь из них частоты букв совпадут с реальными

Хорошая идея. Нужно запомнить…
Не уверен, что это имеет смысл при полном переборе. Стоимость проверки позже, «а не рассматривали ли мы его уже» может оказаться дороже.

Имеет. Среди векторов, а, 2а,… 30а найдётся один, у которого первый элемент — единица (ну или хотя бы ноль). Это значит, что можно ограничить первый элемент в массиве (0 или 1), перебрать все варианты, найди кандидатов по ИС и уже только среди них пробовать вектора 2а, 3а и т.п.

хм. а вот о таком подходе не подумал, да. Получается, можно на 1 число сузить по сути перебор… интересно.
Sign up to leave a comment.

Articles