Timeline for Quadratic Sieve Bottleneck, Multiple Polynomials an option?
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 19, 2012 at 13:28 | comment | added | fgrieu♦ | Congratulations! Now you can move on to MPQS, SIQS, PPMPQS.. | |
| Nov 17, 2012 at 22:34 | comment | added | Sam Kennedy | It works now! What took 4 hours previously now takes less than 10 minutes :) | |
| Nov 14, 2012 at 11:38 | comment | added | fgrieu♦ | Try Carl Pomerance's Smooth numbers and the quadratic sieve | |
| Nov 13, 2012 at 13:00 | history | tweeted | twitter.com/#!/StackCrypto/status/268337600740327425 | ||
| Nov 13, 2012 at 7:09 | comment | added | fgrieu♦ | There's lot of good in this, esp. step 4 which should be where ultimately a great deal of time is spent (notice when you have an $X$ with $Y$ divisible by $p$, the $Y'$ corresponding to $X'=X+k\cdot p$ are). But a comment is not the proper place to describe QS (Fermat notoriously had the same problem with a margin :-) and I suggest you find a reference; time is missing to give you one. | |
| Nov 12, 2012 at 22:55 | comment | added | Sam Kennedy | Okay let's see if I have understood this correctly. n = number to be factored, pmax = highest prime in factor base, M = number of X/Y pairs collected, T = some fudge factor, p = a prime in the factor base 1) Calculate TARGET = (number of bits in n / 2) + number of bits in M 2) CLOSE = TARGET - T * number of bits in pmax 3) Find the first value of Y that is divisible by p, add the number of bits in p to a zero initialised array 4) Repeat for every p'th element 5) If a value in the array is within CLOSE digits to TARGET, then the corresponding Y value is probably smooth. | |
| Nov 12, 2012 at 19:46 | comment | added | fgrieu♦ | You need a raw approximation of the log, times some scaling factor. Try the number of bits. And of course compute that outside the inner loop. | |
| Nov 12, 2012 at 19:30 | comment | added | Sam Kennedy | I was trying to avoid using the log function since GMP doesn't have one. I don't understand why, it's like having a formula one car which can only make left turns. If there's a way around this, I will get rid of the trial division. I'll see how hard it would be to code my own log function. | |
| Nov 12, 2012 at 19:09 | comment | added | fgrieu♦ | This is not a proper implementation of the Quadratic Sieve, and multiple polynomials is not the first thing you want to add. The standard technique for QS uses an array (moreless indexed by your X) where the approximate log of the primes in the factor base is added as appropriate, and thus avoids trial division entirely. The savings are enormous. I think we have a resident expert, I hope he'll be able to give pointers, or/and an answer. | |
| Nov 12, 2012 at 16:36 | history | asked | Sam Kennedy | CC BY-SA 3.0 |