Работа является продолжением серии статей, посвященных обращению дискретных функций из класса, имеющего пересечения с различными областями кибернетики. В данный класс, в частности, попадают функции, используемые в современных криптосистемах в качестве шифрующих преобразований. В настоящей работе обсуждаются некоторые характерные моменты, касающиеся решения задач обращения рассматриваемых функций на многопроцессорных вычислительных системах.
Скачать электронную версию публикации
Загружен, раз: 68
- Title АНАЛИЗ НЕКОТОРЫХ КРИПТОГРАФИЧЕСКИХ ПРИМИТИВОВ НА ВЫЧИСЛИТЕЛЬНЫХ КЛАСТЕРАХ
- Headline АНАЛИЗ НЕКОТОРЫХ КРИПТОГРАФИЧЕСКИХ ПРИМИТИВОВ НА ВЫЧИСЛИТЕЛЬНЫХ КЛАСТЕРАХ
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 2(2)
- Date:
- DOI
Ключевые слова
обращение дискретных функций , преобразования Цейтина , многопроцессорный кластер Авторы
Ссылки
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.
Simon J. On Some Central Problems in Computational Complexity: Doctoral Thesis, Dept. of Computer Science, Cornel University, Ithaca, NY, 1975.
Семенов А.А. О сложности обращения дискретных функций из одного класса // Дискретный анализ и исследование операций. 2004. Т. 11. № 4. С. 44 - 55.
Семенов А.А., Буранов Е.В. Погружение задачи криптоанализа симметричных шифров в пропозициональную логику // Вычислительные технологии (совместный выпуск с журналом «Региональный вестник Востока»). 2003. Т. 8. С. 118-126.
Tseitin G. On the complexity of derivation in propositional calculus // In Studies in Constructive Mathematics and Mathematical Logic, part 2. 1968. P. 115 - 125. Reprinted in J. Siekmann and G. Wrightson (editors). Automation of reasoning. Berlin: Springer Verlag, 1983. V. 2. P. 466 - 483.
Haken A. The intractability of resolution // Theoretical Computer Science. 1985. V. 39. P. 297 - 308. [Перевод: Хакен А. Труднорешаемость резолюций //Кибернетический сборник. Новая серия. М.: Мир, 1991. Вып. 28. С. 179 - 194.]
Robinson J.A. A machine-oriented logic based on the resolution principle // J. ACM. 1965. V. 12. No. 1. P. 23 - 41. [Перевод: Робинсон Дж.А. Машинно-ориентированная логика, основанная на принципе резолюций // Кибернетический сборник. Новая серия. М.: Мир, 1970. Вып. 7. С. 194 - 218.]
Заикин О.С., Семенов А.А., Сидоров И.А., Феоктистов А.Г. Параллельная технология решения SAT-задач с применением пакета прикладных программ D-SAT // Вестник ТГУ. Приложение. 2007. № 23. С. 83-95.
Заикин О.С., Семенов А.А. Технология крупноблочного параллелизма в SAT-задачах // Проблемы управления. 2008. № 1.С. 43-50.
Цейтин Г.С. О сложности вывода в исчислении высказываний // Зап. научн. семинаров ЛОМИ АН СССР. 1968. Т. 8. С. 234-259.
Семенов А.А. Логико-эвристический подход в криптоанализе генераторов двоичных последовательностей // Труды Междунар. науч. конф. ПАВТ'07. Челябинск: ЮУрГУ, 2007. Т. 1. С. 170 - 180.
Cook S.A. The complexity of theorem-proving procedures // Proc. 3rd Ann. ACM Symp. on Theory of Computing, Association for Computing Machinery, Ohio, 1971. P. 151 - 159. [Перевод: Кук С.А. Сложность процедур вывода теорем //Кибернетический сборник. Новая серия. М.: Мир, 1975. Вып. 12. С. 5 - 15.]
Буранов Е.В. Программная трансляция процедур логического криптоанализа симметричных шифров // Вестник ТГУ. Приложение. 2004. № 9 (1). С. 60 - 65.
Буров П.С., Игнатьев А.С., Отпущенников И.В. Программная трансляция алгоритмов в логические выражения в задачах диагностирования дискретных систем // Материалы IX школы-семинара «Математическое моделирование и информационные технологии». Иркутск, 2007. С. 33 - 35.
Семенов А.А., Заикин О. С. Неполные алгоритмы в крупноблочном параллелизме комбинаторных задач // Труды Междунар. науч. конф. ПАВТ'08. СПб., 2008. С. 232 - 244.
Заикин О.С. Пакет прикладных программ Distributed-SAT. Свидетельство об официальной регистрации программы ЭВМ № 2008610423, опубл. 23.01.2008.
Феоктистов А.Г., Сидоров И.А. Языковые средства описания распределенных вычислений в инструментальном комплексе DISCOMP // Труды Междунар. науч. конф. ПАВТ'08. СПб., 2008. С. 488 - 493.
MiniSat [<http://minisat.se/MiniSat.html>]
Biryukov A., Shamir A., Wagner D. Real Time Cryptanalysis of A5/1 on a PC. Fast Software Encryption Workshop 2000. April 10 - 12, 2000. New-York City.
Суперкомпьютерный центр ИДСТУ СО РАН [http://www.mvs.icc.ru]
Научно-исследовательский вычислительный центр МГУ им. М.В. Ломоносова [http://parallel.ru/cluster/]
Список суперкомпьютеров топ-50 [http://supercomputers.ru/]
Межрегиональный вычислительный центр ТГУ [http://skif.tsu.ru]
АНАЛИЗ НЕКОТОРЫХ КРИПТОГРАФИЧЕСКИХ ПРИМИТИВОВ НА ВЫЧИСЛИТЕЛЬНЫХ КЛАСТЕРАХ | Прикладная дискретная математика. 2008. № 2(2).
Скачать полнотекстовую версию
Полнотекстовая версияЗагружен, раз: 409