1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Michael Stocker Oct 28 '15 at 13:11
  • $\begingroup$ Well here is a quote from wiki:The resulting factorization is 84923 = gcd(20712 − 16800, 84923) × gcd(20712 + 16800, 84923) = 163 × 521. $\endgroup$ – Antiusninja Oct 28 '15 at 13:27
  • $\begingroup$ So do you think that -+could matter ? $\endgroup$ – Antiusninja Oct 28 '15 at 13:28
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you. That has helped. I did some small calc in the end to complete the task. I'm checking if abs(u*v) > N then I introduce the variable int factor = (UхV)/N and then U = U/factor $\endgroup$ – Antiusninja Oct 28 '15 at 18:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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