prime factorization algorithms? - Page 5

MathBoy · 2011-01-25, 03:32

OK so the log method doesn't guarantee that all the numbers over a given
threshold factor completely. You test them individually to see if they do and either you discard the ones that don't or add the few new primes to the FB.

But then how is this method better then just going thru all V[r1+kp_i] and as you do divide by the highest power prime. Just like the Wikipedia example does except it doesn't divide thru by the highest power ( just uses power =1 ) .

If it did at the end, the 1 entries in the V would indicate the only numbers in V that could completely factored over FB.

And you could set it to count up to FB + 1 relations and stop so it doesn't go thru the whole thing, just goes until it finds enough.

Their are tons of different variations but they all seem to have the same runtime except considering the actual factoring algorithm used to factor the small V numbers.

Basically I think the wikipedia way is just as good as the log way? Correct me if I am wrong.

CRGreathouse · 2011-01-25, 03:46

Quote:

Originally Posted by MathBoy

Basically I think the wikipedia way is just as good as the log way? Correct me if I am wrong.

No, it's much slower.

bsquared · 2011-01-25, 04:53

Quote:

Originally Posted by MathBoy

Basically I think the wikipedia way is just as good as the log way? Correct me if I am wrong.

Good as in "more accurate", sure. Good as in "as fast", no way. To factor, say, a 75 digit number, a modern quadratic sieve would typically set up 100,000 or so vectors of length 524288. Each point in each one of these vectors represents a number to be trial divided. And each number is on the order of sqrt(n) in size (about 37 digits). Say you had the prime '3' in your factor base. What you propose would involve trial dividing '3' into every third position in every one of those vectors. That's on the order of 10 billion divisions. Divisions are slow to perform in the cpu: each might take 40 clock cycles. Just to check every position for divisibility by 3 might take 400e9 / 3e9 ~= 2 minutes. Additions, on the other hand, take 1-2 clocks (assuming every addition is a write to a cache memory location). I'd rather use additions.

Of course, modern QS implementations don't bother checking for divisibility by 3 at all. The key to speed is sloppiness. We approximate using logs. We don't use the smallest primes at all when sieving. We ignore prime powers. We only look closely at results that are "good enough". The entire exercise is to be able to find (by way of approximate sieving techniques) those locations which are probably good enough very quickly - only spend effort doing laborious divisions on vector locations which are likely to completely factor over the factor base.

Hope this helps.

xilman · 2011-01-25, 21:00

Quote:

Originally Posted by bsquared

... only spend effort doing laborious divisions on vector locations which are likely to completely factor over the factor base.

And not even then if you can avoid it. The keyword here is "resieving".

Paul

fivemack · 2011-01-25, 21:29

Can you give me a good reference for resieving? Is there more to it than simply running the sieve pass again and accumulating the sieve primes that hit specially-marked locations into some other data structure?

R.D. Silverman · 2011-01-25, 22:55

Quote:

Originally Posted by fivemack

Can you give me a good reference for resieving? Is there more to it than simply running the sieve pass again and accumulating the sieve primes that hit specially-marked locations into some other data structure?

No. You got it.

bsquared · 2011-01-25, 22:59

Quote:

Originally Posted by xilman

And not even then if you can avoid it. The keyword here is "resieving".

Paul

Good point, although that's maybe more important for NFS lattice sieving. Profiling my QS code says that the actual time spend doing divisions is ~ 5% of the total time.

I'd also be interested in a re-sieving reference, if you know of one. I've googled it before and haven't turned up anything substantial.

[edit]
nevermind. saw RDS post.

bsquared · 2011-01-25, 23:05

Quote:

Originally Posted by R.D. Silverman

No. You got it.

One part is still confusing me. If the division is never performed, how do we determine either the value of any residual large prime or the value of a residual small composite to split when using two large primes (or three...)?

R.D. Silverman · 2011-01-25, 23:20

Quote:

Originally Posted by bsquared

One part is still confusing me. If the division is never performed, how do we determine either the value of any residual large prime or the value of a residual small composite to split when using two large primes (or three...)?

The division is performed! It's just that the resieve tells you
exactly which primes will divide the norm. It isn't trial division.
You only divide by primes that are known to divide.

bsquared · 2011-01-25, 23:23

Quote:

Originally Posted by R.D. Silverman

The division is performed! It's just that the resieve tells you
exactly which primes will divide the norm. It isn't trial division.
You only divide by primes that are known to divide.

Ahh!!

Thanks - sorry for the mental block there.

- b.

MathBoy · 2011-01-26, 02:46

