Question about selection of a in the P-1 algorithm
 

From [URL]https://www.mersenne.org/various/math.php[/URL]

[QUOTE]
The P-1 method is quite simple. In stage 1 we pick a bound B1. P-1 factoring will find the factor q as long as all factors of k are less than B1 (k is called B1-smooth). We compute E – the product of all primes less than B1. Then we compute x = 3[SUP]E*2*P[/SUP]. Finally, we check the GCD (x-1, 2[SUP]P[/SUP]-1) to see if a factor was found.
[/QUOTE]When computing x, why are we taking 3[SUP]E*2*P[/SUP] instead of 2[SUP]E*2*P[/SUP]?

Wouldn't any coprime number do? If so, why not choose the smaller one?

The reason: 2^(E*2*p)==1 mod 2^p-1.

[QUOTE=ZFR;566179]From [URL]https://www.mersenne.org/various/math.php[/URL]

When computing x, why are we taking 3[SUP]E*2*P[/SUP] instead of 2[SUP]E*2*P[/SUP]?

Wouldn't any coprime number do? If so, why not choose the smaller one?[/QUOTE]
E is not just the product of the primes < B1, it's the product of maximum integral powers of each prime fitting < B1 individually, called powersmooth.
The exponentiation [B]a[/B][SUP]E*2*p[/SUP] is done mod Mp. So smaller [B]a[/B] doesn't really save run time, or operand size after relatively few operations. In practice the exponentiation is done with a full length fft transform from the start, so it saves no run time to use a smaller base.
[URL="https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm"]https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm[/URL]
As to why not 2 instead of 3, there's a small-numbers example early in [URL]https://magazine.odroid.com/article/prime-number-discovery-use-odroid-c2-make-mathematical-history/[/URL] Later on, this same source includes, also in the context of primality testing, rather than P-1 factoring, the following:
[CODE]In the more general context of testing numbers of arbitrary size, however,
it is important to realize that there are certain classes of numbers, all
of which are Fermat base-2 pseudoprimes, irrespective of whether they are
prime or composite. The two best-known such classes are, firstly, the
Mersenne numbers M(p) = 2[SUP]p[/SUP]−1 (for which we restrict the definition to prime
exponents since that is required for a number of this form to have a chance
of being prime); for example, 2[SUP]11[/SUP]−1 passes the test even though it factors as
23 × 89. The second class of such numbers is the Fermat numbers[/CODE]

[QUOTE=kriesel;566200] the product of maximum integral powers of each prime fitting < B1 individually[/QUOTE]
Haha, so complicate said. E is the LCM(x such as x<=B1). The "power trick" just happens to be the fastest known way to calculate it.

Ah, OK. So for base a=2 we'll have pseudoprimes only because 2^(E*2*p) is always 1 mod 2^p-1

Thanks, everyone.

Thanks for the article link, kriesel.

[QUOTE=LaurV;566239]Haha, so complicate said. E is the LCM(x such as x<=B1). The "power trick" just happens to be the fastest known way to calculate it.[/QUOTE]Instead of criticizing from the stands, try entering the arena. "It is not the critic who counts; not the man who points out how the strong man stumbles, or where the doer of deeds could have done them better. The credit belongs to the man who is actually in the arena, whose face is marred by dust and sweat and blood; who strives valiantly; who errs, who comes short again and again, because there is no effort without error and shortcoming; but who does actually strive to do the deeds; who knows great enthusiasms, the great devotions; who spends himself in a worthy cause; who at the best knows in the end the triumph of high achievement, and who at the worst, if he fails, at least fails while daring greatly, so that his place shall never be with those cold and timid souls who neither know victory nor defeat."
[url]https://www.mentalfloss.com/article/63389/roosevelts-man-arena[/url]

@OP: Suggest you try a tiny M(p) example: n = M(11) = 2^11-1 = 23*89. The 2 prime factors have p-1 decompositions:

p = 23: p-1 = 2*11
q = 89: q-1 = 2^3*11

So taking E = 2*11 in p-1 stage 1 should turn up the smaller factor, i.e. in this case we don't even need any of the other smaller primes, just the 2*p bit, in E. Try it to the 2 bases in question and see what happens.

[QUOTE=kriesel;566313]Instead of criticizing from the stands, try entering the arena. "It is not the critic who counts; not the man who points out how the strong man stumbles, or where the doer of deeds could have done them better. The credit belongs to the man who is actually in the arena, whose face is marred by dust and sweat and blood; who strives valiantly; who errs, who comes short again and again, because there is no effort without error and shortcoming; but who does actually strive to do the deeds; who knows great enthusiasms, the great devotions; who spends himself in a worthy cause; who at the best knows in the end the triumph of high achievement, and who at the worst, if he fails, at least fails while daring greatly, so that his place shall never be with those cold and timid souls who neither know victory nor defeat."
[url]https://www.mentalfloss.com/article/63389/roosevelts-man-arena[/url][/QUOTE]

Please don't overreact. AFAICS, LaurV's comment talked about no _person_ at all and
I believe having opinions about _ideas_ is always fine.

