This question is from Quadratic Sieve Factorization Method. Didn't find the solution on the web also. And not aware of how to solve such questions.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
We first take numbers $m$ close to $\sqrt n=\sqrt{4633}\approx 68.066$ and check to see if $m^2-n$ splits into factors contained in $B$ (we discard numbers that don't split in this way. Thus: $$m= 67:\quad\quad m^2-n=-144=(-1)^12^43^2$$ $$m= 68:\quad\quad m^2-n=-9=(-1)^12^03^2$$ $$m= 69:\quad\quad m^2-n=128=(-1)^02^73^0$$
We then take the successful splittings and write down the indices as row vectors: $$m=67:\quad\quad (1,4,2)$$ $$m=68:\quad\quad (1,0,2)$$ $$m=67:\quad\quad (0,7,0).$$
We reduce these vectors mod 2: $$m=67:\quad\quad (1,0,0)$$ $$m=68:\quad\quad (1,0,0)$$ $$m=67:\quad\quad (0,1,0)$$ and then look for a linear combination of the vectors that adds to $(0,0,0)\pmod 2$ (which corresponds to a product of the numbers that is a square). We can do this with linear algebra or we can just observe that the first two vectors are the same and so add to the zero vector mod 2.
For the vectors identified we multiply together the corresponding $m$ values modulo $n$ and add the unreduced vectors: $$67\times 68=4556;\quad\quad (1,4,2)+(1,0,2)=(2,4,4)$$ we halve the summed vector and then create the corresponding product of elements of $B$: $$(2,4,4)/2=(1,2,2)\rightarrow (-1)^12^23^2=-36.$$
All of this tells us that $4556^2-(-36)^2\equiv 0\pmod{4633}$ (this can be checked easily). This means that $4556+36$ and $4556-36$ both share divisors with $4633$ (hopefully non-trivial ones). Sure enough $$\mathrm{GCD}(4633,4556+36)=41,\quad\quad\mathrm{GCD})(4633,4520)=113.$$
We have now recovered the factorisation $4633=41\times 113$.
