Run P-1 before PRP tests

[Mark Rose]

Originally Posted by VictordeHolland

James's site is mainly serving pages created from a database, so PHP makes a lot of sense. What is wrong with using PHP for this case?

There's nothing wrong with PHP, but it's a very incoherent language. I've been using it professionally for nine years, and a lot longer before that. It's the Visual Basic of the modern era.

[CRGreathouse]

[VictordeHolland]

Originally Posted by alpertron

The computer processed 42 numbers and it found more factors for Mersenne numbers with exponents 2300563, 2300731, 2300999 and 2301199. It is clear that something in the formulas related to the probability of finding factors using P-1 algorithm is wrong.

Originally Posted by alpertron

the computer found factors of M2301251 and M2301421.

These 6 had known factors before. I THINK the formula is for finding a first factor (GIMPS doesn't really care if a exponent has 1 or multiple factors, it just knows it doesn't need to run the 'expensive' LL test.) Also it assumes it has had decent trial factoring before, which rarely happens with exponents with known factors. Could the discrepancy come from this? (apart from the small sample size).

I can understand why people are reluctant to spend 0.12 GHzday to try P-1 if a PRP test on these low exponents only takes 0.15 GHzday

[alpertron]

GIMPS does care about all prime factors of Mersenne numbers. That's why it stores all prime factors found (not only the first one) and on GIMPS you can select to perform ECM on numbers that have at least one factor known, and you can also perform PRP on cofactors.

Notice that with the ECM worktype (3 curves with B1=50000, B2=5M), my computer found factors for the following Mersenne numbers:

M2302451, M2314951, M2333651, M2339797, M2357791, M2364161, M2365313 and M2379851 (14 days, two threads)

while using P-1 (B1=500000, B2=15M) my computer found factors for the following Mersenne numbers:

M2300017, M2300057, M2300153, M2300563, M2300731, M2300999, M2301199, M2301251 and M2301421 (1 day, 1 thread).

In both cases these numbers already had factors found. It is clear the P-1 in this range can find a lot more factors than ECM.

From TJAOI's work, the prime factors to be found will be greater than 34*10¹⁸ (about 65 bits).

[axn]

Originally Posted by VictordeHolland

These 6 had known factors before. I THINK the formula is for finding a first factor

No. The formula is for finding a "smooth" factor above the TF limit. It isn't affected by the existence of smaller factors.

However, ...

Now that I think about it, it might be underestimating the probability.

Basically, the formula looks at the probability of k part of P=2kp+1 being B1/B2 smooth. It assumes that k is a random number.

However k is not a random number. It is a factor of a (prime - 1). This ought to have different probabilities of divisibility by other primes. (For example, if k is truly random, it will be divisible by 3 with probability 1/3. However, since 3 cannot divide P, it will divide P-1 with probability 1/2, hence it will divide k with probability 1/2).

This might mean that the formula needs to be tweaked by a correction factor. It might not matter much in the end though -- the formula as such is a crude approximation.

Anybody willing to work on a more sophisticated estimate?

[chris2be8]

Originally Posted by Mark Rose

The Black Speech of Mordor.

Or the modern equivalent from intercal.txt.gz:

//INTERCAL PROC
//COMPILE EXEC PGM=INTERCAL
//STEPLIB DD DSN=U.INTERCAL.LIBRARY,DISP=SHR
//             DD DSN=SYS1.FORTLIB,DISP=SHR
//SYSPRINT DD SYSOUT=A,DCB=(BLKSIZE=992,LRECL=137,RECFM=VBA)
//SYSPUNCH DD DUMMY
//SCRATCH DD DSN=&COMPSET,UNIT=SYSDA,SPACE=(CYL,(3,1)),DISP=(,PASS)
//EXECUTE EXEC PGM=EXECUTE,COND=(4,LT)
//SOURCES DD DSN=U.INTERCAL.SOURCES,DISP=SHR
//STEPLIB DD DSN=U.INTERCAL.LIBRARY,DISP=SHR
//             DD DSN=SYS5.SPITLIB,DISP=SHR
//             DD DSN=SYS1.FORTLIB,DISP=SHR
//SYSIN DD DSN=&COMPSET,DISP=(OLD,DELETE)
//SYSOBJ DD SYSOUT=B,DCB=(BLKSIZE=80,LRECL=80,RECFM=F)
//SYSPRINT DD SYSOUT=A,DCB=(BLKSIZE=992,LRECL=137,RECFM=VBA)
//SYSPUNCH DD DUMMY
// PEND

