IsPerfectPower

[Will Galway]

I've just had a look at Cohen's A COURSE IN COMPUTATIONAL NUMBER THEORY, 
Vol 1, the 1993 edition -- where he presents an Algorithm 1.7.4 (there 
is no Algorithm 1.7.5).  Given a number $n$, Algorithm 1.7.4 determines 
whether $n$ has the form $p^k-1$, where $p$ is prime -- it does not 
apply to the case where $p$ is composite.  Is this the Algorithm we're 
discussing, or is there an Algorithm 1.7.5 in a later edition?

-- Regards, Will

On 03/16/2011 07:15 AM, Torbjorn Granlund wrote:
> James Wanless<bearnol at gmail.com>  writes:
>
>    There is a method for finding PerfectRoots, which I discovered independently
>    a while ago, but recently noticed is also in Cohen ACCANT Algorithm 1.7.5.
>    When I last looked at the GMP source, this hadn't yet been implemented, but
>    it's quite possible ( :) ) you're all already aware of it, and it has been
>    discounted for some other reason...
>
> Is this an algorithm for computing a^{1/b} which works just when a is an
> integer (and b is an integer too)?
>
> We don't have, but that should be very simple to do using 2^t-adic
> arithmetic and lifting (increasing t).  Is that what ACCANT does?
>
> I guess a good implementation it would be less than a page of mpn code.
>