IsPerfectPower

[James Wanless]

No I don't think so - I think I'm referring to a different (ie later)  
alg.
J

On 16 Mar 2011, at 12:02, Will Galway wrote:

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