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

12.3.4 Метод квадратичного решета

Это один из самых широко используемых на практике методов. Его описание можно найти в работах [Pom85], [Silv]. Оценка сложности составляет $ L^{\sqrt{9/8}}$, если используется гауссово исключение, и $ L^{1,02}$, если используется метод Копперсмита -- Винограда. Стратегии PS и EAS не используются, так как выбор значений $ m$ происходит с помощью специального просеивания.

Схема алгоритма заключается в следующем. Пусть $ \pi$ -- факторная база (т. е. конечное множество не слишком больших простых чисел), $ H(m)=m+\left[\sqrt{n\vphantom{n_1}}\right]$, а $ Q(m)=H(m)^2-n$. Будем просеивать значения $ m$, чтобы отыскать те, для которых $ Q(m)$ разлагается в произведение простых чисел из факторной базы $ \pi$. Для этого:     1) для каждого $ p\in\pi$ находим некоторые $ r^{(p)}_1$ и $ r^{(p)}_2$ такие, что $ Q(r^{(p)}_i)\equiv 0\mkern5mu({\rm mod}\,\,p)$ для $ i=1,2$;

    2) заводим массив, пронумерованный значениями целочисленной переменной $ m$ из достаточно большого интервала $ [-M,M]$, и для каждого $ m$ в $ m$-й элемент массива помещаем достаточно грубо вычисленное значение $ \log Q(m)$;

    3) для каждого $ p\in\pi$ из элементов нашего массива с номерами $ m$ такими, что $ m\equiv r^{(p)}_1\mkern5mu({\rm mod}\,\,p)$ или $ m\equiv r^{(p)}_2\mkern5mu({\rm mod}\,\,p)$, вычитаем достаточно грубо вычисленное значение $ \log p$. После такой процедуры мы получим массив, в котором $ m$-й элемент есть грубо вычисленное значение $ \log Q(m)-\sum_{p\in\pi_0}\log p$, где $ \pi_0=\left\{p\in\pi\,\left\vert\,m\equiv r^{(p)}_1\mkern5mu({\rm mod}\,\,p)\text{ или }m\equiv r^{(p)}_2\mkern5mu({\rm mod}\,\,p)\right.\right\}$.

Теперь мы отбираем те номера $ m$, для которых $ m$-е элементы массива достаточно малы, и для них разлагаем значения $ Q(m)$ пробными делениями в произведение элементов факторной базы. Используя технику этапов 3 и 4 алгоритма Диксона, находим числа $ m_1,\ldots,m_k$ такие, что $ Q(m_1)\ldots Q(m_k)$ является квадратом натурального числа, которое мы обозначим через $ x$. С другой стороны, $ Q(m_1)\ldots Q(m_k)\equiv(H(m_1)\ldots H(m_k))^2\mkern5mu({\rm mod}\,\,n)$. Поэтому для $ y=H(m_1)\ldots H(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$.

Преимущество такого метода заключается в том, что на стадии просеивания мы пользуемся только операцией вычитания и в итоге отбрасываем большинство "плохих" (т. е. не разлагающихся в произведение простых $ p\in\pi$) значений $ Q(m)$, в то время как в алгоритме Диксона "плохие" значения $ Q(m)$ отбрасываются после деления на $ p\in\pi$, что значительно дольше.


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


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

TopList Rambler's Top100