Dixon's Factorization Method Modulo Question

Question

Looking at Wikipedia's example for Dixon's Factorization Method, it shows the following.

We will try to factor N = 84923 using bound B = 7. Our factor base is then P = {2, 3, 5, 7}. We then search random for integers between ceil(sqrt(84923), which equals 292 and N whose squares are B-smooth.

At this point, my understanding is that a number x is B-smooth if its factors only include P, which equals {2, 3, 5, 7} in this example.

513^2 mod 84923 = 8400 = 2^4 * 3 * 5^2 * 7
537^2 mod 84923 = 33600 = 2^6 * 3 * 5^2 * 7

Is there any particular factorization that's used to get 8400's and 33600's factors?

(513 * 537)^2 mod 84923 = (275831)^2 mod 84923
= (84923 * 3 + 20712)^2 mod 84923
= (84923 *3)^2 + 2 * (84923 * 3 * 20712) + 20712^2 mod 84923 = 0 + 0 + 20712^2 mod 84923

Please explain the second, third and fourth lines. I don't understand the transition from the first to the second line.

That is,
20712^2 mod 84923 = (2^5 * 3 * 5^2 * 7)^2 mod 84923 = 16800^2 mod 84923

The resulting factorization is
84923 = gcd(20712 - 16800, 84923) x gcd(20712 + 16800, 84923) = 163 * 521

Answer 1

To calculate \begin{align*} 513^2&\mod 84923=8400=2^4\cdot 3\cdot5^2\cdot 7\\ 537^2&\mod 84293=33600=2^6\cdot 3\cdot5^2\cdot 7 \end{align*} there is no particular factorisation algorithm necessary, since we have a small factor base $P=\{2,3,5,7\}$ and we can take each prime and calculate in a brute-force manner if and which powers of the primes in $P$ divide $8400$ resp. $33600$ evenly.

In the calculation below we apply some rules of modular arithmetic and division of integers

\begin{align*} (513\cdot537)^2&\mod 84923\\ &=\color{blue}{275481}^2\mod 84923\tag{1}\\ &=(84923\cdot 3+20712)^2\mod 84923\tag{2}\\ &=(84923\cdot3)^2+2\cdot(84923\cdot3\cdot20712)+20712^2\mod 84923\tag{3}\\ &=0+0+20712^2\mod 84923\tag{4} \end{align*}

Comment:

• In (1) note that $513\cdot 537=275481$ (and not $275831$)

• In (2) we use the Euclidean algorithm $275481=q*84923+r$ with $q\in \mathbb{Z}$ and $0\leq r<84923$ ($q=3$ and remainder $r=20712$)

• In (3) we apply the binomial theorem $(a+b)^2=a^2+2ab+b^2$

• In (4) we use

\begin{align*} a^n\mod b&=(a\mod b)^n\\ (a\cdot b)\mod c&=(a\mod c)\cdot (b\mod c) \end{align*} together with the fact that integer multiples of the modulus $84923$ are zero.

[2015-06-01]: A small note according to OPs comment:

The wiki page states at the end of the example section

\begin{align*} 20712^2 \mod 84923=(2^5\cdot 3\cdot 5^2\cdot 7)^2\mod 84923 \tag{5} \end{align*}

Note: This statement is some kind of summary of the calculations in the example above, since

by some (presumably rather simple) algorithm we could find the prime factor decomposition of the randomly chosen values $513^2$ and $537^2$

\begin{align*} 513^2&\mod 84923=8400=2^4\cdot 3\cdot 5^2\cdot 7\\ 537^2&\mod 84923=33600=2^6\cdot 3\cdot 5^2\cdot 7\\ \end{align*} Therefore we obtain \begin{align*} &(513\cdot 537)^2\mod 84923\\ &\qquad=(2^4\cdot 3\cdot 5^2\cdot 7)\cdot(2^6\cdot 3\cdot 5^2\cdot 7)\mod 84923\\ &\qquad=(2^{10}\cdot 3^2\cdot 5^4\cdot 7^2) \mod 84923\\ &\qquad={(2^5\cdot 3\cdot 5^3\cdot 7)}^2 \mod 84923\tag{6} \end{align*}

We have already derived in steps (1) to (4)

\begin{align*} (513\cdot 537)^2\mod 84923=20712^2 \mod 84923\tag{7} \end{align*}

So, putting the RHS of (6) and (7) together gives the statement in wiki's example section.

Another view of the same thing is

\begin{align*} 20712^2&=(2^3\cdot3\cdot863)^2=428986944=5051\cdot84923 + \color{blue}{40871}\\ 16800^2&=(2^5\cdot3\cdot5^2\cdot7)^2=282240000=3323\cdot 84923+\color{blue}{40871} \end{align*} Since both $20712^2$ and $16800^2$ have the same remainder $\color{blue}{40871}$ by division of $84923$, we observe

\begin{align*} 20712^2\mod 84923 &= 40871\\ 16800^2\mod 84923 &= 40871 \end{align*} or equivalently \begin{align*} (2^3\cdot3\cdot863)^2\mod 84923 &= 40871\\ (2^5\cdot3\cdot5^2\cdot7)^2\mod 84923 &= 40871 \end{align*}