20061229, 16:17  #45  
Tribal Bullet
Oct 2004
2·3·19·31 Posts 
Quote:
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 

20061229, 19:04  #46  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2^{2}·3·883 Posts 
Quote:
Paul 

20070107, 20:51  #47 
Nov 2005
101 Posts 
@ 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%. 
20070108, 14:12  #48 
Nov 2005
101 Posts 
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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Java Quadratic Sieve  Ilya Gazman  Factoring  3  20160222 11:32 
Quadratic Sieve by Hand  Sam Kennedy  Factoring  20  20130109 16:50 
Finding B in Quadratic Sieve  paul0  Factoring  3  20110922 17:12 
Possible improvement of quadratic sieve  Random Poster  Factoring  4  20100212 03:09 
Quadratic Sieve in wikipedia.de  ThiloHarich  Factoring  5  20060714 09:51 