Verifying factors...

Xyzzy · 2002-08-27, 09:05

I have an exponent credited to me as having a factor found...

Exponent: 9835211
Factor: 36293798558667431

Now for some reason this exponent is not listed in the big database or whatever... At least I couldn't find it... And it is listed in my database without a date...

Anyways, Digital Concepts and I worked on making a formula for testing this exponent's factor... The program to run the formula is here:

http://www.uic.nnov.ru/~zny/upa/upa.html

Ordinarily, I would use "bc" but my Sun is not hooked up right now...

Here is the formula DC made:

[code:1](((((2^9835211)-1) div 36293798558667431)*36293798558667431)+1)/(2^9835210);[/code:1]

I use RPN so this thing is awfully complicated looking to me... DC mentioned he had real trouble with the last part for some reason...

Now, is there an easier way to verify factors? This looks like it might take a day or so to run... Even "2^9835211" will take a long time... I'm running it on a 2GHz P4... Surprisingly, it uses very little memory... I have 1GB in the box but it uses only 4K or so, at least right now...

I imagine that all of the factors found by GIMPS are verified, aren't they?

Thanks!

binarydigits · 2002-08-27, 11:42

I understand that the Primenet server "doublechecks" the factor when the result is reported to it, which only takes a fraction of a second. I assume it does it the same way as trial factoring in the client, but it only needs to try the one candidate rather than a range of hundreds of thousands.

alpertron · 2002-08-27, 16:01

You have to find (2^9835211)-1 mod 36293798558667431. If it is zero, the Mersenne number is multiple of the factor found by your computer.

Notice that you do not have to compute (2^9835211) that has millions of digits because it would take a lot of time.

Instead, you should perform all calculations (mainly multiplications) mod 36293798558667431.

That is, as a first step, you could do the the following:

Q <- 1
do 9835211 times: Q <- Q * 2 mod 36293798558667431
Q <- Q - 1

In this case you should get zero, so you found a factor.

Using this method you reduce the time from years to less than a day.

But you can optimize further the procedure using binary exponentiation (see http://primes.utm.edu/glossary/page.php/BinaryExponentiation.html for details). Using this method you reduce the 9835211 multiplications to less than 50, so the check can be done in less than a second.

Best regards,

Dario Alpern

garo · 2002-08-27, 22:09

Xyzzy,
This exponent is listed in George's factos.zip database - I hust checked and it's there.

Xyzzy · 2002-08-28, 00:42

Thanks to all for the help... It looks like I have a lot to read up on... :)

Garo: Where can I get this list?

garo · 2002-08-28, 01:10

ftp://mersenne.org/gimps/factors.zip

You also need a special proggie decomp to decompress it. Find link to that proggie on http://mersenne.org/status.htm

Digital Concepts · 2002-08-28, 20:40

Any idea why that exponent isn't on the Individual Account Report or the PrimeNet Cleared Exponent List?

garo · 2002-08-28, 23:33

Because it was removed in the last database synchronization. DB synchronizations remove completed tests from Primenet and put them in George's master DB.

Digital Concepts · 2002-08-29, 06:04

Looking at the Individul Account Report - I would of guessed the last synch was for exponents < 9M. :?

akruppa · 2002-08-30, 17:45

Quote:

Originally Posted by alpertron

You have to find (2^9835211)-1 mod 36293798558667431. If it is zero, the Mersenne number is multiple of the factor found by your computer.

Notice that you do not have to compute (2^9835211) that has millions of digits because it would take a lot of time.

Instead, you should perform all calculations (mainly multiplications) mod 36293798558667431.

One very convenient way to do it is to use the GMP calulator on the GMP home page. If you enter, i.e.

(2^9835211-1) mod 36293798558667431

it detects that modular arithmetic is possible and uses that instead of first computing 2^983521-1 and then reducing the result mod 36293798558667431.

The output given is

Quote:

The result of executing (2^9835211-1) mod 36293798558667431 is:

computation took 0.01 ms
output conversion took 0.00 ms
0

showing that 2^9835211 - 1 == 0 (mod 3629379855866743) and thus that 3629379855866743 divides M(9835211).

Alex

Maybeso · 2002-09-09, 21:57

The GMP calculator is impressive!

Another tool that I've found useful, Joe Crump wrote an Excel add-in that uses strings for 250 digits calculations. (click on Excel add-in on th left.)

He's included many useful Number Theory functions.

A note of caution: I wrote a looped macro to trial-factor mersenne numbers and it started leaking memory. So don't loop unless you incorporate a check that waits until all zzmath fields are updated.

But it's great for building tables of large factors, 'k' values, relative factor sizes, number of factors, etc. Then you can make some incredible (and visually informative) charts.

