0

Inverse modulo can be solved easily by Euclidean algorithm but 3 to the power minus 13 mod 2 can not be easy, I appreciate if anybody can give a solution.

For example: $3^{-13} \bmod 2 = ?$

Biswas
  • 1
  • 1
    Welcome to Cryptography. Did you take a basic number theory? $3^{-13} = (3^{-1})^{13}$, $3 = 1 \bmod 2$.. – kelalaka Aug 05 '19 at 19:18

1 Answers1

2

but 3 to the power minus 13 mod 2 can not be easy

But it is. That's because if you put "mod 2" at the end, you're working in the finite field $\mathbb F_2$ (this is a field for all primes). In this field all basic rules of arithmetic that you know from the real, complex and the rational numbers still apply.

In particular $$3^{-13}=\left(3^{-1}\right)^{13}=\left(3^{13}\right)^{-1}$$. As $3\equiv 1\pmod 2$ the above simplifies to $1^{-13}\equiv 1\pmod 2$.

SEJPM
  • 424