IsPerfectPower
James Wanless
james at grok.ltd.uk
Wed Mar 16 13:08:00 CET 2011
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.
>>
More information about the gmp-discuss
mailing list