\input{ca_preamble.tex}
\usepackage {graphicx}
\begin{document}

\lectitle{10}{Алгоритм квадратичного решета для факторизации целых чисел}
\lecauthor{Н.\,Дуничкина}
\date{20 декабря 2008}
\maketitle

\tableofcontents

\section{Введение}

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

$x \neq \pm y \pmod{n}$

Тогда $0 \equiv x^2-y^2 \equiv (x-y)(x+y)$. 

$НОД (x+y,n)$, $НОД (x-y,n)$ - нетривиальные делители $n$.

Будем искать $q$, такое что $q^2 \pmod{n}$ мало и польный квадрат в арифметическом смысле, но при этом $q$ - большое.

Пусть $$
x=q
$$
$$
y=\sqrt{q^2\mod n}
$$
Считаем $НОД(x+y,n)$. Если тривиальный, то ищем другое $q$.

$q=\left\lceil \sqrt{an}+b\right\rceil$, 
где $a$,$b$ - малые $\in {\ZZ}$. Например, $a=1$

$q=\sqrt{an}+b+\delta (0\leq\delta<1)$
Тогда

$q^2=an+2(b+\delta)\sqrt{an}+(b+\delta)^2\equiv 2(b+\delta)\sqrt{an}+(b+\delta)^2 \pmod{n}$

$q^2~ O(\sqrt{n})$. Какова вероятность, что из него можно извлечь квадратный корень?

Всего $\sqrt{m}$ чисел - полных квадратов, меньших или равных $m$.

$P=O(\frac{1}{\sqrt[4]{n}})$

Если числа ведут себя как случайные, то сколько надо перебрать $a$ и $b$, чтобы найти нетривиальное сравнение в НОД?

\begin{example}
$n=561$

$a=1$, $b=0$ \,  $\left\lceil \sqrt{561}\right\rceil=24 $

$24^2=576 \equiv 15 \pmod{n}$ - не квадрат

$a=1$, $b=1$ \, $\left\lceil \sqrt{561}+1\right\rceil=25$

$25^2=625 \equiv 64=8^2$ \, Ура!

$НОД(561,25-8)=17$ - найден делитель!

$НОД (561,25+8)=33$

\end{example}


Трудоемкость $\sqrt[4]{n}$. Что можно сделать, чтобы уменьшить ее?

\begin{example}
$n=4633$

$67^2 \equiv -144 \pmod{n}$ \, не квадрат

$68^2 \equiv -9 \pmod{n}$ 

$(67 \cdot 68)^2=(12 \cdot 3)^2$

$x=67 \cdot 68=4556=-77 \pmod{3}$

$y=12 \cdot 3=36$

$НОД(x-y,n)=113$

$НОД(x+y,n)=41$
\end{example}

%Определение 1:
\begin{definition}
\label{PhactorBase}
Возьмем некоторое $B$ ~ $e^{\sqrt{\ln{n} \cdot \ln{\ln{n}}}}$ и рассмотрим простые числа, не превышающие $B+(-1)$. Назовем это множество {\em факторной базой}
\end{definition}

\section{Алгоритм}
\begin{enumerate}
\item[\rm 1.] Найти факторную базу
\item[\rm 2.] Для разных $a$ и $b$ вычислять
$Q_i=\left\lceil \sqrt{an}+b\right\rceil$.

Убедиться, что $Q_i^2 \mod{n}$ раскладывается по факторной базе. Если не раскладывается, то убрать их из рассмотрения. Если раскладывается, то собираем вместе все $Q_i$. Всего надо найти $\pi(B)+2$ таких $Q_i$ ($\pi(B)$ - число простых чисел, не превосходящих $B$).
\item[\rm 3.] Найти подсистему, приводящую к $x^2 \equiv y^2 \pmod{n}$. 

Если окажется, что $x \equiv \pm y$ (не повезло), то найти новое $Q_i$ (решить снова)
\end{enumerate}

\begin{note}
Если $n~10^{130}$, то $B~10^7$.
\end{note}

\begin{example}
$n=85907$ \, $B=10$

$\left\lceil \sqrt{3 \cdot 85907}\right\rceil=507$ \, ($a=3$, $b=0$)

$\left\lceil \sqrt{8 \cdot 85907}\right\rceil=829$

