bachelor/book/williams+1.tex

\chapter{Williams' $p+1$ factorization method \label{chap:william+1}}

Analogously to Pollard's $p-1$ factorization described in chapter
~\ref{chap:pollard-1}, this method will allow the determination of the divisor
$p$ of a number $N$, if $p$ is such that $p+1$ has only small prime divisors.
This method was presented in ~\cite{Williams:p+1} together with the results of
the application of this method to a large number of composite numbers.

\section{Background on Lucas Sequences}

Let us call \emph{Lucas Sequence} the recurrence relation with parameters $\tau,
\upsilon$
\begin{align*}
  \begin{cases}
    U_0 = 0 \\
    U_1 = 1 \\
    U_n = \tau U_{n-1} - \upsilon U_{n-2}
  \end{cases}
  \quad
  \begin{cases}
    V_0 = 2 \\
    V_1 = \tau \\
    V_n = \tau V_{n-1} - \upsilon V_{n-2}
  \end{cases}
\end{align*}
%% <https://en.wikipedia.org/wiki/Lucas_sequence> thanks wikipedia
For respectively different values of $\tau, \upsilon$, Lucas Sequences have
specific names:

\begin{tabular}{c l@{\hskip 0pt} l@{\hskip 1pt} l l l}
  $\bullet$ & $U($ & $\tau=1,$ & $\upsilon=-1)$ & \emph{Fibonacci numbers}; \\
  $\bullet$ & $V($ & $\tau=1,$ & $\upsilon=-1)$ & \emph{Lucas numbers}; \\
  $\bullet$ & $U($ & $\tau=3,$ & $\upsilon=2)$ & \emph{Mersenne numbers}.\\
\end{tabular}
\\
\\
For our purposes, $U_n$ is not necessary, and $\upsilon=1$.\footnote{
  Williams justifies this choice stating that choosing to compute a $U_n$ sequence
  is far more computationally expensive than involving $V_n$; for what
  concerns $\upsilon$, that simplifies Lehmer's theorem with no loss of
  generality. For further references,
  see \cite{Williams:p+1} \S 3.}
In order to simplify any later theorem, we just omit $U_n$, and assume $\upsilon
= 1$.
Therefore, the latter expression becomes:
\begin{equation}
  \label{eq:williams:ls}
  \begin{cases}
    V_0 = 2 \\
    V_1 = \tau \\
    V_n = \tau V_{n-1} - V_{n-2} \\
  \end{cases}
\end{equation}

Two foundamental properties interpolate terms of Lucas Sequences, namely
\emph{addition} and \emph{duplication} formulas:
\begin{align}
  & V_{n+m} = V_nV_m - V_{m-n} \label{eq:ls:addition} \\
  & V_{2n} = V_n^2 - 2 \label{eq:ls:duplication}
\end{align}

All these identities can be verified by direct substitution with
\ref{eq:williams:ls}. What's interesting about the ones of above, is that we can
exploit them to efficiently compute the product $V_{hk}$ if we are provided with
`$V_k$ by considering the binary representation of the number
$h$. In other words, we can consider each bit of $h$, starting from second most
significant one: if it is zero, we compute $\angular{V_{2k}, V_{(2+1)k}}$ using
\ref{eq:ls:duplication} and \ref{eq:ls:addition} respectively; otherwise we
compute $\angular{V_{(2+1)k}, V_{2(k+1)}}$ using \ref{eq:ls:addition} and
\ref{eq:ls:duplication}.

\begin{algorithm}[H]
  \caption{Lucas Sequence Multiplier}
  \begin{algorithmic}[1]
    \Function{Lucas}{$V, a, N$}
      \State $V_1 \gets V$
      \State $V_2 \gets V^2 - 2 \pmod{N}$

      \For{each bit $b$ in $a$ to right of the MSB}
        \If{$b$ is $0$ }
          \State $V_2 \gets V_1V_2 - V \pmod{N}$
          \Comment by addition %% \ref{eq:ls:addition}
          \State $V_1 \gets V_1^2 -2 \pmod{N}$
          \Comment by duplication %% \ref{eq:ls:duplication}
        \ElsIf{$b$ is $1$}
          \State $V_1 \gets V_1V_2 - V \pmod{N}$
          \Comment by addition %% \ref{eq:ls:addition}
          \State $V_2 \gets V_2^2 -2 \pmod{N}$
          \Comment by duplication %% \ref{eq:ls:duplication}
        \EndIf
      \EndFor
      \State \Return $V_1$
    \EndFunction
  \end{algorithmic}
\end{algorithm}

Finally, we need the following (\cite{Williams:p+1} \S 2):
\begin{theorem*}[Lehmer]
  Let $\Delta$ be $\tau^2-4$;
  if $p$ is an odd prime and the Legendre symbol
  $\varepsilon = \legendre{\Delta}{p}$, then:
  \begin{align*}
%%  &  U_{(p - \varepsilon)m} \equiv 0 \pmod{p} \\
  &  V_{(p - \varepsilon)m} \equiv 2 \pmod{p}
  \end{align*}
\end{theorem*}



\begin{remark}
  From number theory we know that the probability that
  $P(\varepsilon = -1) = \rfrac{1}{2}$.
  There is no reason to restrict ourselves to
  $\legendre{\Delta}{p} = -1$.
  In the alternative case of $\varepsilon = 1$, the factorization yields the
  same factors as Pollard's $p-1$ method, but slowerly.
  For this reason it is advisable to first attempt the attack presented in the
  previous chapter \cite{Williams:p+1}whenever we look up for a $p-1$
  factorization.
\end{remark}


\section{Dressing up}

At this point the factorization proceeds just by substituting the
exponentiation and Fermat's theorem with Lucas sequences and Lehmer's theorem
introduced in the preceeding section. If we find a $Q$ satisfying $p+1 \mid Q
\text{ or } p-1 \mid Q$ then, due to Lehmer's theorem $p \mid V_Q -2$ and thus
$\gcd(V_Q -2, N)$ is a non-trial divisor of $N$.

\begin{enumerate}[(i)]
\item take a random, initial $\tau = V_1$; now let the \emph{base} be
  $\angular{V_1}$.
\item take the $i$-th prime in $\mathcal{P}$, starting from $0$, and call it
  $p_i$;
\item assuming the current state is $\angular{V_k}$, compute the
  successive terms of the sequence using additions and multiplications formula,
  until you have $\angular{V_{p_ik}}$.
\item just like with the Pollard $p-1$ method, repeat step (iii) for $e =
  \ceil{\frac{\log N}{\log p_i}}$ times;
\item select $Q = V_k - 2 \pmod{N}$ and check the $gcd$ with $N$, hoping this
  leads to one of the two prime factors:
\begin{align}
  g = gcd(Q, N), \quad 1 < g < N \,.
\end{align}
If so, than we have finished, since $g$ itself and $\frac{N}{g}$
are the two primes factorizing the public  modulus.
Otherwise, if $g = 1$ we go back to to (ii), since $p-1 \nmid Q$ yet;
if $g = N$ start back from scratch, as $pq \mid g$.
%% riesel actually does not examine this case, strangely. However, it seems to
%% be fairly probable that.

\end{enumerate}



\begin{algorithm}
  \caption{Williams $p+1$ factorization}
  \begin{algorithmic}[1]
    \Require $\mathcal{P}$, the prime pool
    \Function{Factorize}{$N, \tau$}
      \State $V \gets \tau$
      \For{$p_i \strong{ in } \mathcal{P}$}
      \Comment step (i)
        \State $e \gets \log \sqrt{N} // \log p_i$
        \For{$e \strong{ times }$}
          \State $V \gets \textsc{lucas}(V, p_i, N)$
          \Comment step (ii)
          \State $Q \gets V -2$
          \State $g \gets \gcd(Q, N)$
          \Comment step (iii)
          \If{$g = 1$} \Return \strong{nil}
          \ElsIf{$g > 1$} \Return $g, N//g$
          \EndIf
        \EndFor
      \EndFor
    \EndFunction
  \end{algorithmic}
\end{algorithm}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: "question_authority"
%%% End: