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


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

В алгоритме Диксона мы будем обозначать через $ Q(m)$ наименьший неотрицательный вычет $ m^2\bmod n$, а через $ a$ -- некоторую константу такую, что $ 0<a<1$. Множество простых чисел, не превосходящих $ L^a$, мы будем называть факторной базой и обозначать через $ \pi$. Алгоритм Диксона заключается в следующем:     1. Выбрать случайное $ m\in\{0,1,\ldots,n-1\}$ и вычислить $ Q(m)$.

    2. Пробными делениями попытаться полностью разложить $ Q(m)$ в произведение простых $ p\in\pi$.

    3. В случае успеха, т. е. если $ Q(m)=\prod_{p\in\pi}p^{\alpha_p(m)}$, где $ \alpha_p(m)\geqslant0$, запомнить $ m$, $ Q(m)$ и вектор $ \overline v(m)=(\alpha_p(m)\bmod2)_{p\in\pi}$, показателей, приведенных по модулю 2. Делать перебор $ m$ до тех пор, пока не будет найдено $ \vert\pi\vert+1$ чисел, для которых $ Q(m)$ полностью разлагаются в факторной базе.

    4. Найти (например, с помощью гауссова исключения) некоторое соотношение линейной зависимости $ \overline
v(m_1)+\ldots+\overline v(m_k)\equiv\overline0\mkern5mu({\rm mod}\,\,2)$ между вычисленными на предыдущем этапе векторами $ \overline
v(m)$:

    5. Найденное на предыдущем этапе соотношение означает, что $ Q(m_1)\ldots Q(m_k)$ является квадратом натурального числа, которое мы обозначим через $ x$. С другой стороны, $ Q(m_1)\ldots Q(m_k)\equiv(m_1\ldots m_k)^2\mkern5mu({\rm mod}\,\,n)$. Поэтому для $ y=m_1\ldots m_k$ имеем $ x^2\equiv y^2\mkern5mu({\rm mod}\,\,n)$. Теперь если $ 1<(x-\varepsilon y,n)<n$ для некоторого $ \varepsilon\in\{-1,1\}$, то $ (x-\varepsilon y,n)$ -- искомый нетривиальный делитель $ n$.

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

В работе [Pom82] показано, что если в алгоритме Диксона перебрано $ \left[L^b\right]$ случайных значений $ m$ и на этапе 4 использовано гауссово исключение, то сложность этого алгоритма составляет $ L^{\max\{a+b,3a\}}$ арифметических операций. Согласно этой же работе, для нахождения нужного количества чисел $ m$ таких, что Q(m) полностью разлагаются в факторной базе, достаточно перебрать $ \left[L^b\right]$ случайных значений $ m$, где $ b=a+1/2a$. В частности, при $ a=1/2$ и $ b=a+1/2a=3/2$ сложность алгоритма Диксона составляет $ L^2$ арифметических операций.


Вперед Вверх Назад Содержание Предметный указатель
Вперед: 12.3.2 Методы ускорения алгоритма Диксона Вверх: 12.3 Факторизация чисел с субэкспоненциальной сложностью Назад: 12.3 Факторизация чисел с субэкспоненциальной сложностью   Содержание   Предметный указатель


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