$501^2 \equiv -6720 = -1 \cdot 2^6 \cdot 3 \cdot 5 \cdot 7$ \, (берем близкие числа к 507, добавляя $b$ в $Q_i$, здесь $b=-6$)

$507^2 = -672 = -1 \cdot 2^5 \cdot 3 \cdot 7$

$508^2 = 343 = 7^3$

$829^2 = -15 = -1 \cdot 3 \cdot 5$

Хотим взять и перемножить какие-то числа слева. Получим квадрат. Хотим, чтобы и справа был квадрат. Для этого надо, чтобы степени сичел из факторной базы были четные.

Вводим коэффициенты $\alpha_i \in {\ZZ_2}$:

$\alpha_i=0$ - не берем число в произведение
$\alpha_i=1$ - берем.

Получаем:

$501^2 \cdot 507^2 \cdot 508^2 \cdot 829^2 = (-1)^{\alpha_1 + \alpha_2 + \alpha_4} \cdot 2^{6 \alpha_1 + 5 \alpha_2} \cdot 3^{\alpha_1 + \alpha_2 + \alpha_4} \cdot 5^{\alpha_1 + \alpha_4} \cdot 7^{\alpha_1 + \alpha_2 + 3 \alpha_3}$

Хотим, чтобы

$$
\alpha_1 + \alpha_2 + \alpha_4 \equiv 0 \pmod{2}
$$
$$
6 \alpha_1 + 5 \alpha_2 \equiv 0 \pmod{2}
$$
$$
\alpha_1 + \alpha_2 + \alpha_4 \equiv 0 \pmod{2}
$$
$$
\alpha_1 + \alpha_4 \equiv 0 \pmod{2}
$$
$$
\alpha_1 + \alpha_2 + 3 \alpha_3 \equiv 0 \pmod{2}
$$

Это система линейных однородных уравнений в поле ${\ZZ_2}$. Система $5 \times 4$. Скорее всего единственное тривиальное решение, но может быть и нет. Если взять число $Q_i$ на 1 больше, чем число элементов в факторной базе, то число неизвестных будет больше, чем число уравнений, и всегда будет существовать нетривиальное решение.
\end{example}

\section{Квадратичное решето}
{\it Померанц, 1982}

Возникает вопрос, как ускорить поиск $Q_i$. 

Пусть $a$ - фиксировано.

$Q_b = (\left\lceil \sqrt{an}+ b\right\rceil)^2 \mod{n}$

Можно ли ускорить процедуру нахождения тех $Q_b$, для которых возможно разложение по факторной базе?

Померанц предложил рассматривать массив $S$:

$$
\begin{array}{c|c|c|c|c|c|c}
\hline
\dots & S[-2] & S[-1] & S[0] & S[1] & S[2] & \dots \\
\hline
\end{array}
$$

$S\left[b\right]=\log{Q_b}$ - записывается в ячейках массива.

Для любого $p$ из факторной базы найти $b \in {\ZZ_p}$, такие что

$Q_b \vdots p \Longleftrightarrow (\left\lceil \sqrt{an}\right\rceil + b )^2 \mod n \equiv 0 \pmod{p}$

Возникает вопрос, сколько таких $b$ для заданного $p$ из факторной базы? ($p$ - простое).

$(\left\lceil \sqrt{an}\right\rceil + b )^2 - qn \equiv 0 \pmod{p}$

Так как $0<b<p$, то $q$ можем найти. Все известно, кроме $b$. Надо решить квадратное уравнение в поле ${\ZZ_p}$.

Если $\left(\frac{qn}{p}\right) = 1$ (вычет), то 2 решения $b_1$ и $b_2$.

Если $\left(\frac{qn}{p}\right) = -1$, то нет решений. Эти значения $a$ и $b$ бесполезны.

В факторной базе надо оставить только вычеты.

Для всех $i$ 
$$
S[b_1 + ip] -= \log{p}
$$
$$
S[b_2 + ip] -= \log{p}
$$

Пытаемся разложить по факторной базе только те $Q_b$, для которых $S[b]\approx 0$

Эта процедура позволяет сократить время, хотя и не повлияет на порядок. но делить все равно будем меньше.
%Определение 2:
\begin{definition}
\label{screening}
Эта процедура называется {\em процедурой просеивания}.
\end{definition}
%Определение 3:
\begin{definition}
\label{QuadraticSieve}
Рассмотренный алгоритм называется {\em алгоритмом квадратичного решета}.
\end{definition}

