Ticket #4296 (new defect)

Opened 3 months ago

Last modified 1 week ago

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

Reported by: zimmerma Assigned to: somebody
Priority: critical Milestone: sage-3.4
Component: basic arithmetic Keywords:
Cc:

Description (Last modified by malb) 

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 f2 mod h.

Attachments

trac_4296.patch (0.9 kB) - added by AlexGhitza on 12/28/2008 07:59:29 AM.

Change History

10/15/2008 09:22:29 AM changed by malb

  • description changed.

12/28/2008 04:27:29 AM changed by AlexGhitza

This works for me in sage-3.2.2.

12/28/2008 07:40:41 AM changed by 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

12/28/2008 07:59:10 AM changed by AlexGhitza

  • summary changed from univariate polynomial power ignores 2nd argument to [with patch, needs review] univariate polynomial power ignores 2nd argument.

OK, a patch with the doctest is attached.

12/28/2008 07:59:29 AM changed by AlexGhitza

  • attachment trac_4296.patch added.

(follow-up: ↓ 6 ) 12/29/2008 12:20:59 PM changed by robertwb

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

(in reply to: ↑ 5 ) 12/29/2008 12:25:32 PM changed by 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

(follow-up: ↓ 8 ) 12/29/2008 01:02:06 PM changed by 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 (ab) in full, then divides by the modulus taking the remainder. This is fine for small exponents, but for anything large is wasteful.

(in reply to: ↑ 7 ) 12/29/2008 01:45:58 PM changed by 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