0

I need to write an example of the Diffie Hellman algorithm, but because the numbers are big and overflow can happen, I need to use Modular Exponentiation in my algorithm. I tried to understand the Modular Exponentiation, but I'm not good at math. So here, I need your help to rewrite my code again in Modular Exponentiation shape.

The code and typical solution:

g = 2
p = 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919

a = 1101001010019203192312312312435234234131235457686756554434232325365645342323243
b = 2343423432473984729384792837492837498273984739847982

A = (g ** a) % p ** 10 % 541

s = A ** b % 541

print(s)
Sina
  • 55
  • 1
  • 8
  • Maybe consider a using the GMP C libraries for python, like the [gmpy2](https://pypi.org/project/gmpy2/) module. – Brett Hale Sep 27 '20 at 15:11
  • 1
    Use the built-in [`pow`](https://docs.python.org/3/library/functions.html#pow) function: it already does modular exponentiation for you. (Replace `g ** a % p` with `pow(g, a, p)`.) There's no need for gmpy2; Python can handle this just fine. – Mark Dickinson Sep 28 '20 at 15:34
  • There are many other questions out there that ask about this; here's one: https://stackoverflow.com/q/14133806/270986 – Mark Dickinson Sep 28 '20 at 15:59
  • @MarkDickinson: Thank You, Man. Your Answer Was Helpful. – Sina Oct 07 '20 at 07:31

0 Answers0