mersenneforum.org MPQS Trial Division Optimisation
 Register FAQ Search Today's Posts Mark Forums Read

 2020-06-10, 04:37 #12 retina 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
2020-06-10, 11:36   #13
jasonp
Tribal Bullet

Oct 2004

3·1,163 Posts

Quote:
 Originally Posted by Sam Kennedy jasonp, is that how msieve works? I was absolutely blown away by how fast it is! I know you've put a lot of effort into optimising it and it's very impressive. My MPQS code can factor a 60 digit semiprime in a couple of minutes, but yours does it in a couple of seconds, so now my goal is to figure out how to optimise my implementation as much as possible. How much faster is SIQS than MPQS? (I know it will be implementation dependent, I read somewhere it's about a factor of 2, does that sound about right?) I would be very interested in discussing optimisations, would it be better for me to start a new thread on that subject?
That is how Msieve works. We have many experienced programmers here and many of them have also implemented some version of QS. Start a thread asking questions if you like, but also check the archives for existing threads that have tips and tricks.

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.

2020-06-10, 16:14   #14
Till

"Tilman Neumann"
Jan 2016
Germany

3·139 Posts

Quote:
 Originally Posted by Sam Kennedy I feel like coding in C++ is like giving Manuel from Fawlty Towers instructions: you can never be 100% certain what's going to happen next. Java definitely has its benefits!

I did an experimental port of my Java PSIQS to C++ some time ago. It is working, and out-of-the-box 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 1-2 seconds, too; RSA-100 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)

 Similar Threads Thread Thread Starter Forum Replies Last Post yih117 Math 5 2018-02-02 02:49 mathPuzzles Math 8 2017-04-21 07:21 Peter Hackman Factoring 7 2009-10-26 18:27 SPWorley Math 8 2009-08-24 23:26 ewmayer Factoring 7 2008-12-11 22:12

All times are UTC. The time now is 02:59.

Fri Oct 23 02:59:55 UTC 2020 up 43 days, 10 mins, 0 users, load averages: 2.07, 1.65, 1.56