/pre>
Обнаружение больших простых чисел - относительно простая
задача, а проблема разложения на множители, произведение двух таких чисел
рассматривается в вычислительном отношении труднообрабатываемым.
Базирующиеся на трудности этой проблемы Ривест, Чамир и Адлеман разработали
RSA общее - ключевую систему шифрования.
В то время как целочисленная проблема факторизации занимала внимание
известных математиков подобно Фермату и Гауссу более чем столетия ,только
в прошлых 20 годах был сделан прогресс в разрешении этой проблемы. Имеются
две главных причины для этого явления. Сначала, изобретение RSA-системы
шифрования в 1978 стимулировало много математиков к изучению этой проблему.
И быстродействующие ЭВМ стали доступными для выполнения и испытания сложных
алгоритмов. Фермат и Гаусс имели небольшой стимул для изобретения алгоритма
разложения на множители решета поля цифр, так как этот алгоритм более
громоздкий ,чем испытательное деление с целью разложения на множители целых
чисел вручную.
3.1.2. Разложения на множетели
Имеются в основном два типа специализированных и универсальных
алгоритмов разложения на множители. Специализированные алгоритмы разложения
на множители пытаются эксплуатировать специальные особенности номера n
разлагаемого на множители. Текущие времена универсальных алгоритмов
разложения на множители зависят только от размера n.
Один из наиболее мощных специализированных алгоритмов разложения на
множители - эллиптический метод разложения на множители кривой (режим
исправления ошибок), который был изобретен в 1985 Х.Ленстром младшим.
Текущее время этого метода зависит от размера главных множителей n, и
следовательно алгоритм имеет тенденцию находить сначала маленькие
множители. 21 июня 1995 Andreas Mueller (студент в Universitaet des
Saarlandes, Германия) объявил, что он нашел 44-десятичную цифру с 147-
разрядным множителем 99-десятичной цифрой с 329-разрядным составным
целым числом, используя режим исправления ошибок. Вычисление было выполнено
на сети АРМ, и долговечность была приблизительно 60 MIPS годы. Самый
большой главный множитель, найденный к настоящему времени режимом
исправления ошибок - 47-десятичная цифра с 157-разрядным главным
множетелем 135-десятичной цифры 449-разрядный номер. До развития RSA
системы шифрования, лучший универсальный алгоритм разложения на множители
был алгоритм цепной дроби , который имел числа множителя до 40 десятичных
цифр (133 бита). Этот алгоритм был основан на идее относительного
использования основы множителя штрихов и производства связанного с набором
линейных уравнений, чее решение в конечном счете вело к факторизации. Та же
самая идея лежит в основе лучших универсальных алгоритмов, используемых
сегодня: квадратичное решето (QS) и решето поля цифр (NFS). Оба эти
алгоритмы могут быть легко параллелизованы, чтобы разрешить разложение на
множители на распределительных сетях АРМ. Квадратичное решето было
разработано Карлом Померансом 1984. Первоначально, это применялось к числам
множителя в 70-десятичной цифре 233-разрядный диапазон. В 1994 это
использовалось группой исследователей во главе с А.Ленстром к множителю 129-
десятичной цифры 429-разрядного номера проблемы RSA, который был изложен
Мартином Гарднером 14 1977. Факторизация была выполнена через 8 месяцев
примерно на 1600 компьютерах во всем мире. Долговечность для факторизации
была оценена как 5000 MIPS годы.
Сначала было разработано в 1989 ,что Решето поля цифр работает лучше
всего на числах специальной формы. Алгоритм привык к множителю 155-
десятичной цифры 513-разрядного номера. Это было впоследствии расширено к
универсальному алгоритму факторизациию. Эксперименты доказали, что NFS
является действительно превосходящим алгоритмом для целых чисел разложения
на множители, имеющих по крайней мере 120 десятичных цифр (400 битов). В
1996, группа во главе с А.Ленстром использовала NFS к множителю 130-
десятичной цифры 432-разрядного номера. Это - самый большой номер,
разложенный на множители до настоящего времени. Факторизация, как
оценивали, брала меньше чем 15 % из 5000 MIPS годы, которые требовались
для факторизации 129-десятичной цифры проблемы RSA. Разложение на множители
155 десятичной цифры 512-разрядного номера могло брать меньше усилия в 5
раз. 512-разрядный модуль n обеспечивает только крайнюю защиту , когда
используется в RSA системе шифрования.
3.2.Дискретная проблема логарифма (процессор передачи данных):
3.2.1 Описание задачи
Алгоритм цифрового представления Американского правительства (системный
агент каталога), Diffie-Hellman ключевая схема соглашения, ElGamal
кодирование и схемы сигнатуры, Schnorr схема сигнатуры, и Nyberg-Rueppel
схема сигнатуры.
Если p - простое число, то Zp обозначает набор целых чисел 0, 1, 2,...,
p - 1, где сложение и амплитудное искажение - выполняются с модулем.
Известно, что существует ненулевой элемент О Zp такой, что каждый ненулевой
элемент в Zp может быть написан как мощность a, такой элемент называется
генератором Zp.
Дискретная проблема логарифма (процессор передачи данных) заключается в
следующем: учитывая штрих p, генератор Zp, и ненулевой элемент О Zp,
находит уникальное целое число 0,1,2,..., p - 2, такое что b принадлежит
al (mod p). Целое число l называется дискретным логарифмом b к основе
a.
Базируясь на трудности этой проблемы, Диффи и Хеллман предложили
известную Diffie-Hellman ключевую схему соглашения в 1976. С тех пор были
предложены многочисленные другие криптогафические протоколы, чья защита
зависит от процессора передачи данных, включая: Американский
правительственный алгоритм цифрового представления (системный агент
каталога), ElGamal кодирование и схемы сигнатуры, Schnorr схема сигнатуры,
и Nyberg-Rueppel схема сигнатуры.С должным интересом
