View Single Post
Old 2012-06-29, 07:35   #129
Romulan Interpreter
LaurV's Avatar
"name field"
Jun 2011

2×4,903 Posts

Coming back to P-1 and Brent-Suyama, I think I changed my mind about requesting a wiki account (see my posts 114 and 120 here). Please make one account for me with the same name like here.

I saw someone did all the changes already for BrS article, but now my concern is the P-1 itself. There is a formulation like "Notice that when p-1 has a repeated prime factor greater than sqrt(n), E will not be multiple of p-1 and the method fails, but this happens with a very low probability".

The method (stage 1) will fail in most of the cases in wich there is a factor f^s of p-1, with f^s>B1, (except maybe when the order of the base is much smaller). The wiki formulation is complicated by that square root, and shows only a part of the truth, i.e. particularized for s=2. Also, having this in mind, one should not risk in making the affirmation about the probability of fail of the method, in general.
LaurV is offline