If precision 1 is aupported, the following results should not be NaN:

Python 2.7a0 (trunk:74738, Sep 10 2009, 11:50:08) 
[GCC 4.3.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from decimal import *
>>> setcontext(Context(prec=1, rounding=ROUND_UP,
Emin=-999999999999999999, Emax=999999999999999999, capitals=1, flags=[],
traps=[]))
>>> pow(Decimal(0), Decimal(3), Decimal(70))
Decimal('NaN')
>>> pow(Decimal(3), Decimal(0), Decimal(70))
Decimal('NaN')
>>>

This behaviour was deliberate:  since the standard doesn't cover three-
argument pow, I more-or-less made up my own rules here.  :)

In this case, I (somewhat arbitrarily) decided that to ensure that any 
possible pow(a, b, m) result could be represented, m should be strictly 
less than 10**current_precision.  In general, you'd expect to make lots
of pow(a, b, m) calls with the same m and differing a and b;  it seems 
less error-prone to have them all these calls fail/pass together than 
have those with small results pass, and those with larger results fail.

Not that I expect there's a single person on this planet who's using 
three-argument pow with the Decimal type.  :)

Looking back at this, I'm not quite sure why I chose 'strictly less 
than' rather than 'less than or equal to'.

Unless anyone else disagrees, I'm going to call this a 'won't fix':  I'm 
happy with the current behaviour.  I would like to relax the condition on 
the modulus from 'modulus < 10**prec' to 'modulus <= 10**prec', though, so 
I'm leaving the issue open for that.

Here's a patch.

I don't think early abortion based on m and the current precision is a
good idea. Then we have the situation that this works (prec=4):

(Decimal(7) ** 2) % 100000

But this does not:

pow(Decimal(7), 2, 100000)

Shrug.  That doesn't really bother me.  x**y%z and pow(x, y, z) aren't 
going to match anyway, as soon as x**y has to be rounded.

What would bother me more is the idea of having, with precision 4:

pow(3, 22, 12347) -> nan
pow(3, 23, 12347) -> 7820
pow(3, 24, 12347) -> nan
pow(3, 25, 12347) -> 8645
pow(3, 26, 12347) -> 1241
etc.

(or a similar phenomenon with the 1st argument varying and 2nd and 3rd 
arguments fixed).  Or something that called pow(x, 3, 100003) with 
precision 5, and worked for all but 3 possible values of x.  That sort 
of thing is the cause of hidden bugs.

It's all academic really;  no-one's going to use Decimal's 3-argument 
pow.  I'm not really sure why it's supported at all.  Come to that, I 
don't really understand why Python's 3-argument pow belongs in the core 
interpreter (as opposed to somewhere in the standard library).  If it 
hadn't been there, and if __pow__ didn't accept a third argument, I 
suspect no-one would have tried to implement 3-argument pow for Decimal.

This whole thing is indeed a matter of taste, so I'd close the bug if no
one else is interested.

I would like to look at this for a bit before it gets closed.

Raymond, can I recommend deprecating and eventually removing three-
argument pow support from Decimal?

Deprecate on the grounds that it is slow in decimal.py or the
InvalidOperation issue?

I think pure integer arithmetic with the decimal type always requires
attention from the user, since in many functions one has to check for
Rounded/Inexact in order to get meaningful results. Here one has to
check for InvalidOperation, so I don't think it's a big deal. (This is
also the reason that I don't find the inconsistencies that you listed
particularly bothersome.)

If slowness is the reason: If any C module makes it into Python, this
would not be an issue any longer.

I was suggesting that it be deprecated on the grounds that:

(1) It's not part of the Decimal standard.
(2) It's not implemented for Python (binary) floats, so why implement
    it for decimal floats?
(3) It's severely use-case challenged.

It's a pure integer-based number-theoretic function that has no place in 
the Decimal module.

(1) is clearly true. I wonder about (2) and (3):

The decimal data type is specified to be usable for integer arithmetic.
With a high precision (and traps for Rounded/Inexact) I think it's
reasonably convenient to use.

This is a very loosely related issue, but I think it fits in here.
To be consistent with the documentation, the three argument power
should use the ideal exponent:

>>> c = getcontext()
>>> c.prec = 400
>>> Decimal('1E400') % Decimal('1123123E5')
Decimal('8.45074E+10')
>>> pow(Decimal('1E400'), 1, (Decimal('1123123E5')))
Decimal('84507400000')

The ideal exponent for three-argument pow should definitely be zero.  You're returning what's essentially an integer, loosely disguised as a decimal instance.

I've fixed the docs to accurately describe three-argument pow results (the exponent in particular) in r78312 through r78315.

I've tried to pinpoint exactly what I don't like about the current
behavior, and the main reason is that it violates my mental model
of how the functions in the specification generally behave:

1) Functions take arbitrary precision input.

2) Functions try to preserve as much of the exponent
   information of the input as possible.


With these in mind, it's easy to specify powmod() as:

(a ** b) % c, calculated with unlimited precision. Raises if
the final result does not fit in the current precision.


It is not totally clear to me why the result should have exponent 0
because it is an integer. Decimal("1E3").to_integral() also preserves
the exponent information.

Well, the real problem is that powmod doesn't really belong in the decimal module at all.  It's not a natural primitive arithmetic operation; it's certainly not naturally a floating-point operation; nothing like this appears in any floating-point standard that I'm aware of; and its (few) use cases are very different from typical decimal use cases.  I'd like to bet that it currently has precisely 0 users.  Trying to shoehorn powmod into the decimal module and make its semantics fit with the rest of the module seems a little pointless to me.

Really, what's the point of making any sort of attempt to preserve exponents in 3-argument pow?  Having the result exponent be 0 is clean, simple to understand, simple to implement (which your proposal is not), and matches the use-cases.  The restriction on the modulus also matches the use-cases:  typically, the modulus m is fixed, and you won't have any expectations about the output of powmod(a, b, m) except that you'll know the result is an integer in the range 0 <= x < m.  Having powmod reject m's for which only part of this range is representable avoids hard-to-find bugs where powmod(a, b, m) works for most values of a but then unexpectedly fails for some particular value of a because the result is just larger than can be represented.

+1 for deprecating three-arg pow for the reasons given.
A user is much better-off composing well-defined operations
than using our short-cut, with our chosen assumptions.
Apologies for taking so long to think this one through.

Closing as won't fix.  Even deprecation doesn't seem worth the effort here.