Potential bug in mpz_perfect_power_p - #4612 in Sage's trac

[mabshoff]

Hi,

John Cremona and Robert Bradshaw are having a discussion about some
potential bug in

mpz_perfect_power_p

at

http://trac.sagemath.org/sage_trac/ticket/4612

Specifically:

[quote]
Replying to robertwb:

Integer.is_perfect_power is a direct call to mpz_perfect_power_p.
Looks like a bug in gmp to me. That's really bad.

sage: len([a for a in srange(100) if not (-a^3).is_perfect_power
()])
24

Experiment shows that it gives the wrong answer for -a^3 whenever a is
not square-free.
[end quote]

Cheers,

Michael

[ja...@njkfrudils.plus.com]

on gmp-4.2.4 on K8-linux with attached gives the error


> Cheers,
>
> Michael
>

[Bill Hart]

Or indeed by:

#include <stdio.h>
#include "gmp.h"

int main(void)
{
mpz_t a;
mpz_init_set_si(a,-64);

printf("%d\n", mpz_perfect_power_p(a));

return 0;
}

The first bug is the following line of code:

if (n2 != 0 && (n2 & 1) == 0 && usize < 0)
return 0; /* 2 has even multiplicity with negative U */

But it is not the only bug.

Bill.

2008/12/23 <ja...@njkfrudils.plus.com>:

[ja...@njkfrudils.plus.com]

On Tuesday 23 December 2008 00:48:38 Bill Hart wrote:
> Or indeed by:
>
> #include <stdio.h>
> #include "gmp.h"
>
> int main(void)
> {
> mpz_t a;
> mpz_init_set_si(a,-64);
>
> printf("%d\n", mpz_perfect_power_p(a));
>
> return 0;
> }
>
> The first bug is the following line of code:
>
> if (n2 != 0 && (n2 & 1) == 0 && usize < 0)
> return 0; /* 2 has even multiplicity with negative U */
>
> But it is not the only bug.

yeah , if you comment out line , you get an error later , some thing else
later relies on n2 not having 2 with even multiplicity... argh

or slightly better
if (n2>1 && POW2_P(n2) && usize<0) return 0;

[Bill Hart]

Yeah the next bug is:

if ((n & 1) == 0 && usize < 0)
{
TMP_FREE;
return 0; /* even multiplicity with negative U, reject */
}

But one needs to gcd the first n2 with the subsequent ones as well. At
some point one needs to check that we don't have a negative value and
an overall power which is itself a power of 2.

[ja...@njkfrudils.plus.com]

On Tuesday 23 December 2008 01:11:49 Bill Hart wrote:
> Yeah the next bug is:
>
> if ((n & 1) == 0 && usize < 0)
> {
> TMP_FREE;
> return 0; /* even multiplicity with negative U, reject */
> }
>
> But one needs to gcd the first n2 with the subsequent ones as well. At
> some point one needs to check that we don't have a negative value and
> an overall power which is itself a power of 2.

License wise , can mpir use Torbjörn's gmp fix ?

[mabshoff]

On Dec 22, 5:50 pm, ja...@njkfrudils.plus.com wrote:
> On Tuesday 23 December 2008 01:11:49 Bill Hart wrote:
>
> > Yeah the next bug is:
>
> > if ((n & 1) == 0 && usize < 0)
> > {
> >    TMP_FREE;
> >    return 0;               /* even multiplicity with negative U, reject */
> > }
>
> > But one needs to gcd the first n2 with the subsequent ones as well. At
> > some point one needs to check that we don't have a negative value and
> > an overall power which is itself a power of 2.
>
> License wise , can mpir use Torbjörn's gmp fix ?

If it were LGPL V2+ compatible: yes

IANAL: But that is generally not the case, so I would not recommend to
even look at it.

Cheers,

Michael

[Bill Hart]

I don't see a fix on the gmp-discuss list.

Besides that it is trivial to fix. I'll fix it before we release if no
one else does.

This may be a good opportunity to start thinking about an efficient
perfect power detection algorithm. One can do better. Detecting
perfect powers can be done in essentially linear time.

Bill.

2008/12/23 mabshoff <Michael...@mathematik.uni-dortmund.de>:

[Bill Hart]

I think the gcd code in that function can also be improved substantially.

Bill.

2008/12/23 Bill Hart <goodwi...@googlemail.com>:

[ja...@njkfrudils.plus.com]

On Tuesday 23 December 2008 02:03:25 Bill Hart wrote:
> I don't see a fix on the gmp-discuss list.
>

Bet there be one tommorow from Torbjörn

> Besides that it is trivial to fix. I'll fix it before we release if no
> one else does.
>
> This may be a good opportunity to start thinking about an efficient
> perfect power detection algorithm. One can do better. Detecting
> perfect powers can be done in essentially linear time.
>

Bernsteins paper. I did some work on it a few years ago , I can't remember how
far I got , I certainly did 2-adic n'th-roots and n'th roots at least (much
much faster than gmp), dont remember if i joined them into perfect-power
detection , may be able to find my old code even.

[David Harvey]

On Dec 22, 2008, at 9:35 PM, ja...@njkfrudils.plus.com wrote:

> On Tuesday 23 December 2008 02:03:25 Bill Hart wrote:
>> I don't see a fix on the gmp-discuss list.
>>
>
> Bet there be one tommorow from Torbjörn

I have reported it to gmp-bugs, but it has not passed through
moderation yet.

david

[mabshoff]

On Dec 22, 6:50 pm, David Harvey <dmhar...@cims.nyu.edu> wrote:
> On Dec 22, 2008, at 9:35 PM, ja...@njkfrudils.plus.com wrote:

Hi David,

> > On Tuesday 23 December 2008 02:03:25 Bill Hart wrote:
> >> I don't see a fix on the gmp-discuss list.
>
> > Bet there be one tommorow from Torbjörn
>
> I have reported it to gmp-bugs, but it has not passed through  
> moderation yet.

I did see that email and Torbjörn's reply a while ago, so your mail
que must be backed up.

> david

Cheers,

Michael

[ja...@njkfrudils.plus.com]

On Tuesday 23 December 2008 02:03:25 Bill Hart wrote:

> I don't see a fix on the gmp-discuss list.
>
> Besides that it is trivial to fix. I'll fix it before we release if no
> one else does.
>
> This may be a good opportunity to start thinking about an efficient
> perfect power detection algorithm. One can do better. Detecting
> perfect powers can be done in essentially linear time.
>
> Bill.

I couldn't find my 2-adic n-th root , but I found the real n-th root part of
it. Theres some bit rot , have to have a read of the paper again , see what
it's all about.