## LLR Version 3.7.0 released

Expand Messages
• 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
Message 1 of 7 , Apr 3, 2006
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.

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

Best Regards,
Jean
• ... That s great news, Jean! I had a job to find it from your instructions on the GIMPS directory . Using google, I homed in on the file LLR370.zip at this
Message 2 of 7 , Apr 4, 2006
Jean Penné <jpenne@...> wrote:

>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.

That's great news, Jean!

I had a job to find it from your instructions "on the GIMPS directory".
http://www.mersenne.org/gimps/
which must be it, yes?

It would be really nice if the search for Gaussian Mersennes was revived. I devoted a lot of time to it some years back, and have no more cycles to spare.
One of you guys with a classroom-ful of PCs?...

>(nevertheless, the
>actual record, GM(991961) , has been discovered by Boris Iskra
>in November 2005).

It's really unfortunate that Chris has to put the "?" aginst this entry:-
123f 2^991961-2^495981+1 298611 x28 2005
Gaussian Mersenne norm 36?

The reason is that Boris has never stated whether this is the next one to:
1156 2^364289-2^182145+1 109662 p58 2001
Gaussian Mersenne norm 35
or not, in spite of having been asked, on and off list.

Without an answer, there seems no real alternative to someone sweeping that intermediate range, which may well be duplicted effort.

There is exactly the same problem about his "Eisenstein Mersenne" record:
152f 3^534827-3^267414+1 255178 x28 2005

Is it the /next/ one after this:
891 3^255361-3^127681+1 121839 p96 2002
or not?

Are you listening, Boris...?

-Mike Oakes
• ... Yes, indeed! I am sorry for this too vague info... ... revived. I hope (and think) it will be the case! ... I know that! ... possibly... ... entry:- ...
Message 3 of 7 , Apr 4, 2006

> That's great news, Jean!
>
> I had a job to find it from your instructions "on the GIMPS directory".
> http://www.mersenne.org/gimps/
> which must be it, yes?

Yes, indeed! I am sorry for this too vague info...

>
> It would be really nice if the search for Gaussian Mersennes was
revived.

I hope (and think) it will be the case!

> I devoted a lot of time to it some years back,

I know that!

>and have no more cycles to spare.
> One of you guys with a classroom-ful of PCs?...
>

possibly...

> >(nevertheless, the
> >actual record, GM(991961) , has been discovered by Boris Iskra
> >in November 2005).
>
> It's really unfortunate that Chris has to put the "?" aginst this
entry:-
> 123f 2^991961-2^495981+1 298611 x28 2005
> Gaussian Mersenne norm 36?
>
> The reason is that Boris has never stated whether this is the next
one to:
> 1156 2^364289-2^182145+1 109662 p58 2001
> Gaussian Mersenne norm 35
> or not, in spite of having been asked, on and off list.
>
> Without an answer, there seems no real alternative to someone
sweeping that intermediate range, which may well be duplicted effort.

If you agree,
I think I can do this job, having already prefactored the corresponding
candidates up to 40 bits factors, so it would not be too time consuming.

Regards,
Jean
• ... Thanks very much, Jean, for a significant speed up over version 3.6.2 on some P4s at 2.6M bits (321). For example, at 2.5GHz I have noticed the times for a
Message 4 of 7 , Apr 11, 2006
--- In primenumbers@yahoogroups.com, Jean Penné <jpenne@...> wrote:
>
> Hi All,
>
> The new LLR 3.7.0 Version is now available on the GIMPS directory!
>

Thanks very much, Jean, for a significant speed up over version 3.6.2
on some P4s at 2.6M bits (321). For example, at 2.5GHz I have noticed
the times for a test dropping from 4:30 hours to 3:50 hours,

Paul
• Hi, I just wanted to mention the following:- The algorithm described in LLR3.7 can be extended to several other forms of numbers. In short, all forms that are
Message 5 of 7 , Apr 22, 2006
Hi,
I just wanted to mention the following:-

The algorithm described in LLR3.7 can be extended to several other
forms of numbers. In short, all forms that are factors of k*a^n+-1,
where k can be 1 to a positive integer can be tested faster than PFGW
using this algorithm.

I think that the PIES project will benefit from the algorithm if Phll
wants to implement it.

(May be Dr. Cadwell can post the algorithm on his Gaussian Mersenne
webpage, so other people can understand and improve on it)

Thanks, Harsh

--- In primenumbers@yahoogroups.com, Jean Penné <jpenne@...> wrote:
>
> 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.
>
>
> I wish this work would help you for many big prime discoveries in the
> near future!
>
> Best Regards,
> Jean
>
• ... _If_ you can quantitatively detail the benefits I ll look at it. I already use a combination of DWTs which include _no wastage at all_. You only make FFTs
Message 6 of 7 , Apr 23, 2006
--- eharsh82 <harsh@...> wrote:
> Hi,
> I just wanted to mention the following:-
>
> The algorithm described in LLR3.7 can be extended to several other
> forms of numbers. In short, all forms that are factors of k*a^n+-1,
> where k can be 1 to a positive integer can be tested faster than PFGW
> using this algorithm.
>
> I think that the PIES project will benefit from the algorithm if Phll
> wants to implement it.

_If_ you can quantitatively detail the benefits I'll look at it.

I already use a combination of DWTs which include _no wastage at all_.
You only make FFTs larger if you don't have modular reduction for
free anyway. The new LLR technique adds _significant_ wastage.

PIES could most benefit from not being written in pure portable C.
(And only being a few tens of kilobytes of code at that.)
The Prime95 libraries that LLR uses contain large quantities of
exceptionally optimised hand-coded assembly. However, the interface
looked like a train-wreck, I just didn't want to touch it.

An FFT that's 1.5x faster than my version of DJBFFT could beat my
current implementation by using this 'short cut'. However, if I had
an FFT which was 1.5x faster, then this 'short cut' would be
significantly slower.

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
• ... You ll be glad to know that the interface was improved last year. It is now just an automobile accident.
Message 7 of 7 , Apr 23, 2006
At 05:28 AM 4/23/2006, you wrote:
>The Prime95 libraries that LLR uses contain large quantities of
>exceptionally optimised hand-coded assembly. However, the interface
>looked like a train-wreck, I just didn't want to touch it.

You'll be glad to know that the interface was improved last year. It is
now just an automobile accident.
Your message has been successfully submitted and would be delivered to recipients shortly.