Karim Belabas on Fri, 24 Sep 2004 19:52:11 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: sigma explosion |
* Phil Carmody [2004-09-23 23:46]: > If you're checking other powers, then I assume you perform an initial modular > reduction modulo some small primes, in which case, throwing a few extra primes > into the reduction would probably incur little runtime penalty. > Just squeezing 137149 into it would throw out >99.9% of non-11th powers right > away. 548497 dismisses >99.95% of non-13th powers. > > Draw the line at a point such that higher powers would be spotted easily by > Rho/ECM. > > Detecting perfect powers is incomparably less expensive than factoring. I find > chosing the latter over the former to be non-intuitive, in particular when > non-powers can be detected on average even faster than perfect powers. I'm not too keen on that: larger code, harder to maintain (tables...) catering for events with negligibly small probability, etc. [ also it would probably slow things down unless we complicate further the factoring code: it would get called each time a factor is found ] I have just committed a stupid function for this kind of things, which I found myself doing over and over again by hand, which is the straightforward generalization of issquare() [ doesn't even do modular checks for 11th powers and higher at this point, it being almost instantaneous anyway ] isperfectpower(x,{&n}): return the maximal k >= 2 such that x = n^k is a perfect power, or 0 if no such k exist. If n is given puts the exact k-th root there. This is not used by the factoring machinery at this point [ it might be someday if somebody makes it more clever, along the lines you suggested ], so if you're interested in factoring things which migh be k-th powers where k is not 7-smooth, you can do something like if (isperfectpower(n, &c), addprimes(c)); Cheers, Karim. P.S: There are obvious extensions of the above for rational numbers and polynomial/rational functions [ where it becomes a straightforward x / gcd(x,x') ]. Not implemented yet. -- Karim Belabas Tel: (+33) (0)1 69 15 57 48 Dep. de Mathematiques, Bat. 425 Fax: (+33) (0)1 69 15 60 19 Universite Paris-Sud http://www.math.u-psud.fr/~belabas/ F-91405 Orsay (France) http://pari.math.u-bordeaux.fr/ [PARI/GP]