Yes to the first question. No to the second.

[QUOTE=c10ck3r;333774]M1277 shows a B1 of 2*10^12 and a B2 of 3*10^13. If there was a prime k-value of about, say, 1*10^13, would stage 2 find it?
If so, does this mean it has, through P-1, been effectively TF'ed to 96.95 bits? (2*1277*2e12*3e13)[/QUOTE]

No. P-1 will find a factor 2kp+1 in stage 2 if there is a single prime in the factorisation of k between B1 and B2, and all other primes [i]and prime powers[/i] of the factorisation of k are < B1. Theoretically k could be a prime power a little over 2*10^12 and the factor will have been missed. This means that M1277 has been "TFed" by P-1 to 2*1277*2e12 which is about 52 bits, less than the real amount of TF.

However, there has also been a considerable amount of [url=http://mersenne.org/report_ECM/]ECM[/url] done on this exponent, so much that any factor less than 60 digits (200 bits) would most likely have been found. So while it remains a theoretical possibility that a small factor remains to be found, the expectation is that NFS will be needed to crack this number.

[QUOTE=Mr. P-1;333784]No. P-1 will find a factor 2kp+1 in stage 2 if there is a single prime in the factorisation of k between B1 and B2, and all other primes [I]and prime powers[/I] [/QUOTE](those last three words, I keep forgetting!)[quote]of the factorisation of k are < B1.

<snip>

This means that M1277 has been "TFed" by P-1 to 2*1277*2e12 which is about 52 bits, less than the real amount of TF.[/quote]Hmmm... could someone add to the [URL]http://www.mersenne.ca/exponent.php[/URL] so that it also shows the equivalent TF bit level that corresponds to the highest P-1 B1 bound done so far?

(Or maybe I should get energetic and learn PHP so I could add that myself ... Okay, it's on my to-do list.)

[QUOTE=Mr. P-1;333784]No. P-1 will find a factor 2kp+1 in stage 2 if there is a single prime in the factorisation of k between B1 and B2, and all other primes [I]and prime powers[/I] of the factorisation of k are < B1. Theoretically k could be a prime power a little over 2*10^12 and the factor will have been missed. This means that M1277 has been "TFed" by P-1 to 2*1277*2e12 which is about 52 bits, less than the real amount of TF.

*snipped*[/QUOTE]

Would (1e13+37) have been found, then? By "Theoretically k could be a prime power a little over 2*10^12 and the factor will have been missed", do you mean, say, k=2^41 would have been missed? Thanks for clarification!

P-1 is a factoring method based on Fermat's theorem. To be more clear, when we apply this to mersenne numbers, we should call it "q-1" factoring method, as we normally use p to denote the exponent, and it is confusing, specially for newcomers.

So, Fermat says that for a prime q, and a base b which is not multiple of q, we always have b[SUP]q-1[/SUP]=1 (mod q).

This implies the fact that b[SUP]s*(q-1)[/SUP]=1[SUP]s[/SUP]=1 (mod q) for any natural s. Or, we can say that b[SUP]s*(q-1)[/SUP]-1 is a multiple of q, note this number z=q*x.

Now assume q is a factor of some mersenne number Mp=2[SUP]p[/SUP]-1.

This means Mp=q*y. So, if we do a GCD of Mp and z=b[SUP]s*(q-1)[/SUP]-1=qx, we find the common factor q.

How can we find z? Generally, we can not find it. What "q-1" algorithm is doing, we take a random b (for P95 this is 3) and we raise it at some power a lot of times, computing y=(((...(((b^p[SUB]1[/SUB])^p[SUB]2[/SUB])^p[SUB]3[/SUB])...)...)...)^p[SUB]n[/SUB] and we [B]might be lucky[/B] that the product of all p[SUB]i[/SUB] contains all factors of q-1, and other numbers (whose product is s), so we have our z=b[SUP]s*(q-1)[/SUP]. If so, the gcd of y-1(=z) and Mp will reveal the factor.

For this to happen, ALL factors of q-1 must be contained in the product of those p[SUB]i[/SUB].

For the case of mersenne numbers, we already know the fact that any factor q has the form q=2*k*p+1, for some natural k. So, q-1 is in fact 2*k*p. So, by already considering p[SUB]0[/SUB]=2 and p[SUB]1[/SUB]=p in the product above, we reduce the problem from "factors of q-1" to "factors of k".

So, rephrase: For this to happen, ALL factors of k must be contained in the product of those p[SUB]i[/SUB], for i=3 to n.

I said all factors, not all prime factors. This means prime factors, and all their powers, and all their combinations.

What "q-1" algorithm came with new, is an efficient way to compute b at a power E equal to LCM(1, 2, 3, .... B1). So, like taking all natural numbers up to B1, prime or not, compute their product in an efficient way, take that LCM of them, be this E, and use this number as "s*(q-1)" given above. Or s*k, if you like, as we already added 2 and p to the product. Of course, this number is a product of many-many-many "small" numbers, and IF k has nothing but small factors, whose powers are under B1, then k is contained in this number, and we really have E=s*k for some s. In this case b[SUP]E*k[/SUP]-1 is a multiple of q, and the GCD will reveal a factor.

This is what [B]Stage 1[/B] of "q-1" algorithm is doing. It will find a factor of Mp if all factors of k raised at their powers are small enough (under B1).

Statistically, most of the composite numbers (k in our case) have a single factor which is much larger comparing with the other factors (this is because only one factor, maximum, can be over sqrt(k), and there are more primes between sqrt(k) and k/2 comparing with primes between 2 and sqrt(k), etc, for example, if k=10000, there are 25 primes under 100, and 644 primes between 100 and 5000, which will give 644 numbers of the form 2*prime<10k, also there are 445 primes between 100 and 3333, which give 445 primes of the form 3*prime<10k, then 342 numbers which are 4*prime, then 278 which are 5*prime, etc.

So, most of the numbers have a big factor, and then nothing but small factors.

As we already have computed c=b[SUP]E[/SUP] and did not find a factor, we can try our luck by randomly picking a large prime, p[SUB]x[/SUB] between B1 and a larger limit B2, and compute c^p[SUB]x[/SUB]. If p[SUB]x[/SUB] is "that big factor of k", we are done. If not, we may pick another, and try again, compute c^p[SUB]y[/SUB], etc.

What [B]Stage 2[/B] of "q-1" is doing, it comes with an efficient way to raise c at all primes between B1 and B2 by doing cheap multiplications instead of expensive powering.

So, stage 2 will find a factor q=2kp+1 of Mp, when all factors of k raised ar their powers are smaller then B1, except a single factor which can be between B1 and B2.

(still some lunch break left, but reserved for corrections :smile:, expecting axn or some others to jump...:razz:)

[QUOTE=c10ck3r;333806]Would (1e13+37) have been found, then? By "Theoretically k could be a prime power a little over 2*10^12 and the factor will have been missed", do you mean, say, k=2^41 would have been missed? Thanks for clarification![/QUOTE]

Yes and yes.

[URL="http://www.mersenne.org/report_exponent/?exp_lo=61829237"]61829237[/URL] has a factor(P-1): [URL="http://www.mersenne.ca/exponent/61829237"]788336251820136770338211725470049[/URL]
109.28 bits. :banana:

P-1 found a factor in stage #2, B1=585000, B2=10530000.
M[URL="http://www.mersenne.ca/exponent/62407999"]62407999[/URL] has a factor: 3961718768062037610391289 (81.712 bits)

k=2^[SIZE=2]2 × 7 × 19 × 1583 × 7001 × 5383451[/SIZE]

This is my first factor in 60M range and my largest prime factor so far.

M75001907 has a factor: 1010802793688728611211724617. This was found in P-1 Stage 1. The factor is 89.708 bits and prime. [TEX]k = 2^2 \times 3^3 \times 13^3 \times 1297 \times 130817 \times 167381.[/TEX]

P-1 factor for M60293969: 1222657127492229705673250308913 99.9 bits!

P-1 found a factor in stage #2, B1=585000, B2=10822500.
UID: Jwb52z/Clay, M62319203 has a factor: 44059018962638311977599

75.222 bits.