# Modular Arithmetic with large exponents

I have to return $a^x b^y(mod p)$

However I'm having difficulty doing this with such large numbers.

I know I can change the format to $a b (mod p)^n$ and I will get a number however I'm just not sure how to work with different exponents, and numbers so large, and still get the correct answer.

$a = 1531201089928563$
$b = 5232015514746838$
$p = 36591670045183523$

$x = 31146826187279844$
$y = 1747419798738$

It is in computer programming. I'm just unsure of how to structure the formula correctly and would like some guidance.

• Unless it is an exercise in computer programming you should not be doing this. – P Vanchinathan Mar 17 '17 at 2:33
• It is in computer programming, I'm just unsure of how to structure the formula correctly. – Kenjii Mar 17 '17 at 2:36
• Do you have the tools to find $ab \bmod p$? $a^2 \bmod p$? – Joffan Mar 17 '17 at 3:20
• Do you have data types large enough to store $p^2$ without overflowing? – Mike Mar 17 '17 at 6:01

First reduction: ensure $x,y$ are replaced by something less than $p$. This is by Fermat's theorem which states that $a^x=a^r\pmod p$ where $r$ is the remainder from $x$ when divided by $p-1$.
Next use the iterated squaring method: I'll sketch this. Normally to calculate $a^{41}$ one needs 40 multiplications. Iterated squaring exploits the binary representation, $41=32+8+1$. So $a^{41}= a^{32}\times a^8 \times a^1$. This requires 2 multiplications, to calculates $a^{32}$ repeatedly square $a$, and on the way you would also have computed $a^8$. (All this holds for mudular exponentiation. At every stage you can calculates the result mod p.
• $x$ and $y$ are actually already less than $p$. Calculation of $a^{41}$ requires $7$ multiplications, since squaring counts as a multiplication. – Joffan Mar 17 '17 at 3:19
• Also I'd say the very first thing to do is check whether $p$ is prime. :-) (It is) – Joffan Mar 17 '17 at 3:29