[with patch, with positive review] univariate polynomial power ignores 2nd argument

[zimmerma]

sage: R = PolynomialRing(GF(2), x)
sage: f = R(x^9 + x^7 + x^6 + x^5 + x^4 + x^2 + x)
sage: h = R(x^10 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + 1)
sage: (f^2) % h
x^9 + x^8 + x^7 + x^5 + x^3
sage: pow(f, 2, h)
x^18 + x^14 + x^12 + x^10 + x^8 + x^4 + x^2

We should expect both results to be equal to f² mod h.

[AlexGhitza]

This works for me in sage-3.2.2.

[mabshoff]

Same for me:

----------------------------------------------------------------------
| Sage Version 3.2.2, Release Date: 2008-12-18                       |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
sage: R = PolynomialRing(GF(2), x)
sage: f = R(x^9 + x^7 + x^6 + x^5 + x^4 + x^2 + x)
sage: h = R(x^10 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + 1)
sage: (f^2) % h
x^9 + x^8 + x^7 + x^5 + x^3
sage: pow(f, 2, h)
x^9 + x^8 + x^7 + x^5 + x^3
sage: 

Please add a doctest and once it has been merged we can close this ticket.

Cheers,

Michael

[AlexGhitza]

OK, a patch with the doctest is attached.

[robertwb]

The attached patch seems to be just the doctest, no new code...

[mabshoff]

Replying to robertwb:

The attached patch seems to be just the doctest, no new code...

Yes, because the bug originally reported has been fixed [or so it seems :)].

Cheers,

Michael

[robertwb]

Ah, good point.

I'm not sure how I feel about throwing the symbolic x around all around, though I guess efficiency doesn't matter too much here.

Also, just looking at the code it can be very inefficient--it computes (a^{b) in full, then divides by the modulus taking the remainder. This is fine for small exponents, but for anything large is wasteful.}

[mabshoff]

Replying to robertwb:

Ah, good point.

:)

I'm not sure how I feel about throwing the symbolic x around all around, though I guess efficiency doesn't matter too much here.

Yeah, I would consider it a good idea to get this in as is and open another ticket to make this more efficient.

Also, just looking at the code it can be very inefficient--it computes (a^b) in full, then divides by the modulus taking the remainder. This is fine for small exponents, but for anything large is wasteful.

Cheers,

Michael

[cremona]

I give this a positive review since it is just a doctest showing that something which used to fail now works.

I sympathise with robertwb's concern, but that should be a separate ticket. I looked for, but could not find anywhere, the code which pow(f,2,h) runs.

[mabshoff]

Merged in Sage 3.3.alpha0