mersenneforum.org Dixon's algorithm
 Register FAQ Search Today's Posts Mark Forums Read

 2005-03-15, 15:43 #1 JHansen     Apr 2004 Copenhagen, Denmark 22×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
2005-03-15, 19:31   #2
maxal

Feb 2005

22·32·7 Posts

Quote:
 Originally Posted by JHansen How can I deduce that because b is chosen at random , then (B² mod M) is also randomly distributed in [1,M]?
Strictly speaking, that's true if and only if n is a multiple of M. But for general n the difference of the probabilities
Pr(b mod M=r1) - Pr(b mod M=r2)
for any r1,r2 in [0,M-1] does not exceed 1/n. So for large enough n it can be neglected.

For uniformely random b in [0,n-1] and any r in [0,M-1], prove the following formula:
Code:
Pr(b mod M=r) = ceil((n-r)/M)/n
and then the inequality
Code:
| Pr(b mod M=r) - 1/M | ≤ 1/n

Last fiddled with by maxal on 2005-03-15 at 19:37

 2005-03-15, 21:02 #3 JHansen     Apr 2004 Copenhagen, Denmark 22×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 2005-03-15 at 21:04
2005-03-15, 21:19   #4
maxal

Feb 2005

22×32×7 Posts

Quote:
 Originally Posted by JHansen 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
If b \in [1,M] then (b mod M)=b with the only exception of b=M for which (M mod M)=0. And the statement
Quote:
 Originally Posted by JHansen because b is chosen at random , then (B² mod M) is also randomly distributed in [1,M]
becomes trivial (of course, it should be [0,M-1] rather than [1,M]).

Last fiddled with by maxal on 2005-03-15 at 21:20

 2005-03-15, 21:29 #5 JHansen     Apr 2004 Copenhagen, Denmark 22×29 Posts I think I have not expressed myself properly. My trouble is this: If b_i \in [0,M-1] is chosen at random, why is it true that ( (b_i)^2 mod M) is randomly distributed in [0,M-1], 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 2005-03-15 at 21:34
2005-03-15, 21:35   #6
maxal

Feb 2005

22×32×7 Posts

Quote:
 Originally Posted by JHansen If b_i \in [0,M-1] is chosen at random, why is it true that (b^2 mod M) is randomly distributed in [0,M-1]?
That's not true since not every number in [0,M-1] is a square mod M. Say, for prime M only (M+1)/2 numbers in [0,M-1] are squares mod M and the other (M-1)/2 are not.

 Similar Threads Thread Thread Starter Forum Replies Last Post jasonp Math 2 2012-06-17 20:04 davieddy Miscellaneous Math 61 2011-07-06 20:13 Unregistered Homework Help 0 2007-08-09 17:40 nuggetprime Riesel Prime Search 5 2007-04-20 04:19 Angular Math 6 2002-09-26 00:13

All times are UTC. The time now is 12:33.

Tue Nov 30 12:33:11 UTC 2021 up 130 days, 7:02, 0 users, load averages: 1.25, 1.23, 1.11