2002-08-27, 09:05	#1
Xyzzy "Mike" Aug 2002 201F₁₆ Posts	Verifying factors... I have an exponent credited to me as having a factor found... Exponent: 9835211 Factor: 36293798558667431 Now for some reason this exponent is not listed in the big database or whatever... At least I couldn't find it... And it is listed in my database without a date... Anyways, Digital Concepts and I worked on making a formula for testing this exponent's factor... The program to run the formula is here: http://www.uic.nnov.ru/~zny/upa/upa.html Ordinarily, I would use "bc" but my Sun is not hooked up right now... Here is the formula DC made: [code:1](((((2^9835211)-1) div 36293798558667431)*36293798558667431)+1)/(2^9835210);[/code:1] I use RPN so this thing is awfully complicated looking to me... DC mentioned he had real trouble with the last part for some reason... Now, is there an easier way to verify factors? This looks like it might take a day or so to run... Even "2^9835211" will take a long time... I'm running it on a 2GHz P4... Surprisingly, it uses very little memory... I have 1GB in the box but it uses only 4K or so, at least right now... I imagine that all of the factors found by GIMPS are verified, aren't they? Thanks!

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
'Verifying' a Mersenne prime vs. 'proving' it	Rodrigo	Information & Answers	28	2011-02-14 23:43
Missing factors at the 'Known Factors' page	MatWur-S530113	PrimeNet	11	2009-01-21 19:08
I need some factors	MatWur-S530113	Math	21	2007-05-12 19:36
The factors of 11,199-	Jeff Gilchrist	NFSNET Discussion	2	2004-09-27 23:40
Introducing GIMPS, Now Verifying M10,000,000+!	E_tron	Lounge	7	2003-09-16 21:30

2002-08-27, 11:42	#2
binarydigits Aug 2002 64₈ Posts	I understand that the Primenet server "doublechecks" the factor when the result is reported to it, which only takes a fraction of a second. I assume it does it the same way as trial factoring in the client, but it only needs to try the one candidate rather than a range of hundreds of thousands.

2002-08-27, 16:01	#3
alpertron Aug 2002 Buenos Aires, Argentina 2×683 Posts	You have to find (2^9835211)-1 mod 36293798558667431. If it is zero, the Mersenne number is multiple of the factor found by your computer. Notice that you do not have to compute (2^9835211) that has millions of digits because it would take a lot of time. Instead, you should perform all calculations (mainly multiplications) mod 36293798558667431. That is, as a first step, you could do the the following: Q <- 1 do 9835211 times: Q <- Q * 2 mod 36293798558667431 Q <- Q - 1 In this case you should get zero, so you found a factor. Using this method you reduce the time from years to less than a day. But you can optimize further the procedure using binary exponentiation (see http://primes.utm.edu/glossary/page.php/BinaryExponentiation.html for details). Using this method you reduce the 9835211 multiplications to less than 50, so the check can be done in less than a second. Best regards, Dario Alpern

2002-08-27, 22:09	#4
garo Aug 2002 Termonfeckin, IE 2²×691 Posts	Xyzzy, This exponent is listed in George's factos.zip database - I hust checked and it's there.

2002-08-28, 00:42	#5
Xyzzy "Mike" Aug 2002 201F₁₆ Posts	Thanks to all for the help... It looks like I have a lot to read up on... :) Garo: Where can I get this list?

2002-08-28, 01:10	#6
garo Aug 2002 Termonfeckin, IE 2²·691 Posts	ftp://mersenne.org/gimps/factors.zip You also need a special proggie decomp to decompress it. Find link to that proggie on http://mersenne.org/status.htm

2002-08-28, 20:40	#7
Digital Concepts Aug 2002 36₁₆ Posts	Any idea why that exponent isn't on the Individual Account Report or the PrimeNet Cleared Exponent List?

2002-08-28, 23:33	#8
garo Aug 2002 Termonfeckin, IE 2764₁₀ Posts	Because it was removed in the last database synchronization. DB synchronizations remove completed tests from Primenet and put them in George's master DB.

2002-08-29, 06:04	#9
Digital Concepts Aug 2002 2·3³ Posts	Looking at the Individul Account Report - I would of guessed the last synch was for exponents < 9M. :?

2002-09-09, 21:57	#11
Maybeso Aug 2002 Portland, OR USA 112₁₆ Posts	The GMP calculator is impressive! Another tool that I've found useful, Joe Crump wrote an Excel add-in that uses strings for 250 digits calculations. (click on Excel add-in on th left.) He's included many useful Number Theory functions. A note of caution: I wrote a looped macro to trial-factor mersenne numbers and it started leaking memory. So don't loop unless you incorporate a check that waits until all zzmath fields are updated. But it's great for building tables of large factors, 'k' values, relative factor sizes, number of factors, etc. Then you can make some incredible (and visually informative) charts.