1
$\begingroup$

I am reading the Quadratic Sieve algorithm from Silverman's mathematical Cryptography book.

I have understood almost everything in the algorithm except the part where he uses Gaussian Elimination to narrow down those numbers which can be tried with the next step to find the factors.

We have the list - list of smooth numbers I understand how this list is formed.

From this list, he forms the matrix - Matrix formed from exponents mod 2 - I understood the above - how he forms the matrix.

After this he says

The next step is to solve the system of linear equations in Table 3.5. This can be done by standard Gaussian elimination, always keeping in mind that all computations are done modulo 2. The set of solutions turns out to be an F2-vector space of dimension 8. A basis for the set of solutions is given by the following 8 vectors, where we have written the vectors horizontally, rather than vertically, in order to save space:

And then he gets these vectors as the solution

$v1 = (0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0),$

$v2 = (0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0),$

$v3 = (0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0),$

$v4 = (1,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0),$

$v5 = (1,0,1,0,1,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0),$

$v6 = (1,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,0),$

$v7 = (1,0,0,0,0,0,1,1,0,0,0,0,1,0,0,0,0,0,1,0),$

$v8 = (1,0,0,0,0,0,0,1,0,0,0,1,1,0,0,0,0,0,0,1)$


So, we have a Matrix $M_{15X20}$ & a vector with 20 rows. So from these, how do we get 8 vectors each with 20 elements?

Shouldn't we get $u_1$ to $u_{20}$. What exactly are these vectors & how do get to it?


I understand basic gaussian elimination to solve Linear Algebra equations - i.e if you have 3 variables (x, y, z) & you have 3 equations, then you can use Gaussian elimination to solve it. I understand how it works, but I usually use SageMath to do it.

M.solve_right(v) - where M is the Matrix & v is the vector.

In this case, since it's mod 2, I will define the Matrix M & vector v in a Ring of 2 & do it. But if I try with the the above matrix & vector in a ring of 2, I just get 1 vector as the answer with 20 elements. And it seems logical because I have a 15x20 Matrix & a 20 element vector. So how is the book doing whatever it's doing?

$\endgroup$
5
  • $\begingroup$ I only remember that there is a special algorithm to find the needed congruences (containing hopefully at least one leading to a nontrivial factor). Something like "Lanzelot's block method". But I think this example is only an illustration. The zero vector can be explained : All exponents corresponding to the prime factors of $x^2 \mod n$ must be even because the result should be a perfect square. $\endgroup$
    – Peter
    Aug 4 '21 at 12:10
  • $\begingroup$ @Peter - I understand the part of the algorithm to find the needed congruences. I also understand the Zero Vector. i.e. I understand the Matrix (15x20), I understand the 20 element vector. What I don't understand it those 8 vectors (v1 to v8) & How you get them $\endgroup$
    – user93353
    Aug 4 '21 at 13:40
  • $\begingroup$ Is this the Hoffstein, Pipher, and Silverman book? Which problem or is it a different book? $\endgroup$
    – Moo
    Aug 5 '21 at 11:49
  • $\begingroup$ Yes, it's that book @Moo $\endgroup$
    – user93353
    Aug 5 '21 at 12:20
  • $\begingroup$ @Moo Chapter 3 (Integer Factorization & RSA). This is at the end of Section 3.6 (Factorization by diff of squares). This is the page before 3.7 starts. Page 143. $\endgroup$
    – user93353
    Aug 5 '21 at 12:32
2
$\begingroup$

Though this is clothed in number theory trappings, this is a linear algebra question. At its core, this question is How do we find a basis for the kernel of a linear transformation using Gaussian elimination? Here is one possible answer.

For a smaller example, we might consider the equation $$ A \vec{x} = \vec{0} \tag{1}$$ where $$ A = \left(\begin{array}{rrrr} 1 & 2 & 3 & 4 \\ 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3 \\ 3 & 4 & 5 & 6 \end{array}\right).$$ This is like your equation, except over $\mathbb{C}$ instead of $\mathbb{F}_2$, and smaller dimension. Finding all such $\vec{x}$ is exactly the same as computing the kernel, and Gaussian elimination is very commonly used to find a basis for the kernel. Here, a basis for the kernel are the two vectors $$ v_1 = \left(1,\,0,\,-3,\,2\right), \quad v_2 = \left(0,\,1,\,-2,\,1\right), $$ where I've written them as row vectors, but think of them as column vectors.

