It is perhaps a bit depressing that after all that work, Algorithm SEF only
succeeds (in the worst case) with probability 1/2. Of course, to reduce the
failure probability, we can simply repeat the entire computation - with \(\ell\)
repetitions, the failure probability drops to \(2^{-\ell}\). However, there is a
better way to reduce the failure probability. Suppose that in stage \(1,\)
instead of collecting \(k+2\) relations, we collect \(k+1+\ell\) relations, where
\(\ell \geq 1\) is an integer parameter.
(a) Show that in stage \(2,\) we can use Gaussian elimination over
\(\mathbb{Z}_{2}\) to find inte-
ger vectors
$$
c^{(j)}=\left(c_{1}^{(j)}, \ldots, c_{k+1+\ell}^{(j)}\right)
\in\\{0,1\\}^{\times(k+1+\ell)}(j=1, \ldots, \ell)
$$
such that
\- over the field \(\mathbb{Z}_{2},\) the images of the vectors \(c^{(1)},
\ldots, c^{(\ell)}\) in \(\mathbb{Z}_{2}^{\times(k+1+\ell)}\) form a linearly
independent family of vectors, and
\(-\) for \(j=1, \ldots, \ell,\) we have
$$
c_{1}^{(j)} v_{1}+\cdots+c_{k+1+\ell}^{(j)} v_{k+1+\ell} \in 2
\mathbb{Z}^{\times(k+2)}
$$
(b) Show that given vectors \(c^{(1)}, \ldots, c^{(\ell)}\) as in part (a), if
for \(j=1, \ldots, \ell,\) we
set
$$
\begin{array}{c}
\left(e_{1}^{(j)}, \ldots, e_{k+1}^{(j)}\right) \leftarrow c_{1}^{(j)}
v_{1}+\cdots+c_{k+1+\ell}^{(j)} v_{k+1+\ell} \\
\alpha^{(j)} \leftarrow \prod_{i=1}^{k+1+\ell} \alpha_{i}^{c_{i}^{(j)}},
\beta^{(j)} \leftarrow \pi_{1}^{e_{1}^{(j)} / 2} \cdots \pi_{k}^{e_{k}^{(j)} /
2} \delta^{-e_{k+1}^{(j)} / 2}, \gamma^{(j)} \leftarrow \alpha^{(j)} /
\beta^{(j)},
\end{array}
$$
then the family of random variables \(\gamma^{(1)}, \ldots, \gamma^{(\ell)}\) is
mutually independent, with each \(\gamma^{(j)}\) uniformly distributed over the
set of all square roots of 1 in \(\mathbb{Z}_{n}^{*},\) and hence at least one
of \(\operatorname{gcd}\left(\operatorname{rep}\left(\gamma^{(j)}-1\right),
n\right)\) splits \(n\) with probability at least \(1-2^{-\ell}\)
