mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

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

2×3×5×193 Posts
Default

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

3·1,163 Posts
Default

Quote:
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
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

3·139 Posts
Default

Quote:
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
Reply

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 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.