- Hi All,

The new LLR 3.7.0 Version is now available on the GIMPS directory!

It contains as a new important feature an efficient primality proving

test for the Gaussian-Mersenne norms.

Mike Oakes originated this search in the early 1970, and discovered

most of the above-titanic GM primes presently known (nevertheless, the

actual record, GM(991961) , has been discovered by Boris Iskra in

November 2005).

These numbers may be proven prime by the Proth theorem test, but the k

multiplier value beeing an exponential function of p, it would

require using the gwnums in generic mode...

Following a suggestion by Harsh Aggarwal, I implemented, in the new

version LLR3.7.0, a much more efficient method :

The starting point is the Aurifeuillian factorization of M(p) = 4^p+1 :

M(p) = 4^p+1 = (2^p + 2^((p+1)/2) + 1)(2^p - 2^((p+1)/2) + 1)

One of these two factors is the norm N(p) of GM(p) = (1±i)^p - 1

Now, the idea is to run the Proth algorithm, but doing the squarings

modulo M(p), and then doing the modulo N reduction only on the final

result. Then, the performances for a given p may be approximatively

the same as for a Lucas-Lehmer test with exponent 2*p.

In order to make this prime search really efficient, it is however

necessary that the prime exponent candidates would be sieved enough by

prefactoring, so I adapted the George Woltman's "factor32.asm" for

4^p+1 factoring, and this new code is included in LLR to eliminate the

candidates having a non trivial factor, before doing the Proth test.

The factoring upper limit is dependent on the exponent size, and can

reach 86 bits, as for GIMPS.

Also, an option allows to use the LLR program for a factoring-only job.

For example, to use this option for prefactoring candidates up to 40

bits factor, add the line "FacTo=40" in the llrxxxx.ini file.

I think we have now an efficient tool, and that the time for a

systematic search for Gaussian-Mersenne primes has arrived!

Beside this new feature, the new LLR is identical as 3.6.2 version,

with only some secondary corrections and error recovery improvings :

-The InterimResidues and InterimFiles options have been added, and work

exactly as in Prime95/Mprime.

-The rounding error recovery has been improved.

-When an error opening output file occurs, the current result is now

saved in the Log file.

-A wrong order bug on Lucky plus and Lucky minus tests has been fixed.

You may read the Readme.txt file for more precisions.

I wish this work would help you for many big prime discoveries in the

near future!

Best Regards,

Jean - At 05:28 AM 4/23/2006, you wrote:
>The Prime95 libraries that LLR uses contain large quantities of

You'll be glad to know that the interface was improved last year. It is

>exceptionally optimised hand-coded assembly. However, the interface

>looked like a train-wreck, I just didn't want to touch it.

now just an automobile accident.