Re: sigma explosion

[Karim Belabas <Karim.Belabas@math.u-psud.fr>]

* 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]