20200610, 04:37  #12 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2×3×5×193 Posts 
python is fine with negatives.
Code:
python3 c "print(1064%109)" 26 
20200610, 11:36  #13  
Tribal Bullet
Oct 2004
3·1,163 Posts 
Quote:
Contini's original thesis estimated that SIQS is asymptotically 2x faster than MPQS, but the factor speedup to expect is not entirely clear. Msieve got 6x faster transitioning from MPQS to SIQS but that was because a lot of the MPQS code sucked and was improved in the process. Variants of QS are also extremely sensitive to parameter tuning, you can easily achieve a 2x speedup just by playing with factor base sizes, sieve sizes and thresholds where you switch to different strategies. Beyond 60 digits was also the point where not using block Lanczos for the linear algebra starts to really hurt. 

20200610, 16:14  #14  
"Tilman Neumann"
Jan 2016
Germany
3·139 Posts 
Quote:
I did an experimental port of my Java PSIQS to C++ some time ago. It is working, and outofthebox a bit faster than in Java (10 or 20%, some parts faster, some slower, but the sieve is faster and that's what matters most). But resolving all the memory leaks is really hard work and I stopped working on it. The mix of C++ "stack" memory management (said to be preferrable, but doesn't work always) and the good old C memory management is confusing me. But probably that's my problem; I switched from C to Java kind of 20 years ago... Nonetheless, if somebody is interested I could publish the code on github. It factors a 60 digit semiprime in a question of 12 seconds, too; RSA100 has been done in 17 min on a AMD 3950. The code is probably much smaller than the QS code of msieve. (754.405 Bytes to be exact) 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Sublinear complexity of trial division?  yih117  Math  5  20180202 02:49 
Mersenne trial division implementation  mathPuzzles  Math  8  20170421 07:21 
trial division over a factor base  Peter Hackman  Factoring  7  20091026 18:27 
P95 trial division strategy  SPWorley  Math  8  20090824 23:26 
Need GMP trialdivision timings  ewmayer  Factoring  7  20081211 22:12 