mersenneforum.org (https://www.mersenneforum.org/index.php)
-   mersennewiki (https://www.mersenneforum.org/forumdisplay.php?f=57)
-   -   Possible P-1 Entry Example Error (https://www.mersenneforum.org/showthread.php?t=17878)

 Jayder 2013-03-04 03:07

Possible P-1 Entry Example Error

Been trying to figure out P-1 (I've mostly got it now) and I think there's an error with [URL="http://mersennewiki.org/index.php/P-1_Factorization_Method#Example"]the example[/URL].

237876521^29 does not equal 171331425 (mod 2^29-1), but rather is 337474461 (mod 2^29-1).

Further: when you take the gcd of either the old incorrect remainder or this new one, you get a gcd of 1. A fail for P-1, I believe. I'm guessing the bound needs to be risen?

This may belong in the Discussion part of the wiki, but I don't have a wiki account yet and I wasn't sure if it would be noticed.

 LaurV 2013-03-04 03:32

Try figuring out more :D

[CODE]
gp > a=Mod(237876521,1<<29-1)^29
%1 = Mod(171331425, 536870911)
gp > gcd(%-1,1<<29-1)
%2 = Mod(486737, 536870911)
gp >
[/CODE]

 Jayder 2013-03-04 04:10

I'm afraid I don't get your point. :sad: The way that is written makes no sense to me. Are you showing me why I'm wrong, or why I'm right? :blush:

Sorry if I made a mistake.

 Batalov 2013-03-04 04:20

[QUOTE=Jayder;331858]237876521^29 does not equal 171331425 (mod 2^29-1), but rather is 337474461 (mod 2^29-1).
[/QUOTE]
He was demonstrating that yes, 237876521^29 [I]does indeed [/I]equal 171331425 (mod 2^29-1), and that your calculation was wrong.

You can use multiple tools to do that; it is far from being tricky because 2^29-1 (536870911) is a small number.
One is shown above (Pari/GP).
Another way is using dc:
[CODE]> dc
237876521 29 ^ 2 29 ^ 1 - % p
171331425
[/CODE]Yet another way is to write it in C (Visual basic, C#, etc etc), using "long long" or a similar type and calculating 237876521^29 by brute force: multiply 237876521 by 237876521 28 times, taking %536870911 every time. Can you try that?

 Jayder 2013-03-04 04:32

I'm very sorry, the calculator I was using doesn't return that result. Too large a number I suppose. Thought I double checked in wolframalpha but I guess I forgot to.

But then, what about the gcd? gcd(1713314245-1,2^29-1) in wolfram alpha returns 1.

I am using windows so cannot use dc (or do not know how). I would use calc but the instructions provided for compiling(?) are not clear enough/too much trouble.

I am a layman. I can read pseudocode and that's about it. But I am trying to learn.

 Batalov 2013-03-04 04:41

That's because you have a typo.

 Jayder 2013-03-04 04:45

Yeah, I just figured that out. Only it's not my typo, it's in the wiki. As I do not have an account I cannot edit it myself.

Thanks for clearing this up for me.

 LaurV 2013-03-04 04:52

[strike]My point was not only about calculus. You did not get the method either, as you missed subtracting 1 from the "old result" before taking the gcd (see your "further" part), threfore missed the factor. This is part of the method, not of the calculus.

P-1 is very simple: From Fermat theorem, one has the fact that [TEX]b^{p-1}=1[/TEX] (mod p) for any prime p. Therefore, raising both sides at any power k, you get [TEX]b^{k*(p-1)}=1^k=1[/TEX] (mod p), or [TEX]b^{k*(p-1)}-1=0[/TEX] (mod p). Assuming you want to factor a big number n, which has a factor p, you might get lucky and find a multiple of p-1 very fast, if that p-1 has nothing but small factors. Then, taking the gcd of n with b[SUP]k*(p-1)[/SUP][COLOR=Red][B]-1 [/B][/COLOR]may reveal that factor.
[/strike]
Edit: scrap this! Indeed there was a typo on wiki page. I just corrected it, by eliminating additional "4". Thanks for signaling it.

 All times are UTC. The time now is 22:46.