Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am working through the example in implementation of the quadratic sieve, and I have got stuck at the very last part: the matrix processing. In the example we must find the vector $S$ by left null space.

Example

However if we transpose the matrix A and attempt to apply Gaussian Elimination to find the solution to S as in the example, the resulting solution does not match up with the answer in the example.

enter image description here

What am I missing here? Is the "mod 2" part left out of the null space method or applied later to the resulting solution?

How is the resulting $S$ vector then used in the next two equations we find:

enter image description here

enter image description here

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

There might be a more instructive way to do this!

We want to find: $S = \left[ \begin{array}{ccc} a & b & c \end{array} \right]$ given $A = \left[ \begin{array}{ccc} 0 & 0 & 0 & 1\\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \end{array} \right]$

such that:

$$ S \cdot A \equiv \left[ \begin{array}{ccc} 0 & 0 & 0 & 0 \end{array} \right] \pmod 2$$

so, multiplying the $S$ and $A$, yields a $3x4$:

$$\tag 1 S \cdot A = \left[ \begin{array}{ccc} 0 & b & c\\ 0 & b & c\\ 0 & b & c\\ a & 0 & c \end{array} \right] \equiv \left[ \begin{array}{ccc} 0 & 0 & 0 & 0 \end{array} \right] \pmod 2$$

From $(1)$, we get a set of modular equations (given that we have three duplicates):

$$ b + c \equiv 0 \pmod 2$$ $$ \tag 2 a + c \equiv 0 \pmod 2$$

So, solving the system in $(2)$ by whatever method you are comfortable with, we get

$$S = \left[ \begin{array}{ccc} a & b & c \end{array} \right] = \left[ \begin{array}{ccc} 1 & 1 & 1 \end{array} \right]$$

This is, apparently, telling us that the product of all 3 equations yields a square$\pmod N$, meaning we use the table they calculated above and take the product of all three factors for both sides from $X + 124$ and $Y$ (table they calculated earlier).

So, forming the product of all three (since we have S with all $1's$), $Y's \equiv$ the product of the three $X + 24's$, yielding, $29 \cdot 782 \cdot 22678 = 22678^2$ and $124^2 \cdot 127^2 \cdot 195^2 = 3070860^2$, and then equating sides, we arrive at:

$$22678^2 \equiv 3070860^2 \pmod {15347}$$

Update:

I am not sure it is a good idea to rely on an example on the Wiki for such a complex algorithm. I just got home and looked in "Prime Numbers, A Computational Perspective", by Crandall and Pomerance. In it, they have spelled out the algorithm and all of the nuances!

You can also find additional examples in these papers on NFS:

NFS 1

NFS 2

Regards

share|improve this answer
    
You put a lot of work into this! $+1(0000000)$ –  amWhy May 5 '13 at 0:52
    
@amWhy: I think the Wiki has many excellent things on it, but sometimes it makes rather provocative statements, with no detail. It seems to have become a very rich source for MSE problems! :-) I really had to research and figure out what the heck this algorithm was doing from their description, but it was just one of those things that was itching to be figured out! –  Amzoti May 5 '13 at 0:58
    
Yes, I agree...It's Wiki is a wonderful concept and great resource...but... (And I too have noticed a lot of "Wiki" based questions!) –  amWhy May 5 '13 at 0:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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