Chris

[ET_]

Originally Posted by chris2be8

Or the modern equivalent from intercal.txt.gz:

//INTERCAL PROC
//COMPILE EXEC PGM=INTERCAL
//STEPLIB DD DSN=U.INTERCAL.LIBRARY,DISP=SHR
//             DD DSN=SYS1.FORTLIB,DISP=SHR
//SYSPRINT DD SYSOUT=A,DCB=(BLKSIZE=992,LRECL=137,RECFM=VBA)
//SYSPUNCH DD DUMMY
//SCRATCH DD DSN=&COMPSET,UNIT=SYSDA,SPACE=(CYL,(3,1)),DISP=(,PASS)
//EXECUTE EXEC PGM=EXECUTE,COND=(4,LT)
//SOURCES DD DSN=U.INTERCAL.SOURCES,DISP=SHR
//STEPLIB DD DSN=U.INTERCAL.LIBRARY,DISP=SHR
//             DD DSN=SYS5.SPITLIB,DISP=SHR
//             DD DSN=SYS1.FORTLIB,DISP=SHR
//SYSIN DD DSN=&COMPSET,DISP=(OLD,DELETE)
//SYSOBJ DD SYSOUT=B,DCB=(BLKSIZE=80,LRECL=80,RECFM=F)
//SYSPRINT DD SYSOUT=A,DCB=(BLKSIZE=992,LRECL=137,RECFM=VBA)
//SYSPUNCH DD DUMMY
// PEND

Chris

That's JCL...

[LaurV]

Originally Posted by axn

Anybody willing to work on a more sophisticated estimate?

I always use to multiply that by 2, which somehow matched with my results (number of factors) in the past when I had like 20 GPUs doing TF assignments from Chris' site. You may remember that I was always finding more factors than expected, and I used to joke that I am a lucky guy (which I still do sometimes). But a real reason may be that we need to multiply everything by 2 or so, including for P-1. I can not offer a more "mathematical" explanation for it, but a reason may be the fact that indeed, k in q=2kp+1 is not a random number, but it can only be "0 or 1 (mod 4)" if p=3 (mod 4), or it can be "0 or 3 (mod 4)" if p=1 (mod 4). So, it is somehow "half" of the four possible cases in each category.

For the case in this thread, the sample is too small. I also remember having long strikes of bad luck, where I could not uncover a P-1 factor for weeks, and then finding lots of factors in the same day (or week).

[chris2be8]

Originally Posted by ET_

That's JCL...

I know what it is. But it's the best candidate for The Black Speech of Mordor I've seen.

My happiest memory of it was the expression on my sister's face after I explained the COND statement to her...

Chris

[wblipp]

Has anybody checked if the heuristic for B1/B2 smooth is near the real value? The comments in the code sample indicate that the code generates a smashup estimate calculated from the function for being b-smooth at multiple values of b. But there is a known formula for being B1/B2 smooth. It may be more complex than we want to calculate on the fly, but a handful of test cases could be calculated.

Here are the code comments:

Originally Posted by VictordeHolland

The calculator uses more or less the same code as Prime95:

/* If $temp < 1.0, then there are no factor to find in this bit level */
        if ($LogTemp > 0) {

/* See how many smooth k's we should find using B1 */
/* Using Dickman's function (see Knuth pg 382-383) we want k^a <= B1 */
            $Prob1 = DickmansFunction($logB1 / $LogKK);

/* See how many smooth k's we should find using B2 */
/* Adjust this slightly to eliminate k's that have two primes > B1 and < B2 */
/* Do this by assuming the largest factor is the average of B1 and B2 */
/* and the remaining cofactor is B1 smooth */

The exact B1/B2 formula has been discussed a few time. I had a pissing contest with RDS about it in 2004 because it is wrong in his famous Wagstaff paper. We finally agreed my guess was correct when we discovered Richard Brent saying the same thing in 1985 - see equation 3.3 in the full pdf.

I don't currently have access to good tools to do the numerical integration - perhaps someone else can check a few cases?

[CRGreathouse]

I don't think Dickman's rho is particularly accurate in that range -- I wonder if we'd be better off checking numbers for smoothness directly.