View Single Post
Old 2013-03-04, 04:52   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

24·613 Posts
Default

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.

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 2013-03-04 at 04:58
LaurV is offline   Reply With Quote