0
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ $x$ and $y$ are actually already less than $p$. Calculation of $a^{41}$ requires $7$ multiplications, since squaring counts as a multiplication. $\endgroup$ – Joffan Mar 17 '17 at 3:19
  • $\begingroup$ @Joffan. Thanks for pointing out the missing info. $\endgroup$ – P Vanchinathan Mar 17 '17 at 3:27
  • 1
    $\begingroup$ Also I'd say the very first thing to do is check whether $p$ is prime. :-) (It is) $\endgroup$ – Joffan Mar 17 '17 at 3:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.