Go Back > Factoring Projects > Factoring

Thread Tools
Old 2020-06-10, 04:37   #12
retina's Avatar
"The unspeakable one"
Jun 2006
My evil lair

33×233 Posts

python is fine with negatives.
python3 -c "print(-1064%109)"
retina is online now   Reply With Quote
Old 2020-06-10, 11:36   #13
Tribal Bullet
jasonp's Avatar
Oct 2004

67278 Posts

Originally Posted by Sam Kennedy View Post
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.
jasonp is offline   Reply With Quote
Old 2020-06-10, 16:14   #14
Till's Avatar
"Tilman Neumann"
Jan 2016

11×43 Posts

Originally Posted by Sam Kennedy View Post
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)
Till is offline   Reply With Quote

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Sublinear complexity of trial division? yih117 Math 5 2018-02-02 02:49
Mersenne trial division implementation mathPuzzles Math 8 2017-04-21 07:21
trial division over a factor base Peter Hackman Factoring 7 2009-10-26 18:27
P95 trial division strategy SPWorley Math 8 2009-08-24 23:26
Need GMP trial-division timings ewmayer Factoring 7 2008-12-11 22:12

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

Thu Oct 28 06:26:39 UTC 2021 up 97 days, 55 mins, 0 users, load averages: 1.63, 1.85, 1.82

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.