User:Decrypt3/WIP2

Data collection

$\left\lfloor {\sqrt {55}}\right\rfloor =7$

Now, we let x equal ...−2, −1, 0, 1, 2... and check if the resulting y is 5-smooth. Keep in mind that −1 is included in the factor base.

$4^{2}\equiv 16=2^{4}\cdot 3^{0}\cdot 5^{0}{\pmod {55}}$

$5^{2}\equiv -30=-1\cdot 2^{1}\cdot 3^{1}\cdot 5^{1}{\pmod {55}}$

$6^{2}\equiv -19=-1\cdot 19{\pmod {55}}$

$7^{2}\equiv -6=-1\cdot 2^{1}\cdot 3^{1}\cdot 5^{0}{\pmod {55}}$

$8^{2}\equiv 9=2^{0}\cdot 3^{2}\cdot 5^{0}{\pmod {55}}$

$9^{2}\equiv 26=2^{1}\cdot 13{\pmod {55}}$

$10^{2}\equiv 45=2^{0}\cdot 3^{2}\cdot 5^{1}{\pmod {55}}$

We have to collect, at least, one more full relation than there are primes in the factor base to guarantee the presence of a congruence of squares. We now have 4 full relations, with 4 primes in the factor base. In fact, it is a standard result from linear algebra that we need t + 1 independent full relations to guarantee a linear dependence (a relationship that will yield a congruence of squares), where t is the size of the factor base. When t is large is nearly impossible for the relations being found to be independent, so we compute more full relations in order to overcome this problem.

Notice that the y(6) and y(9), though they both contain large primes, contain different large primes and so cannot be combined into a full relation. We want to find a linear combination of the exponent vectors that is equal to the zero vector mod 2, as follows:

${\begin{bmatrix}1&1&0&0\\1&1&0&0\\1&1&2&2\\1&0&0&1\end{bmatrix}}{\begin{bmatrix}c_{1}\\c_{2}\\c_{3}\\c_{4}\end{bmatrix}}\equiv {\begin{bmatrix}0\\0\\0\\0\end{bmatrix}}{\pmod {2}}$

We can use Gaussian elimination to achieve this, after first reducing the matrix modulo 2.

${\begin{bmatrix}{cccc|c}1&1&0&0&0\\1&1&0&0&0\\1&1&0&0&0\\1&0&0&1&0\end{bmatrix}}\equiv {\begin{bmatrix}c_{1}\\c_{2}\\c_{3}\\c_{4}\end{bmatrix}}$

${\begin{bmatrix}{cccc|c}1&1&0&0&0\\1&1&0&0&0\\1&1&0&0&0\\1&0&0&1&0\end{bmatrix}}\equiv {\begin{bmatrix}c_{1}\\c_{2}\\c_{3}\\c_{4}\end{bmatrix}}$