All vectors of the form $a v_1 + b v_2$ for any $a, b$ are solutions to $(1)$.

Since you note that you want to compute this in sage, I'll note that you do this with the following:

m = matrix([[1, 2, 3, 4], [1, 1, 1, 1], [0 ,1, 2, 3], [3, 4, 5, 6]])
m.T.kernel()  

An oddity here is using m.T. In sage, m.kernel() gives the left kernel, i.e. the solutions to $\vec x A = \vec 0$. But you've given an equation for the right kernel. Taking the transpose of the matrix first fixes this.

For your particular problem, you can do it in sage with

F = Zmod(2)
m = matrix(F, [
  [1 0 1 0 0 1 1 1 1 1 0 0 1 1 1 1 0 0 0 1],
  [0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 1],
  [1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0],
  [0 0 1 0 0 1 0 0 1 1 1 1 0 1 0 0 0 0 0 1],
  [1 1 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0],
  [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0],
  [0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 0 1 1 0 0],
  [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0],
  [1 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 1 0],
  [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0],
  [0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0],
  [0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1],
  [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0],
  [0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0],
  [0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0],
])
m.T.kernel()

I'll note that this gives a basis of $8$ vectors for the kernel, though this basis probably isn't the same basis that Hoffstein, Pipher, and Silverman give. Nonetheless, this is sufficient.

I don't think this is deterministic and it might change between versions of sage, but the kernel I got back was generated by $$\begin{align} &\left(1,\,0,\,0,\,0,\,0,\,0,\,0,\,0,\,1,\,0,\,0,\,0,\,0,\,1,\,1,\,0,\,0,\,0,\,1,\,0\right), \\ &\left(0,\,1,\,0,\,0,\,0,\,1,\,0,\,0,\,0,\,1,\,1,\,0,\,0,\,1,\,1,\,0,\,0,\,0,\,1,\,0\right), \\ &\left(0,\,0,\,1,\,0,\,0,\,0,\,0,\,0,\,1,\,0,\,1,\,0,\,0,\,1,\,1,\,0,\,0,\,0,\,1,\,0\right), \\ &\left(0,\,0,\,0,\,1,\,0,\,0,\,0,\,0,\,1,\,1,\,1,\,0,\,0,\,1,\,1,\,0,\,0,\,0,\,1,\,0\right), \\ &\left(0,\,0,\,0,\,0,\,1,\,0,\,0,\,0,\,0,\,0,\,1,\,0,\,0,\,1,\,1,\,0,\,0,\,0,\,1,\,0\right), \\ &\left(0,\,0,\,0,\,0,\,0,\,0,\,1,\,0,\,0,\,0,\,0,\,0,\,0,\,0,\,1,\,0,\,0,\,0,\,1,\,0\right), \\ &\left(0,\,0,\,0,\,0,\,0,\,0,\,0,\,1,\,1,\,0,\,0,\,0,\,1,\,1,\,0,\,0,\,0,\,0,\,1,\,0\right), \\ &\left(0,\,0,\,0,\,0,\,0,\,0,\,0,\,0,\,0,\,0,\,0,\,1,\,0,\,0,\,1,\,0,\,0,\,0,\,0,\,1\right). \end{align}$$

And somewhat surprisingly, taking the first basis vector is sufficient to factor the number. Explicitly,

# The list of numbers used in PHS
ps = (3129, 3130, 3131, 3166, 3174, 3215, 3313, 3449,
      3481, 3561, 4394, 4425, 4426, 4432, 4442, 4468,
      4551, 4595, 4651, 4684)
basisvector1 = (1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0)
numlist = [v[1] for v in list(zip(basisvector1, ps)) if v[0] == 1]
# numlist = [3129, 3481, 4432, 4442, 4651]

N = 9788111
a = prod(numlist) % N      # a = 5710850

# I redo a bit of the work done earlier in the book, reacquiring the factorization:
# the product below is guaranteed to be a square of an integer by the
# linear algebra above.
b = sqrt(prod([num * num % N for num in numlist])) % N
b = 8758842

gcd(N, a - b)              # 2741

This finds the factor $2741$ of $N = 9788111$ (which factors as $3571 \cdot 2741$).

$\endgroup$
2
  • $\begingroup$ Thank you. It's going to take me a little while to understand this! $\endgroup$
    – user93353
    Aug 5 '21 at 3:19
  • 1
    $\begingroup$ Thank you very much again $\endgroup$
    – user93353
    Aug 9 '21 at 12:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.