network profile
| bio | website | |
|---|---|---|
| location | ||
| age | ||
| visits | member for | 7 months |
| seen | Feb 5 at 13:14 | |
| stats | profile views | 2 |
|
Dec 18 |
awarded | Editor |
|
Dec 18 |
revised |
Generating Polynomials for the MPQS Found an answer to one of my questions |
|
Dec 18 |
asked | Generating Polynomials for the MPQS |
|
Nov 17 |
comment |
Quadratic Sieve Bottleneck, Multiple Polynomials an option? It works now! What took 4 hours previously now takes less than 10 minutes :) |
|
Nov 12 |
comment |
Quadratic Sieve Bottleneck, Multiple Polynomials an option? 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 |
comment |
Quadratic Sieve Bottleneck, Multiple Polynomials an option? 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 |
asked | Quadratic Sieve Bottleneck, Multiple Polynomials an option? |
|
Nov 11 |
accepted | ECM Implementation is really slow |
|
Nov 3 |
asked | ECM Implementation is really slow |
|
Oct 31 |
awarded | Supporter |
|
Oct 31 |
accepted | Optimising Pollard's Rho algorithm for large semi-primes |
|
Oct 30 |
comment |
Optimising Pollard's Rho algorithm for large semi-primes A few more questions, do x and y always have to start at 2? Does the function always have to be in the form of x^2 + c? Can c be a negative value? Also, the number of iterations is less than the square root of p, I'm assuming that's a good thing and I have it implemented properly? |
|
Oct 29 |
comment |
Optimising Pollard's Rho algorithm for large semi-primes I added the d == n after the algorithm kept outputting 15 as a factor of 15. I commented out the "failed" section of code for factoring 170141183460469237316439072031450875157 because of the same reason you mentioned, it factored it in 1 hour and 45 minutes, is that considered slow for this algorithm, or does it sound about right? |
|
Oct 29 |
asked | Optimising Pollard's Rho algorithm for large semi-primes |
|
Oct 28 |
comment |
Is there an algorithm for factoring N, which is just as simple as this one, but faster? I quickly wrote a program using Pollard's Rho algorithm, it's much faster than than the original (factored 31226716938897156373 in 0.055 seconds). I have some questions about Pollard's Rho algorithm now, should I ask here or start a new question with the relevant topic? |
|
Oct 28 |
comment |
Is there an algorithm for factoring N, which is just as simple as this one, but faster? Are either of these better alternatives? coolissues.com/mathematics/Goldbach/goldbach.htm mirlabs.info/cddump/data/4437a108.pdf |
|
Oct 28 |
awarded | Scholar |
|
Oct 28 |
accepted | Is there an algorithm for factoring N, which is just as simple as this one, but faster? |
|
Oct 28 |
awarded | Student |
|
Oct 28 |
comment |
Is there an algorithm for factoring N, which is just as simple as this one, but faster? I've looked into the quadratic sieve, but I'm not a mathematician and find it hard to understand. It looks very promising if I could get it to work though. |
