[QUOTE=S34960zz;280158]the B1 and B2 values are listed on the exponent status page. Is the E value saved somewhere as well? Does it matter?[/QUOTE]As far as I know, the B1/B2 bounds are recorded by PrimeNet but the E value is not. The E value represents how much (and if at all) the Brent-Suyama extension was used. With generous amounts of memory this allows P-1 to find a factor that is outside the normal P-1 factor range. It's there possible that a factor could be found with certain bounds by using the extension, but not found if the extension wasn't used. If a factor was found it apparent whether the B-S extension was necessary to find it; if no factor was found there's no way to know whether the extension was used if that data wasn't recorded. But no, it doesn't matter a whole lot.

A question of my own: can someone explain in simple terms how does the Brent-Suyama extension translate into (small) increased chance of finding a factor beyond the normal bounds? I assume it's nothing so simple as being equivalent to a higher B2?

[QUOTE=James Heinrich;280162]A question of my own: can someone explain in simple terms how does the Brent-Suyama extension translate into (small) increased chance of finding a factor beyond the normal bounds? I assume it's nothing so simple as being equivalent to a higher B2?[/QUOTE]

Recall that stage 1 computes S=3[sup]E[/sup] where E is the product of prime powers less than B1. Then by Fermat's Little Theorem, a prime number p | S-1 if p-1 | E

A naive stage 2 would then compute T=S[sup]q[/sup] = 3[sup]E*q[/sup] for successive prime q in the range (B1,B2]. Then p | T-1 if p-1 | q*E.

Slicker would be to note that all primes > 3 are of form 6k+/-1. Suppose instead that we compute T=S[sup](6k)[sup]2[/sup]-1[/sup] = 3[sup]E*(6k-1)*(6k+1)[/sup] whenever one of 6k+1 or 6k-1 is prime. If both are prime, then we get to include two for the price of one. Even if only one is prime, the other may be a multiple of some other prime > B1, so with a bit of planning, we may be able to skip that prime on the way up, and thus again get two for the price of one. This is called "prime pairing".

Brent-Suyama instead computes T=S[sup](6k)[sup]e[/sup]-1[/sup], where e is a small even number >2. (6k)[sup]e[/sup]-1 = (6k-1)*(6k+1)*(a higher order polynomial in k). The algorithm will then find a factor p if the largest prime factor of p-1 is 6k-1, 6k+1, or if it is a factor of the higher order polynomial evaluated at some k between B1/6 and B2/6 - and all other factors of p-1 are below B1. It is this latter case, whether the relevant prime factor of the higher order polynomial happens to be > B2, that the additional factors are found.

Note that there is nothing special about the number 6, other than that it is a primorial. A larger primorial increases the proportion of primes that pair up, at the cost of having to consider a larger number of congruence classes "relatively prime" to it, and consequently a larger memory requirement. Prime95 uses 30, 210, and 2310, depending upon the available memory.

Did you get all that from the source, or ...? Did you code it yourself into P95? Who did? George? akruppa? Brent and Suyama?

Otherwise very interesting :)

[QUOTE=Mr. P-1;280258]Note that there is nothing special about the number 6, other than that it is a primorial. A larger primorial increases the proportion of primes that pair up, at the cost of having to consider a larger number of congruence classes "relatively prime" to it, and consequently a larger memory requirement. Prime95 uses 30, 210, and 2310, depending upon the available memory.[/QUOTE]I would assume that these equate to the E=__ values in Prime95 output of E=4, E=6, E=12... but I can't quite figure out how that makes sense? 4#=6; 6#=30; 12#=2310. 210 would be a good value to use, but that's 10# and I've never seen E=10 in any results...?

Otherwise, thanks for the explanation (despite it being completely beyond my ken). I've immortalized it in the wiki since there was no article for that. Please make any corrections there if I messed anything up:
[url]http://www.mersennewiki.org/index.php/Brent-Suyama_extension[/url]

[QUOTE=James Heinrich;280263] S=3E[/QUOTE]

Should be S=3^E (don't have a wiki account)
And then a period at the end of the second line

Edit: Oops, again:

T=Sq = 3E*q should be
T=S^q = 3^(E*q)
I do believe that wiki software has a way of making super/subscripts somewhere, to prettify it.

[QUOTE=Dubslow;280267]Should be S=3^E (don't have a wiki account). And then a period at the end of the second line.[/QUOTE]Changed.

[QUOTE=James Heinrich;280268]Changed.[/QUOTE]

There are still several exponents not superscripted:

[quote]A naïve stage 2 would then compute T=Sq = 3E*q ... Brent-Suyama instead computes T=S(6k)e-1[/quote]

All in all, I'd prefer that the wiki page were written by an expert, i.e., not me.

Better you than nothing. akruppa?

[QUOTE=James Heinrich;280263]I would assume that these equate to the E=__ values in Prime95 output of E=4, E=6, E=12... but I can't quite figure out how that makes sense? 4#=6; 6#=30; 12#=2310. 210 would be a good value to use, but that's 10# and I've never seen E=10 in any results...?[/QUOTE]

No, E in the output equates to e in my explanation - the Brent-Suyama exponent. The small primorial is d in the source code, but isn't directly indicated in the output. You can see its effect, though:

[tex]\phi[/tex](30)=8
[tex]\phi[/tex](210)=48
[tex]\phi[/tex](2310)=480

Where [tex]\phi[/tex](x) is Euler's totient function - the number of congruences (mod x) which are relatively prime to x.

So you're saying that in T=S[sup](z*k)[sup]e[/sup]-1[/sup]
e=4,6,12 (or whatever we see in the results line) and
z=30,210,2310 ?

Then e would have to be even, otherwise you can't factor the square out...

[QUOTE=Mr. P-1;280281]There are still several exponents not superscripted[/QUOTE]Indeed, sorry. I think I've got them all now. Not perfectly pretty, but hopefully no longer incorrect.