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? :shock:

Thanks!

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.

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

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

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

Garo: Where can I get this list?

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

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

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

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

[quote="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.

[/quote]

One very convenient way to do it is to use the [url=http://www.swox.com/gmp/#TRY]GMP calulator[/url] 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
[/quote]
showing that 2^9835211 - 1 == 0 (mod 3629379855866743) and thus that 3629379855866743 divides M(9835211).

Alex

The GMP calculator is impressive!

Another tool that I've found useful, Joe Crump wrote an [url=http://www.spacefire.com/numbertheory/] Excel add-in [/url] 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.