Re: sigma explosion

[Phil Carmody <thefatphil@yahoo.co.uk>]

--- Igor Schein <igor@txc.com> wrote:
> OddPwrs: is
>
11383060931611972087309109789996968343219695883990256301855546143975326574480561146376352393480764093270004531343229460069640975362334863052665903147660436143963077669821714492900421706099931668095348370353939306558380975834271106415521419227974023535332867876933135397993776447501454350992330027448703725775032000902770797098006060636836292416703271897610369604149549615728266915657894812283903554997991520666350426291352422632334591235036729922462579117522094877
>         ...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
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.

Phil

=====
When inserting a CD, hold down shift to stop the AutoRun feature
In the Device Manager, disable the SbcpHid device.
http://www.cs.princeton.edu/~jhalderm/cd3/


		
__________________________________
Do you Yahoo!?
New and Improved Yahoo! Mail - Send 10MB messages!
http://promotions.yahoo.com/new_mail