20130304, 03:07  #1 
Dec 2012
2·139 Posts 
Possible P1 Entry Example Error
Been trying to figure out P1 (I've mostly got it now) and I think there's an error with the example.
237876521^29 does not equal 171331425 (mod 2^291), but rather is 337474461 (mod 2^291). 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 P1, 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. 
20130304, 03:32  #2 
Romulan Interpreter
Jun 2011
Thailand
10001010101100_{2} Posts 
Try figuring out more :D
Code:
gp > a=Mod(237876521,1<<291)^29 %1 = Mod(171331425, 536870911) gp > gcd(%1,1<<291) %2 = Mod(486737, 536870911) gp > 
20130304, 04:10  #3 
Dec 2012
426_{8} Posts 
I'm afraid I don't get your point. The way that is written makes no sense to me. Are you showing me why I'm wrong, or why I'm right?
Sorry if I made a mistake. 
20130304, 04:20  #4  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{3}·7·163 Posts 
Quote:
You can use multiple tools to do that; it is far from being tricky because 2^291 (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 

20130304, 04:32  #5 
Dec 2012
2·139 Posts 
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(17133142451,2^291) 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. Last fiddled with by Jayder on 20130304 at 04:42 
20130304, 04:41  #6 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{3}·7·163 Posts 
That's because you have a typo.

20130304, 04:45  #7 
Dec 2012
100010110_{2} Posts 
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. Last fiddled with by Jayder on 20130304 at 04:48 
20130304, 04:52  #8 
Romulan Interpreter
Jun 2011
Thailand
8876_{10} Posts 
P1 is very simple: From Fermat theorem, one has the fact that [TEX]b^{p1}=1[/TEX] (mod p) for any prime p. Therefore, raising both sides at any power k, you get [TEX]b^{k*(p1)}=1^k=1[/TEX] (mod p), or [TEX]b^{k*(p1)}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 p1 very fast, if that p1 has nothing but small factors. Then, taking the gcd of n with b[SUP]k*(p1)[/SUP][COLOR=Red][B]1 [/B][/COLOR]may reveal that factor. Edit: scrap this! Indeed there was a typo on wiki page. I just corrected it, by eliminating additional "4". Thanks for signaling it. Last fiddled with by LaurV on 20130304 at 04:58 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
odd entry on stats page  mdettweiler  Prime Sierpinski Project  3  20080827 18:34 
Formula entry enhancement?  Xyzzy  GMPECM  5  20070822 19:54 
wiki entry  delta_t  PSearch  2  20060521 07:05 
Error 5 causes userid change and error 17 updates for exponents  Old man PrimeNet  PrimeNet  0  20060205 02:27 
ERROR: Primenet error 2252. Q: which tcp/ip ports are being used for the transfer?  nevillednz  PrimeNet  15  20040517 23:08 