[QUOTE=ewmayer;566325]@OP: Suggest you try a tiny M(p) example: n = M(11) = 2^11-1 = 23*89. The 2 prime factors have p-1 decompositions:

p = 23: p-1 = 2*11
q = 89: q-1 = 2^3*11

So taking E = 2*11 in p-1 stage 1 should turn up the smaller factor, i.e. in this case we don't even need any of the other smaller primes, just the 2*p bit, in E. Try it to the 2 bases in question and see what happens.[/QUOTE]

Thanks.

gcd(4194303, 2047) = 2047
gcd(31381059608, 2047) = 23

So using base 2 gives us n, while using base 3 gives us the right answer.

I played around with some other Mersenne numbers. The gcd always returns n.

I might be overlooking something very obvious here, but I'm still missing one step.

How does
2^(E*2*p)==1 mod 2^p-1.
imply that
gcd(2^(E*2*p)-1, 2^p-1) = 2^p -1

[QUOTE=ZFR;566363]How does
2^(E*2*p)==1 mod 2^p-1.
imply that
gcd(2^(E*2*p)-1, 2^p-1) = 2^p -1[/QUOTE]

2^(E*2*p)==1 mod 2^p-1
==>
2^(E*2*p)-1 == 0 mod 2^p-1

Therefore gcd(2^(E*2*p)-1, 2^p-1) = gcd(0, 2^p-1) = 2^p-1

[QUOTE=axn;566364]2^(E*2*p)==1 mod 2^p-1
==>
2^(E*2*p)-1 == 0 mod 2^p-1

Therefore gcd(2^(E*2*p)-1, 2^p-1) = gcd(0, 2^p-1) = 2^p-1[/QUOTE]

OK, thanks for explaining. Yeah, it's pretty basic, I can be blind at times.

One last question: when Prime95 does the P-1 algorithm, that time-consuming part of it would be the exponentiation of 3 (and modulo n)? The gcd itself is pretty fast comparatively, right?

[QUOTE=jnml;566362]Please don't overreact. AFAICS, LaurV's comment talked about no _person_ at all and
I believe having opinions about _ideas_ is always fine.[/QUOTE]Quoting was sufficient. Over time, patterns emerge. There are some on the forum whose contributions are quite commonly cynical or critical and not so commonly constructive or enlightening. The incidence of that among moderators is dismayingly high. Perhaps you have been fortunate enough to not be subjected to that, or threats by some, repeatedly.

[QUOTE=ZFR;566366]One last question: when Prime95 does the P-1 algorithm, that time-consuming part of it would be the exponentiation of 3 (and modulo n)? The gcd itself is pretty fast comparatively, right?[/QUOTE]

Yes and yes. Well, there is also the stage 2.

Thanks, everybody.

[QUOTE=kriesel;566370]Quoting was sufficient. Over time, patterns emerge. There are some on the forum whose contributions are quite commonly cynical or critical and not so commonly constructive or enlightening. The incidence of that among moderators is dismayingly high. Perhaps you have been fortunate enough to not be subjected to that, or threats by some, repeatedly.[/QUOTE]

And yet, his post was enlightening- he said exactly what he thought the better explanation should be. And you went off about criticizing from the stands etc.

You post in nearly every single thread on this forum, speaking with the tone of an expert even when you don't know what you are talking about. When corrected, you nearly always take it personally, or write an even-longer-than-long-winded post to defend and explain your inaccurate post, and in the end present a know-it-all attitude that's really quite abrasive. Some of the moderators don't like the attitude, and treat you as such.

If your posts were half as long in half as many threads, I don't think you'd run into nearly the cynicism that you perceive- but you can't help yourself, and even when a question has already been answered you post a reply-answer anyway.

No one responded to the OP for hours. While I was trying to help, and understand/remember myself, researching an answer, and composing, previewing, and formatting [URL="https://www.mersenneforum.org/showpost.php?p=566200&postcount=3"]one[/URL] with helpful links, R. Gerbicz replied, very concisely. Ernst's explanation I quoted is useful. Etc.

Ok, people, thanks for jumping to my help, hehe, me and kriesel go long way back, so there was no harm done this time. I mean, I don't consider he harmed me in any way, ever. In fact, I really like his post #6, with the Roosevelt quote, albeit I don't consider myself a "gladiator in the arena". That's for show, and I understand some people like it. Not me. Anyhow, if he considers I harmed him in any way, now or in the past, is his problem. I still don't know how a random guy from the web, which you don't know, and who doesn't know you, can harm you with his [URL="https://youtu.be/-QJsljIDKkk?t=95"]arguments[/URL].

On the other hand, kriesel, buddy, I agree with Curtis' post that if you would post only half as much as you do, and limit to your "tutorials" (which I do use sometimes, and they were quite useful to me in the past, like for example when I was looking for the format of the worktodo lines for different work types, it was the easiest way to find it in your "tutorial", due to the well-done "contents" table), and to the subjects you really know, then your status and credibility here would be much higher. Have you ever seen me commenting about, say, gnfs, prime gaps, etc? No, I try to limit myself to subject I REALLY understand well (P-1 is one of them). And there, yeah, the RDS inside me sometimes overflows from my ears :razz:

For which, I don't apologize.