Алгоритм квадратичного решета находится на втором месте среди алгоритмов факторизации.
Его сложность есть $O\left(e^{c \sqrt{\ln{n} \cdot ln{\ln{n}}}}\right)$

\section{Использование цепных дробей}

Хотим найти нетривиальное решение сравнения
$$
x^2 \equiv y^2 \pmod{n}
$$
%Определение 4:
\begin{definition}
\label{ChainFrac}
{\em Цепная дробь} - это дробь вида
$$
\theta = a_1 + \frac{1}{\theta_1} = a_1 + \frac{1}{a_2 + \frac{1}{\theta_2}} = a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \frac{1}{\theta_3}}}=\cdots,
$$
где $\theta>0$, $\theta \in {\RR}$.
\end{definition}

Если исходное число - рациональное, то разложение рано или поздно закончится. Если действительное, то может бесконечно продолжаться.

Заметим, что $a_1=\left\lfloor \theta \right\rfloor$.

Что будет, если разложение оборвем в каком-то месте?

$\frac{1}{\theta_i}\longrightarrow 0$, то получим в правой части

$\frac{p_i}{q_i}$ - $i$-я подходящая дробь для числа $\theta$. Это очень хорошее рациональное приближение для $\theta$.

Теорема Лагранжа говорит, что $\left|\theta - \frac{p_i}{q_i}\right|\leq \frac{1}{q_i^2}$

\begin{example}
$\pi = 3 + \frac{1}{7+\frac{1}{15+\frac{1}{\theta_3}}}$

$\frac{p_1}{q_1}=3$

$\frac{p_2}{q_2}=\frac{22}{7}$

$\frac{p_3}{q_3}=\frac{333}{106}$

$\frac{p_4}{q_4}=\frac{355}{113}$. Эту подходящую дробь знали уже в Др.Китае.
\end{example}

Если $\theta=\frac{p}{q}$, то разложение в цепную дробь - алгоритм Евклида для нахождения $НОД(p,q)$.

В алгоритме мы в качестве $Q$ брали $Q=x$. Чтобы они были меньше и корень по возможности извлекался, $Q$ можно выбирать, исходя из следующего:

$\sqrt{n}\approx \frac{p_i}{q_i}$

Используя теорему Лагранжа:

$\left|\frac{p_i^2}{q_i^2} - n\right|=\left|\frac{p_i}{q_i}-\sqrt{n}\right|\left(\frac{p_i}{q_i}+\sqrt{n}\right)\approx 2\sqrt{n}\left|\frac{p_i}{q_i}-\sqrt{n}\right|\leq\frac{2\sqrt{n}}{q_i^2}$

Отсюда 
$$
\left|p_i^2 - q_i^2 n\right| \leq 2\sqrt{n}
$$
$$
p_i^2 \mod{n} \leq 2\sqrt{n}
$$

Приходим к алгоритму, который предложили Brillhart, Morrison в 1975.
Надо искать подходящие дроби для квадратичной иррациональности.

\begin{example}
$\theta=\sqrt{45}$
$$
a_1=6 \Longrightarrow \theta_1 = \frac{1}{\sqrt{45}-6}=\frac{\sqrt{45}+6}{9}
$$
$$
a_2=1 \Longrightarrow \theta_2 = \frac{9}{\sqrt{45}-3}=\frac{\sqrt{45}+3}{4}
$$
$$
a_3=2 \Longrightarrow \theta_3 = \frac{4}{\sqrt{45}-5}=\frac{\sqrt{45}+5}{5}
$$
$$
\theta=6+\frac{1}{1+\frac{1}{2+\frac{1}{2+\cdots}}}
$$
\end{example}

\begin{theorem}
\label{ChainFracTheorem}
Цепная дробь периодическая, то есть последовательность $a_1$, $a_2 \cdots$, начиная с некоторого момента начинает повторяться $\Longleftrightarrow$ иррациональность $\theta$ является квадратичной иррациональностью, то есть
$$
\theta = \frac{a+\sqrt{D}}{b}
$$
\end{theorem}
\begin{proof}
Теорема слеует из того факта, что числитель и знаменатель ограничены. Знаменатель есть $\sqrt{45}$ - (что-то меньшее). Числитель ограничен значением $2\cdot\sqrt{45}+1$ 
\end{proof}

\end{document}