Phil Carmody on Thu, 23 Sep 2004 23:28:53 +0200

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: sigma explosion

--- Igor Schein <> wrote:
> OddPwrs: is
>         ...a 3rd, 5th, or 7th power?
>         modulo: resid. (remaining possibilities)
>            211:    6   (3rd 0, 5th 0, 7th 0)
> IFAC: trying Pollard-Brent rho method
> Rho: searching small factor of 1539-bit integer
> Rho: using X^2+5 for up to 49152 rounds of 32 iterations
>   *** factor: user interrupt after 1,560 ms.
> It's trivial to add, but where do you draw a line?  

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

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.


When inserting a CD, hold down shift to stop the AutoRun feature
In the Device Manager, disable the SbcpHid device.

Do you Yahoo!?
New and Improved Yahoo! Mail - Send 10MB messages!