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

24·613 Posts

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