# 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.

• Yea, i edited it to $X= n - X$, which is what the crypto library is doing. – TrinityTonic Jun 29 '17 at 6:30
• If the library is doing $X = n - x$, then it's broken (or you're looking at the modular multiplication routine, not the modular exponentiation). As written, they'd have $X^{-1} = n - X$, which is wrong, as we know $X \cdot X^{-1} = X^0 = 1$, and $X \cdot (n - X)$ is not 1 in general. What they'd need to do at this set is known as a 'modular inverse', that's certainly doable, but is considerably more complex that $X = n-x$. – poncho Aug 28 '17 at 22:57

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 < 0$) into the range $[0, n)$ would be something like:

function(A):
while(A < 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).

Here is a way to see that the library performs correctly. Assume $A$ (seen as an integer) be negative. Define $B = (-A)^e \bmod n$. Then: \begin{align*} A^e \bmod n &= [(-1)*(-A)]^e \bmod n\\ &= (-1)^e (-A)^e \bmod n\\ &= (-1)^e B \bmod n\\ &=\begin{cases} B \bmod n = B&\text{if $e$ is even}\\ -B \bmod n = n - B & \text{if $e$ is odd}\end{cases} \end{align*}

Note that the result remains correct if $-A$ is replaced with $-A \bmod n$ since $(-A)^e \bmod n = (-A \bmod n)^e \bmod n$.