Go Back > Great Internet Mersenne Prime Search > Math

Thread Tools
Old 2008-09-19, 00:43   #1
Syd's Avatar
Sep 2008
Krefeld, Germany

2×5×23 Posts
Default 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.

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


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
Syd is offline   Reply With Quote

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 ThiloHarich Factoring 5 2006-07-14 09:51

All times are UTC. The time now is 19:52.

Thu Apr 22 19:52:40 UTC 2021 up 14 days, 14:33, 0 users, load averages: 1.90, 1.65, 1.75

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