mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-03-15, 15:43   #1
JHansen
 
JHansen's Avatar
 
Apr 2004
Copenhagen, Denmark

22×29 Posts
Question 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
JHansen is offline   Reply With Quote
Old 2005-03-15, 19:31   #2
maxal
 
maxal's Avatar
 
Feb 2005

22·32·7 Posts
Default

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
maxal is offline   Reply With Quote
Old 2005-03-15, 21:02   #3
JHansen
 
JHansen's Avatar
 
Apr 2004
Copenhagen, Denmark

22×29 Posts
Default

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
JHansen is offline   Reply With Quote
Old 2005-03-15, 21:19   #4
maxal
 
maxal's Avatar
 
Feb 2005

22×32×7 Posts
Default

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
maxal is offline   Reply With Quote
Old 2005-03-15, 21:29   #5
JHansen
 
JHansen's Avatar
 
Apr 2004
Copenhagen, Denmark

22×29 Posts
Default

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
JHansen is offline   Reply With Quote
Old 2005-03-15, 21:35   #6
maxal
 
maxal's Avatar
 
Feb 2005

22×32×7 Posts
Default

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.
maxal is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
new factorization algorithm jasonp Math 2 2012-06-17 20:04
TF algorithm(s) davieddy Miscellaneous Math 61 2011-07-06 20:13
Is there an algorithm which solves this? Unregistered Homework Help 0 2007-08-09 17:40
Maybe new sieving algorithm nuggetprime Riesel Prime Search 5 2007-04-20 04:19
Prime95's FFT Algorithm 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.