# Somethings wrong with my Dickson factorization algorithm implementation

1. I use N = 89755 as a sample number;
2. I calculate the limit for my primes base M = sqrt(exp(sqrt(log(N)*log(log(N))))) = 14
3. I create primes base = {2,3,5,7,11,13} Loop:
4. Generate random B: sqrt(N) <= B <= N;
5. Generate A = (B*B) mod N;
6. Perform factorization of A according to the primes base(step3) with "trial division". If A factors fully with primes base, thus being a B-smooth number, store powers of canonical form to vector and save A,B and vector;
7. Perform 4-6 until I have more vectors than primes in the base after this stage i got
A:        B:        2:  3:  5:  7:  11: 13:
24750     52210     1   2   3   0   1   0
750       66270     1   1   3   0   0   0
86400     9190      7   3   2   0   0   0
900       68120     2   2   2   0   0   0
3696      47289     4   1   0   1   1   0
324       89737     2   4   0   0   0   0
87846     37689     1   1   0   0   4   0

1. Convert the resulting matrix of powers of canonical form to mod 2
A:        B:        2:  3:  5:  7:  11: 13:
24750     52210     1   0   1   0   1   0
750       66270     1   1   1   0   0   0
86400     9190      1   1   0   0   0   0
900       68120     0   0   0   0   0   0
3696      47289     0   1   0   1   1   0
324       89737     0   0   0   0   0   0
87846     37689     1   1   0   0   0   0

1. Here I should solve linear equations but I just check the matrix for rows that XOR togather to zeroes And I get rows
324       89737     0   0   0   0   0   0
900       68120     0   0   0   0   0   0


which are same as

324       89737     2   4   0   0   0   0
900       68120     2   2   2   0   0   0


that do

1. Calculate X and Y , where
> X = 2^((2+2)/2)*3^((4+2)/2)*5^(2/2) mod N = 510
> Y = (89737*68120)mod(89755) = 30410

1. Check that X mod N != Y mod N;
2. Compute U an V, where
U= GCD(X+Y,N) = GCD(30410+510,89755) = 3095,
V= GCD(X-Y,N) = GCD(30410-510,89755) = 145


Result: According to the algorithm description U and V are the components of N

But 3095 * 145 = 448775, and 448775/5 = 89755, which should be their product in the fist place.

The places I was checking to were wiki https://en.wikipedia.org/wiki/Dixon%27s_factorization_method also this Questions from Dixon Factorization Paper Answer 2 was a great explanation but it missed the part that solved equations. Also some couple of books on the topic, but they all dont provide a complete example of how to solve equations mod 2 for this particular application.

There are some other problems like solving for 10 or 200 or 202 doesnt work , but solving for 201,205 does work

So my bet is that step 9 is really broken.

Updating my question with one more. The algorithm gives some weird behaviour on 25 and 49. Looks like I should understand more clearly what's going on in my algorithm

• Where exactly does it say that UV=N? You can say that N | UV , but that's it. Also 11. should be $X mod N \neq \pm Y mod N$, shouldn't it? – Michael Stocker Oct 28 '15 at 13:11
• Well here is a quote from wiki:The resulting factorization is 84923 = gcd(20712 − 16800, 84923) × gcd(20712 + 16800, 84923) = 163 × 521. – Antiusninja Oct 28 '15 at 13:27
• So do you think that -+could matter ? – Antiusninja Oct 28 '15 at 13:28

When $GCD(X+Y,N)\neq 1 {or} N$ it gives you a proper factorization.
Step 11 has to read "Check that $X \mod N \neq \pm Y \mod N$". Take for example $2^2 \equiv 13^2 mod 15$. You get $GCD(13+2,15)= 15$ and $GCD(13-2,15)= 1$. Neither of which are of much help in finding a proper factor.