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