ЗАСТОСУВАННЯ ГЕНЕТИЧНИХ АЛГОРИТМІВ У ЗАДАЧІ ПРО УКЛАДАННЯ РАНЦЯ
Анотація
Розглядається застосування генетичних алгоритмів у криптології. Описуються основні поняття генетичного алгоритму, представляється його цикл у вигляді блок-схеми та приведена послідовність етапів роботи алгоритму. Формулюється задача про укладання ранця та загальний алгоритм її розв’язання. На прикладі задачі про укладання ранця розглядається можливість застосування генетичних алгоритмів при шифруванні. Показується, що застосування генетичних алгоритмів – один із найкращих методів для пошуку «прийнятних» рішень.
Посилання
Holland J.H. Adaptation in Natural and Artificial Systems / J.H. Holland. Ann Arbor, MI: The University of Michigan Press, 1975. 2nd edn. Boston, MA: MIT Press, 1992.
Merkle R.C. Hiding Information and Signatures in Trapdoor Knapsacks / R.C. Merkle, M.E. Hellman // IEEE transactions on Information Theory. Sep 1978. V. 24. N. 5. P. 525–530.
Aхo А. Построение и анализ вычислительных алгоритмов / А. Ахо, Д. Хопкрофт, Д. Ульман. М.: Мир, 1979. С. 404–446.
Brickell E. Solving Low Density Knapsacks / E. Brickell // Advances in Cryptology: Proceedings of crypto. New York: Plenum Press, 1984. P. 25–37.
Shamir A. A Polynomial – Time Algorithm for Breaking the Basic Merkle – Hellman Cryptosystem / A. Shamir // Proceedings of the 23rd IEEE Symposium on the Foundations of Computer Science. 1982. P. 145–152.
Schneier B. Applied Cryptography Second Edition: protocols, algorithms and source code in C. John Wiley & Sons Inc., 1996. (Русский перевод: Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. М.: ТРИУМФ, 2002).
Cryptanalysis of knapsack ciphers using genetic algorithms / R. Spillman // Cryptologia. 1993. V. 17. N. 4. P. 367–377.
Matthews R. The use of genetic algorithms in cryptanalysts / R. Matthews // Cryptologia. 1993. V. 17. N. 2. P. 187–201.
Use of a Genetic Algorithm in the Cryptanalysis of Simple Substitution Ciphers / [R. Spillman, M. Janssen, B. Nelson, M. Kepner] // Cryptologia. 1993. V. 17. N. 1. P. 31–44.
UA 
EN 
