Different ways for modular exponentiation $A^E$ with negative A's I was looking at a way for modular exponentiation $X=A^e \mod{n}$ with negative base $A$ in order to evaluate how it needs to be changed so I can use it with my hardware acceleration unit.

The crypto library I was looking at deals with negative base $A$ (MPI) as follows:


Check if A was negative and if it was, remember that it was negative and invert its sign (e.g. -5 --> 5)
Perform the actual modular exponentiation using a specific algorithm (e.g. sliding window method) with the positively signed $A$
If $A$ was positive at the beginning, you're done 
If $A$ was negative at the beginning and the exponent $e$ was odd compensate by performing $ X = n-X$


This library can work with arbitrarily large (or small) values of $A$. However my crypto core which accelerates moudular exponentiation expects the input parameters $e$ and $A \in [0 \dots n-1]$ which is why I came up with following solution:


At the beginning always perform $A = A \mod{n}$. This would reduce $A$ if $A \ge n$. In case $A \lt 0$ this would make $A$'s sign positive.
Perform the actual modular exponentiation using a specific algorithm (e.g. sliding window method) with the positively signed $A$


I think that performing the reduction at the beginning to reduce A and make its sign positive should not change the final result as $A^e \mod{n} = (A \mod{n})^e \mod{n}$. However I wanted to make sure, that I did not forget anything.
For any integer $A$ we have the congruence $A \equiv A + kn \text{ mod } n$ for all integers k. This means a generic algorithm to get $A$ (where $A &lt; 0$) into the range $[0, n)$ would be something like:

function(A):
    while(A &lt; 0):
        A = A + n
    return A


Doing A = A % n will work in some languages as well (e.g. python) but not all languages (e.g. C).