mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2008-09-19, 00:43   #1
Syd
 
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.

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

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

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.