I am still unclear how these logs are faster.
Since for example let V[] be the set that we are going to sieve using the log method.

let N = the threshold log value for example lets use log(V[i]) > 5.7

using this we still have to go thru all the elements in V and for the elements > 5.7 they still have to be factored. So where is the time saver?

The only time saver I can see is the method used in factoring the elements in V. Maybe I don't use trial but ECM or something different to speed this up...
But I would still think this is a slow process.

once we have these FB+1 relations and their factorization then the rest of the algorithm just relys on matrix solving and gcd algorithm. Which I believe the matrix can be solved in O(n^2.3ish) and gcd(b1,b2) is O(log(max{#b1,#b2})) . So the only difference, in creating a better algorithm like QS , NFS ,...etc variants is to improve the data collection part. For the most part the sieving piece. Find a factor bases really cann't be improved that much since it is almost trivial to find one O(n) using Legendre symbol "provided we already know the primes in the set". And finding the x in x^2 mod p is also pretty fast just find a quadratic nonresidue a (50% changes randomly picking)
and compute (a + sqrt(a^2 - n^2 ) )^p+1/2

Side question these fastest/best known algorithms all use the same thought process look for relations x^2 = y^2 mod N.
Would their be any benefit in looking not at the case power = 2 but also in the case where power >= 3? Or maybe varying the power as a way of adding another edge to the algorithm. Just in the way MPQS varies over many different polynomials.

2011-01-25, 03:32	#45
MathBoy Jan 2011 3·5 Posts	OK so the log method doesn't guarantee that all the numbers over a given threshold factor completely. You test them individually to see if they do and either you discard the ones that don't or add the few new primes to the FB. But then how is this method better then just going thru all V[r1+kp_i] and as you do divide by the highest power prime. Just like the Wikipedia example does except it doesn't divide thru by the highest power ( just uses power =1 ) . If it did at the end, the 1 entries in the V would indicate the only numbers in V that could completely factored over FB. And you could set it to count up to FB + 1 relations and stop so it doesn't go thru the whole thing, just goes until it finds enough. Their are tons of different variations but they all seem to have the same runtime except considering the actual factoring algorithm used to factor the small V numbers. Basically I think the wikipedia way is just as good as the log way? Correct me if I am wrong. Last fiddled with by MathBoy on 2011-01-25 at 03:51

2011-01-26, 02:46	#55
MathBoy Jan 2011 3×5 Posts	I am still unclear how these logs are faster. Since for example let V[] be the set that we are going to sieve using the log method. let N = the threshold log value for example lets use log(V[i]) > 5.7 using this we still have to go thru all the elements in V and for the elements > 5.7 they still have to be factored. So where is the time saver? The only time saver I can see is the method used in factoring the elements in V. Maybe I don't use trial but ECM or something different to speed this up... But I would still think this is a slow process. once we have these FB+1 relations and their factorization then the rest of the algorithm just relys on matrix solving and gcd algorithm. Which I believe the matrix can be solved in O(n^2.3ish) and gcd(b1,b2) is O(log(max{#b1,#b2})) . So the only difference, in creating a better algorithm like QS , NFS ,...etc variants is to improve the data collection part. For the most part the sieving piece. Find a factor bases really cann't be improved that much since it is almost trivial to find one O(n) using Legendre symbol "provided we already know the primes in the set". And finding the x in x^2 mod p is also pretty fast just find a quadratic nonresidue a (50% changes randomly picking) and compute (a + sqrt(a^2 - n^2 ) )^p+1/2 Side question these fastest/best known algorithms all use the same thought process look for relations x^2 = y^2 mod N. Would their be any benefit in looking not at the case power = 2 but also in the case where power >= 3? Or maybe varying the power as a way of adding another edge to the algorithm. Just in the way MPQS varies over many different polynomials. Last fiddled with by MathBoy on 2011-01-26 at 02:57

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Semi-prime factorization conjecture	Alberico Lepore	Alberico Lepore	7	2018-02-16 08:27
Prime factorization for RSA210	Kalestiel	Factoring	6	2012-11-04 17:58
Mersenne(prime exponents) factorization	science_man_88	Miscellaneous Math	3	2010-10-13 14:32
Distributed Factoring and prime testing algorithms	bunbun	Software	6	2006-03-27 17:14
"Trivial" factorization algorithms	Fusion_power	Math	13	2004-12-28 20:46

2011-01-25, 21:29	#49
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 3·2,141 Posts	Can you give me a good reference for resieving? Is there more to it than simply running the sieve pass again and accumulating the sieve primes that hit specially-marked locations into some other data structure?