20050315, 15:43  #1 
Apr 2004
Copenhagen, Denmark
2^{2}×29 Posts 
Dixon's algorithm
I'm writing a small assignment on the continued fraction factorization method, and therefore want to give a detailed description of Dixon's algorithm.
I've stumbled upon something that I'm having trouble proving, maybe someone here can help? Let M be the integer to be factored with Dixon's algorithm. Let \psi(x,z) be the number of m\in N less than x such that all the prime factors of m is less than z. Let the largest prime in the factorbase be y. Take b \in [1,n] arbitrary and see if (b² mod n) factors completely over the factorbase. The probability that b factors into primes from the factorbase is clearly P=\psi(M,y)/M, since b is chosen arbitrarily, but that isn't so interesting. The interesting thing is the probability that (b² mod M) factors completely over the factorbase. How can I deduce that because b is chosen at random , then (B² mod M) is also randomly distributed in [1,M]?  Cheers, Jes 
20050315, 19:31  #2  
Feb 2005
2^{2}·3^{2}·7 Posts 
Quote:
Pr(b mod M=r1)  Pr(b mod M=r2) for any r1,r2 in [0,M1] does not exceed 1/n. So for large enough n it can be neglected. For uniformely random b in [0,n1] and any r in [0,M1], prove the following formula: Code:
Pr(b mod M=r) = ceil((nr)/M)/n Code:
 Pr(b mod M=r)  1/M  ≤ 1/n Last fiddled with by maxal on 20050315 at 19:37 

20050315, 21:02  #3 
Apr 2004
Copenhagen, Denmark
2^{2}×29 Posts 
I messed up.
I meant b \in [1,M] and (b² mod M), but for some reason the "M" looks very much like an "n" to the untrained eye Anyway, thanks for your help!  Cheers, Jes Last fiddled with by JHansen on 20050315 at 21:04 
20050315, 21:19  #4  
Feb 2005
2^{2}×3^{2}×7 Posts 
Quote:
Quote:
Last fiddled with by maxal on 20050315 at 21:20 

20050315, 21:29  #5 
Apr 2004
Copenhagen, Denmark
2^{2}×29 Posts 
I think I have not expressed myself properly.
My trouble is this: If b_i \in [0,M1] is chosen at random, why is it true that ( (b_i)^2 mod M) is randomly distributed in [0,M1], i.e. why does the squareing mod M "preserve the randomness", so to speak?  Cheers, Jes PS: A math forum with the possibility to typeset formulas in (La)TeX would be great! Last fiddled with by JHansen on 20050315 at 21:34 
20050315, 21:35  #6  
Feb 2005
2^{2}×3^{2}×7 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
new factorization algorithm  jasonp  Math  2  20120617 20:04 
TF algorithm(s)  davieddy  Miscellaneous Math  61  20110706 20:13 
Is there an algorithm which solves this?  Unregistered  Homework Help  0  20070809 17:40 
Maybe new sieving algorithm  nuggetprime  Riesel Prime Search  5  20070420 04:19 
Prime95's FFT Algorithm  Angular  Math  6  20020926 00:13 