Спирина, М.С. Дискретная математика

Т а б л и ц а 6.5 Трудоемкость разложения простых чисел Длина Число операций Примечание 50 О О Раскрываем на суперкомпьютерах 100 2,3 • 1015 На пределе современных технологий 200 1,2 • 1023 За пределами современных технологий 400 2,7 ■1034 Требует существенных изменений в технологии 800 1,3 • 1051 Требует существенных изменений в технологии (не раскрываем) С точки зрения практической реализации такой шифр обладает высокой криптостойкостью, так как в его основе лежит выбор простых чисел. В настоящее время, как известно, не найдена мате­ матическая формула или алгоритм установления простого числа. Генерация простых чисел достаточно трудоемкая задача. Еще боль­ шую трудность вызывает определение ключей, также являющих­ ся простыми числами. Известны данные о трудоемкости разложения простых чисел различной длины, установленные Шроппелем (табл. 6.5). Авторы алгоритма RSA рекомендуют использовать размеры модуля п для: частных лиц 768 бит, коммерческой информации 1024 бит. На практике встречаются и иные криптоустойчивые системы, использующие как теорию вычетов, так и поиск логарифма чис­ ла — не менее трудоемкую математическую задачу. Упражнения 6.1. Переведите в двоичную, восьмеричную и шестнадцатерич­ ную системы счисления числа: а) 53; б) 62; в) 71; г) 84; д) 96; е) 47. 6.2. Переведите двоичное число в десятичную, восьмеричную и шестнадцатеричную системы счисления: а) 010011 ; б) 100111 ; в) 110100 ; г) 010101 ; д) 101010 ; е) 010010 . 6.3. Найдите сумму, разность и произведение чисел А и £ в двоичной системе счисления и сделайте проверку результата в десятичной системе счисления: а) Л = 100110 , б)Л = 010111 , в)А = 011011 , г)^4 = 101100 , £ = 001001 ; £ = 101000 ; £ = 010010 ; £ = 101000 ; д ) Л = 111010 , е) Л = 110011 , £ = 110000 ; £ = 001001 . 336