Opened 12 years ago

Closed 12 years ago

#4850 closed defect (fixed)

[with patch; positive review] bug in power_mod

Reported by: was Owned by: somebody
Priority: major Milestone: sage-3.3
Component: basic arithmetic Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

----------------------------------------------------------------------
| SAGE Version 3.1.4, Release Date: 2008-10-16                       |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------

sage: power_mod(11,1,7)
11
sage: mod(11^1,7)
4
sage: # Hmmm...???
sage:

...al

Note above that power_mod(11,1,7) should return 4. The fix is to look at the *pure python* code that defines power_mod in rings/arith.py and:

  1. change it to use some much more intelligent compiled code, i.e., either the powermod or powermod_ui methods when the first input coerces to ZZ, and
  1. when a doesn't coerce to ZZ, just revert to the existing Python code, but make sure to throw in an %m somewhere before returning the answer.
  1. Add a doctest like this that illustrates non-integer input for the first argument to power_mod:
    sage: power_mod(3*x, 10, 7)
    4*x^10
    
  1. There is an inconsistency in that the Integer method for power_mod is called "powermod" instead of "power_mod". I think the Integer method should be changed, for consistency with the naming conventions used throughout sage (namely, be generous with underscores).

Attachments (1)

trac_4850.patch (1.1 KB) - added by was 12 years ago.

Download all attachments as: .zip

Change History (6)

comment:1 Changed 12 years ago by burcin

I suggest we remove the power_mod function completely, since python already supports this.

sage: pow?
Type:           builtin_function_or_method
Base Class:     <type 'builtin_function_or_method'>
String Form:    <built-in function pow>
Namespace:      Python builtin
Docstring:
    pow(x, y[, z]) -> number
    
    With two arguments, equivalent to x**y.  With three arguments,
    equivalent to (x**y) % z, but may be more efficient (e.g. for longs).
Class Docstring:
    <attribute '__doc__' of 'builtin_function_or_method' objects>

This would call the __pow__ method of the function in question with the right arguments, so we can handle the modulo powering operation in the right place. Recall that the signature of the __pow__ method is actually:

__pow__(self, other[, modulus]).

So the objective of this ticket should be changed to:

  • let sage.structure.element.generic_power_c handle modulus arguments
  • change the __pow__ methods in sage.structure.element to accept and pass on the third argument
  • deprecate sage.rings.arith.power_mod
  • deprecate Integer.powermod

Thoughts?

comment:2 Changed 12 years ago by mabshoff

  • Milestone changed from sage-3.2.3 to sage-3.4

Changed 12 years ago by was

comment:3 Changed 12 years ago by was

  • Milestone changed from sage-3.4.1 to sage-3.3
  • Summary changed from bug in power_mod to [with patch; needs review] bug in power_mod

This is a humble patch that solves the problem of the ticket. I'm not addressing burcin's far more difficult enhancement of introducing a whole arithmetic architecture. I'm also not addressing the powermod versus power_mod, since I don't want to break existing code by third party people.

comment:4 Changed 12 years ago by burcin

  • Summary changed from [with patch; needs review] bug in power_mod to [with patch; positive review] bug in power_mod

Given patch fixes the reported problem, and it's really simple.

I will open a sage-wishlist issue for removing power_mod.

comment:5 Changed 12 years ago by mabshoff

  • Resolution set to fixed
  • Status changed from new to closed

Merged in Sage 3.3.alpha2

Note: See TracTickets for help on using tickets.