Somethings wrong with my Dickson factorization algorithm implementation

Question

Please check:

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

8. 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

9. 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

10. 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

11. Check that X mod N != Y mod N;
12. 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

Answer 1

I'll make an answer of it, since it would be a bit cramped as a comment.

On the wiki page it does say that "The resulting factorization is 84923 = gcd(20712 − 16800, 84923) × gcd(20712 + 16800, 84923) = 163 × 521." I guess that can be misleading. Yes, in their case you are left directly with a factorization. But, as you have shown with your calculation, GCD(X+Y,N)*GCD(X-Y,N) doesn't have to be N, it can also be a multiple of N.

But doesn't change much. GCD(X+Y,N) and GCD(X-Y,N) are factors of N. And you get a factorization N = (N/GCD(X+Y,N)) * GCD(X+Y,N) (also = (N/GCD(X-Y,N)) * GCD(X-Y,N)) .

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.