Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Курсы лекций
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: 12.2 Факторизация чисел с экспоненциальной сложностью Вверх: 12. Задача факторизации больших целых чисел Назад: 12. Задача факторизации больших целых чисел   Содержание   Предметный указатель

12.1 Введение

Стойкость наиболее распространенной системы открытого шифрования RSA и стойкость схемы электронной подписи на основе RSA определяется сложностью задачи факторизации больших целых чисел. Поэтому эта задача -- одна из наиболее важных математических задач современной криптографии. По популярности она превосходит задачу дискретного логарифмирования, а также является составной частью известных алгоритмов дискретного логарифмирования.

Задача факторизации целых чисел -- это задача нахождения по данному натуральному числу $ n$ различных простых чисел $ p_1,\ldots,p_s$ и натуральных чисел $ \alpha_1,\ldots,\alpha_s\geqslant1$ таких, что $ n=p_1^{\alpha_1}\ldots p_s^{\alpha_s}$. Отметим, что если известен некоторый простой делитель $ p_i$ числа $ n$, то соответствующее $ \alpha_i$ может быть легко найдено (например, перебором) за полиномиальное от $ \log n$ время. Поэтому основная трудность задачи факторизации заключается в нахождении простых делителей $ n$.

Все описываемые ниже алгоритмы факторизации сводятся к нахождению нетривиальных (т. е. положительных и отличных от $ 1$ и $ n$) делителей числа $ n$, если $ n$ составное. Если мы умеем находить нетривиальные делители, то разложение $ n$ на простые множители может быть получено следующим образом. Сначала разложим число $ n$ на два нетривиальных множителя (если $ n$ составное), затем, в свою очередь, разложим каждый из этих множителей на два нетривиальных множителя (если этот исходный множитель составной), потом то же самое проделаем со всеми составными множителями, найденными на предыдущем этапе и т. д., пока все множители не станут простыми. Очевидно, что для вычисления разложения $ n$ на простые множители потребуется находить нетривиальные делители полиномиальное от $ \log n$ число раз.

В свою очередь, для нахождения нетривиального делителя $ n$ часто используется следующее замечание. Пусть каким-либо образом найдены целые числа $ a,b$ такие, что $ a^2\equiv b^2\mkern5mu({\rm mod}\,\,n)$. Тогда если $ 1<(a-\varepsilon b,n)<n$ для некоторого $ \varepsilon\in\{-1,1\}$, то $ (a-\varepsilon b,n)$ -- искомый нетривиальный делитель $ n$. Как обычно, запись $ (x,y)$ здесь и далее обозначает наибольший общий делитель чисел $ x$ и $ y$.

В настоящее время нет достаточно быстрых алгоритмов для факторизации целых чисел. Имеющиеся алгоритмы факторизации по сложности (числу арифметических операций, необходимых для их реализации) разделяются на три группы ($ c$ обозначает некоторую константу):     1) алгоритмы экспоненциальной сложности, делающие $ O(n^c)$ арифметических операций (см. раздел 12.2);

    2) алгоритмы субэкспоненциальной сложности, делающие $ L(n)^{c+o(1)}$, арифметических операций, где $ L(n)=e^{\sqrt{\ln n\,\ln\ln n}}$ (см. раздел  12.3);

    3) алгоритм, называемый методом решета числового поля, и его дальнейшие обобщения, имеющие сложность $ e^{\left((c+o(1))(\ln n)^{1/3}(\ln\ln n)^{2/3}\right)}$ арифметических операций (см. раздел 12.4).

В криптографических схемах, стойкость которых основана на сложности задачи факторизации целых чисел, в качестве сложно разлагаемого числа часто выбирают произведение $ n$ двух различных простых чисел. Отметим, что если мы умеем эффективно вычислять дискретные логарифмы по модулю такого $ n$, то мы можем эффективно разложить $ n$ на простые множители:

Теорема 1 [Cha].  Пусть $ n=pq$, где $ p$ и $ q$ -- различные простые числа. Предположим, что существует вероятностный полиномиальный алгоритм, вычисляющий по $ a\in\mathbb{Z}_n*$ и $ b\in\langle a\rangle $ некоторый дискретный логарифм $ b$ по основанию $ a$ (т. е. некоторое целое $ x$, для которого $ b\equiv a^x\mkern5mu({\rm mod}\,\,n)$) с вероятностью не менее $ 1/P(\log n)$ для некоторого полинома $ P$. Тогда существует вероятностный полиномиальный алгоритм, разлагающий $ n$ на простые множители $ p$ и $ q$ с вероятностью не менее $ 1/2$.

Через $ \langle a\rangle $ в теореме 1 обозначена подгруппа, порожденная элементом $ a$ группы $ \mathbb{Z}_n*$.

Таблицы разложений на множители и больших простых чисел можно найти в [Rie], [BriMS], [GLS], [Rib]. Самые последние сведения о разложении чисел вида $ a^n\pm 1$, где $ 13\leqslant a<100$, приведены в [BrRi]. Там собраны все известные (полные и частичные) разложения этих чисел на множители.

Вперед Вверх Назад Содержание Предметный указатель
Вперед: 12.2 Факторизация чисел с экспоненциальной сложностью Вверх: 12. Задача факторизации больших целых чисел Назад: 12. Задача факторизации больших целых чисел   Содержание   Предметный указатель

Проект осуществляется при поддержке:
 Геологического факультета МГУ,
РФФИ
    
TopList Rambler's Top100