2008-09-19, 00:43 | #1 |
Sep 2008
Krefeld, Germany
11100110_{2} Posts |
Mersenne-version of the quadratic sieve
Hi everyone,
i tried to modify the quadratic sieve for mersenne primes, can anyone please comment on this one? All factors of mersenne numbers have the form (k*x+1), for x being the exponent. So: 2^x-1 = ((k+t)*x+1)((k-t)*x+1) 2^x-1 = k^2*x^2 - t^2*x^2 + 2kx + 1 k^2*x + 2kx - (2^x-2)/x = t^2*x now we need a k to make the left side positive and start with k=(sqrt(2^x-1)-1)/x and go up from that until the left side is divisible by x (any way to improve that?) When found, we increase k by x in the next steps and get a divisable one every step. Divise all them by x and continue: Factorize all numbers found that way and cut out double prime factors, multiply all remaining factors and put that number in a big list. Check every new number coming in against all the others on the list in that way: is new*old/ggt(new,old)^2 < new? Then add new to the list. x*y/ggt(x,y)^2 wipes out all common prime factors. If we finally get a zero we have a factor. Will this algorithm work fast? Will it even work? Thanks for reading |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Non-sieving version of Quadratic Sieve | mickfrancis | Factoring | 5 | 2016-03-31 06:21 |
Quadratic Sieve by Hand | Sam Kennedy | Factoring | 20 | 2013-01-09 16:50 |
Possible improvement of quadratic sieve | Random Poster | Factoring | 4 | 2010-02-12 03:09 |
Factoring in the Quadratic Sieve | ThiloHarich | Factoring | 47 | 2007-01-08 14:12 |
Quadratic Sieve in wikipedia.de | ThiloHarich | Factoring | 5 | 2006-07-14 09:51 |