40 reputation
5
bio website
location
age
visits member for 1 year, 9 months
seen Feb 5 '13 at 13:14

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