2
$\begingroup$

Given is Generator $g = 5$, Multiplicative group $F_{10007}^*$, Private key = 7347.

Then public key is $5^{7347} \bmod 10007$ right?

On a calculator this gives an overflow error, how am I supposed to calculate the public key when a private key is a large number?

$\endgroup$
1
3
$\begingroup$

On a calculator this gives overflow error, how am I supposed to calculate the public key when a private key is a large number?

A standard calculator cannot handle that, and we don't expect it. If you have a programmable one you can use square-and-multiply as in levgeni's answer. This, however, will fail when the calculator cannot handle integers (the modulus) larger than the calculator's word size.

There are better and easy approaches

  1. Use WolframAlpha 5^7347 mod 10007
  2. Use SageMathCell 5^7347 % 10007
  3. Use Python's pow that takes a third parameters as modulus pow(5,7347,10007) and uses modular-square-and-multiply. Online
$\endgroup$
2
  • $\begingroup$ Thanks a lot, I had no idea I could calculate this using Wolfram. $\endgroup$
    – SJ19
    Mar 25 at 17:06
  • 2
    $\begingroup$ Wolfram can do a lot of things online. You can think that they carry their system to online. SageMath, on the other hand, is free and uses Python 3 syntax. It worth learning. Of course, I did not count the other languages. $\endgroup$
    – kelalaka
    Mar 25 at 17:09
2
$\begingroup$

If you are on linux/mac you can also use bc:

echo "(5^7347)%10007" | bc
$\endgroup$
1
  • $\begingroup$ There's no guarantee that any particular implementation of bc won't overflow available memory. $\endgroup$
    – DannyNiu
    Apr 7 at 9:25
1
$\begingroup$

5^{7347} is a huge integer (with thousands bits), if you are using standard integer encoding, you can only use few hundreds bits ($128$, in general).

But, if you are looking the fact that you don't need to compute entirely this integer, you can use the square-and-multiply algorithm smartly :

pow (a,b) : if b is odd then return (a* (pow (a, b-1)) mod 10007)
        elif b == 0 then return 1
        elif return (pow ((a*a) mod 10007, b/2)

By using modulo 10007 at each step, you can be sure that your integers will be never too big.

$\endgroup$

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.