mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2006-12-29, 16:17   #45
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·3·19·31 Posts
Default

Quote:
Originally Posted by ThiloHarich View Post
The question is: "Is there a clever way to find the small divisors?"
Is there a way to find them without checking every of the pseudo smooth values with every prime.
Can we create an efficient function which decides if the prime p divides one (or more precisely which of the) pseudo smooth q (x)?
If you're talking about many small primes, the answer is likely no. If there are only a few small primes, a standard trick is to compute the gcd of the leftover sieve value with the product of the small primes. You can organize the small primes into 32-bit products and perform a succession of 1-word gcd computations, and if the sieve value has only one of the factors in a word then you'll find it. I'm not sure how much this would buy you, since at most it would reduce the number of actual division operations by a linear factor but a gcd is more expensive than a division unless implemented very carefully.

Is division by the small primes such a bottleneck for you? There are 30 of them, and thousands of larger factor base primes that need testing.

jasonp
jasonp is offline   Reply With Quote
Old 2006-12-29, 19:04   #46
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

22·3·883 Posts
Default

Quote:
Originally Posted by jasonp View Post
If you're talking about many small primes, the answer is likely no. If there are only a few small primes, a standard trick is to compute the gcd of the leftover sieve value with the product of the small primes. You can organize the small primes into 32-bit products and perform a succession of 1-word gcd computations, and if the sieve value has only one of the factors in a word then you'll find it. I'm not sure how much this would buy you, since at most it would reduce the number of actual division operations by a linear factor but a gcd is more expensive than a division unless implemented very carefully.

Is division by the small primes such a bottleneck for you? There are 30 of them, and thousands of larger factor base primes that need testing.

jasonp
I suggest both of you read a paper by Dan Bernstein about asymptotically fast division by small primes. That should be enough information for you to be able to find it and the search will be educational.


Paul
xilman is offline   Reply With Quote
Old 2007-01-07, 20:51   #47
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

101 Posts
Default

@ xilman Thanks for the Link. I'am going to read about it.

@ akruppa I'am testing with the exponents of the lower primes.

I first check if q(x) is divideble by p via the mod argument. If so, I divide q(x) by p as long as possible.
Since the division does not appears very often, this cheap.

@ jasonp Since sieving and factoring dominates the running time improvements will be appreciated. But my improvements were less then 30%.
ThiloHarich is offline   Reply With Quote
Old 2007-01-08, 14:12   #48
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

101 Posts
Default

The Ideas in the paper http://cr.yp.to/papers/sf.pdf should increase sieving and/or factoring.

Has anybody tried the Bernstein algorithm?

In java sieving is clearly the bottleneck (due to the slow array operations). Changing the polynomial is cheap. So this might be a good idea for java.
ThiloHarich is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Java Quadratic Sieve Ilya Gazman Factoring 3 2016-02-22 11:32
Quadratic Sieve by Hand Sam Kennedy Factoring 20 2013-01-09 16:50
Finding B in Quadratic Sieve paul0 Factoring 3 2011-09-22 17:12
Possible improvement of quadratic sieve Random Poster Factoring 4 2010-02-12 03:09
Quadratic Sieve in wikipedia.de ThiloHarich Factoring 5 2006-07-14 09:51

All times are UTC. The time now is 06:37.

Mon Mar 8 06:37:06 UTC 2021 up 95 days, 2:48, 0 users, load averages: 2.41, 2.20, 2.19

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.