- --- In primenumbers@yahoogroups.com, mikeoakes2@... wrote:

> That's great news, Jean!

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

>

> 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 page:

> http://www.mersenne.org/gimps/

> which must be it, yes?

>

revived.

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

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.

possibly...

> One of you guys with a classroom-ful of PCs?...

>

> >(nevertheless, the

entry:-

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

> 123f 2^991961-2^495981+1 298611 x28 2005

one to:

> Gaussian Mersenne norm 36?

>

> The reason is that Boris has never stated whether this is the next

> 1156 2^364289-2^182145+1 109662 p58 2001

sweeping that intermediate range, which may well be duplicted effort.

> 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

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 - --- In primenumbers@yahoogroups.com, Jean Penné <jpenne@...> wrote:
>

Thanks very much, Jean, for a significant speed up over version 3.6.2

> Hi All,

>

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

>

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

>

> 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

> - --- eharsh82 <harsh@...> wrote:
> Hi,

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

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

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