Информационный центр "Центральный Дом Знаний"

ЖМИ: ТУТ ТЫСЯЧИ КУРСОВЫХ РАБОТ ДЛЯ ТЕБЯ

cendomzn@yandex.ru

Наш опрос
Я учусь (закончил(-а) в школе техникуме институте академии университете Результаты \| Архив опросов Всего ответов: 2690

Онлайн всего: 1

Гостей: 1

Пользователей: 0

Форма входа

Алгоритм Диксона

Алгоритм Диксона, алгоритм факторизации, использующий в своей основе идею Лежандра, заключающуюся в поиске пары целых чисел x и y таких, что и

Метод Диксона является обобщением метода Ферма.

Пусть задано подмножество простых чисел $\Beta = \left\{ {p_1,p_2,\dots,p_h} \right\}$ , называемое факторной базой.

Каждому Β-гладкому числу сопоставляется вектор показателей из разложения $\vec{\alpha}\left({b}\right)=\left({\alpha_{p_1}\left({b}\right), \dots, \alpha_{p_h}\left({b}\right)}\right)$ , а также двоичный вектор, полученный из вектора $\vec{a}\left({b}\right)$ приведением всех его координат по модулю 2,

$\vec{\varepsilon}\left({b}\right)=\left({\alpha_{p_1}\left({b}\right)\mod{2}, \dots, \alpha_{p_h}\left({b}\right)\mod{2}}\right)$ .

Если теперь подобрать такое множество различных Β-гладких чисел $b_1,\dots,b_m$ , что выполнится линейное соотношение

$\vec{\varepsilon}\left({b_1}\right)\oplus \cdots \oplus\vec{\varepsilon}\left({b_m}\right)=\vec{0},$

то для произведения $x=b_1\cdots b_m$ выполнится сравнение

$x^2\equiv y^2 \pmod{n},$

где y определяется как

$y=\prod_{p \isin \Beta}p^{\left({ \vec{\alpha_p}\left({b_1}\right) + \dots +\vec{\alpha_p}\left({b_m}\right) }\right) \over{2}}.$

Описание алгоритма:

Выбирается случайное $~b, 1<b<n$ и вычисляется $~b^2\bmod{n}$ .
Проверка, факторизуют ли числа из факторной базы $~b^2\bmod{n}$ .
Если $~b^2 \bmod{n}$ является Β-гладким числом, то есть:
$b^2 \equiv \prod_{p\isin \Beta}p^{\alpha_{p}\left({b}\right)}\pmod{n},$
следует запомнить $\vec{\alpha} \left({b}\right)$ и $\vec{\varepsilon} \left({b}\right)$ . Повторять процедуру генерации чисел $~b$ до тех пор, пока не будет найдено $~m=h+1$ чисел чисел $~b_1,...,b_m$ , являющихся Β-гладкими.
Найти линейную зависимость:
$\vec{\varepsilon}\left({b_{i_1}}\right)\oplus\dots\oplus\vec{\varepsilon}\left({b_{i_t}}\right)=\vec{0}, 1<t<m$ .
и положить:
$x=b_{i_1}, \dots, b_{i_t}, y=\prod_{p\isin\Beta}p^{\left({ \vec{\alpha_p}\left({b_{i_1}}\right)+\dots+\vec{\alpha_p}\left({b_{i_t}}\right) }\right) \over{2}}$ .
Проверить $x\equiv \pm y \pmod{n}$ . Если это так, то повторить процедуру генерации. Если нет, то найдено нетривиальное разложение:
$n=u\cdot v, u=\left({x+y,n}\right), v=\left({x-y,n}\right).$

Среднюю временную арифметическую сложность А.Д. можно оценить выражением

$T=O_A \left({u^{u}\cdot h^{2}+h^{3}}\right)$ ,

где $O_A \left({h^3}\right)$ — сложность решения системы из h + 1 линейных уравнений от h неизвестных. В данном случае $h=\pi \left({M}\right)=\frac{M}{\ln{M}}$ .

Возьмем в качестве M величину $M=L\left({n}\right)^{\frac{1}{2}}$ , где $L\left({n}\right)=\exp{\left({\sqrt{\ln{n}\cdot \ln{\ln{n}}}}\right)}$ , тогда

$u^{u}=L\left({n}\right)^{\frac{1}{2}},$

$M=\pi \left({M}\right)=L\left({n}\right)^{\frac{1}{2}}.$

Отсюда следует, что трудоемкость А.Д. оценивается следующим образом

$T=O_{A}\left({L\left({n}\right)^{2}+L\left({n}\right)^{\frac{3}{2}}}\right)=O\left({L\left({n}\right)}^{2}\right).$

Лит.: Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. 2003. Стр. 78-83. Черемушкин А. В. Лекции по арифметическим алгоритмам в криптографии. 2002. Стр. 77-80.

Календарь

Архив записей
2010 Август 2010 Сентябрь 2010 Октябрь 2010 Ноябрь 2010 Декабрь 2011 Январь 2011 Февраль 2011 Март 2011 Апрель 2011 Май 2011 Июнь 2011 Июль 2011 Август 2011 Сентябрь 2011 Октябрь 2011 Ноябрь 2011 Декабрь 2012 Январь 2012 Февраль 2012 Ноябрь

Друзья сайта
Заказать курсовую работу! Выполнение любых чертежей Новый фриланс 24

Информационный центр "Центральный Дом Знаний"

Наш опрос

Форма входа

Алгоритм Диксона

Календарь

Архив записей

Друзья сайта