Modular exponentiation by hand ($a^b\bmod c$)

How do I successfully calculate $a^b\bmod c$ :

  • When $b$ is massive, as an example $5^{844325}\bmod 21$ ?
  • When $b$ is much less than $c$ yet it would certainly still be a great deal of job to increase $a$ on its own $b$ times, as an example $5^{69}\bmod 101$ ?
  • When $(a,c)\ne1$ , as an example $6^{103}\bmod 14$ ?

Exist any kind of various other methods for reviewing backers in modular arithmetic?


This is being asked in an initiative to lower matches, see here and also here.

126
2022-06-29 01:26:52
Source Share
Answers: 4

For the first inquiry: make use of $a^{\Phi(c)}=1 \mod c$, where $\Phi(c)$ is the variety of coprimes to $c$ listed below $c$. For $c=21=7\cdot 3$ we have $\Phi(c)=(7-1)\cdot(3-1)=12$

2nd inquiry: Use $a^4=(a^2)^2, a^8=(a^4)^2$ and more. Decay the backer right into powers of 2 and also incorporate them making use of $a^n\cdot a^m=a^{n+m}$ E.g. $a^{69}=a^{64}\cdot a^4\cdot a^1$.

7
2022-06-29 01:41:44
Source

Let is attempt $5^{844325} \bmod 21$: $$ \begin{align} 5^0 & & & \equiv 1 \\ 5^1 & & &\equiv 5 \\ 5^2 & \equiv 25 & & \equiv 4 \\ 5^3 & \equiv 4\cdot 5 & & \equiv 20 \\ 5^4 & \equiv 20\cdot 5 & & \equiv 16 \\ 5^5 & \equiv 16\cdot 5 & & \equiv 17 \\ 5^6 & \equiv 17\cdot 5 & & \equiv 1 \end{align} $$ So increasing by $5$ 6 times coincides as increasing by $1$. We intend to increase by $5$ a lot of times: $844325$. The amount of times do we increase by $5$ 6 times? The variety of times $6$ enters into $844325$ is $140720$ with a rest of $5$. That rest is what issues. Multiply by $5^6$ specifically $140720$ times which coincides as increasing by $1$ that sometimes. After that increase by $5$ simply $5$ extra times, and also get $17$.

So $5^{844325} \equiv 17 \bmod 21$.

44
2022-06-29 01:40:56
Source

In basic, made even exponentiation is made use of, this is $O(\log(b) \cdot \log(n))$ if reproduction $\bmod n$ is $O(\log (n))$ .

def powmod(a, b, c):
    res = 1
    while b > 0:
        if b % 2 == 1:
            res = res * a % c
        a = a * a % c
        b //= 2
    return res

Try it online

Example for $5^{69}\bmod101$ :

\begin{align} 5^{69} & \equiv 5 \times (5^2)^{34} & \equiv 5 \times 25^{34} \\ & \equiv 5 \times (25^2)^{17} & \equiv 5 \times 19^{17} \\ & \equiv 5 \times 19 \times (19^2)^8 & \equiv 95 \times 58^8 \\ & \equiv 95 \times (58^2)^4 & \equiv 95 \times 31^4 \\ & \equiv 95 \times (31^2)^2 & \equiv 95 \times 52^2 \\ & \equiv 95 \times 78 \\ & \equiv 37 \end{align}


When $b$ is massive (much bigger than $n$ ) you can (effort) to locate the ranking of the ring ( $\varphi(n)$ ) and also locate the rest of $b \pmod {\varphi(n)}$ due to the fact that $a^b \bmod n= a^{b \mod \varphi(n)} \bmod n$ (for $21$ , it is $(3-1) \cdot (7-1)=12$ ) this calls for locating the prime variables of $n$ .

As a whole the ranking for $n = \prod{(p_i)^{k_i-1} \cdot (p_i-1)}$ with $p_i^{k_i}$ the prime variables of $n$ .

13
2022-06-29 01:39:58
Source

Wikipage on modular arithmetic is not bad.

  • When $b$ is huge, and $a$ and $c$ are coprime, Euler's theorem applies: $$ a^b \equiv a^{b \, \bmod \, \phi(c)} \, \bmod c $$ For the example at hand, $\phi(21) = \phi(3) \times \phi(7) = 2 \times 6 = 12$. $$ \Rightarrow 844325 \bmod 12 = 5,\ \text{so}\ 5^5 = 5 \times 25^2 \equiv 5 \times 4^2 = 80 \equiv 17 \mod 21 $$.

  • When $a$ and $c$ are coprime, but $0<b<\phi(c)$, repeated squaring (or using other compositions of powers) is the fastest way to go (manually): $$ \begin{eqnarray} 5^4 \equiv 5 \times 5^3 \equiv 5 \times 24 \equiv 19 &\pmod{101}\\ 19^4 \equiv (19^2)^2 \equiv 58^2 \equiv (-43)^2 \equiv 1849 \equiv 31 &\pmod{101} \\ 31^4 \equiv (31^2)^2 \equiv (961)^2 \equiv 52^2 \equiv 2704 \equiv 78 &\pmod{101} \\ 5^{69} \equiv 5 \times 5^4 \times ((5^4)^4)^4 \equiv 5 \times 19 \times 78 \equiv 5 \times 19 \times (-23)\\ \equiv 19 \times (-14) \equiv -266 \equiv 37 & \pmod{101} \end{eqnarray} $$

  • When $a$ and $c$ are not coprime, let $g = \gcd(a,c)$. Let $a = g \times d$ and $c = g \times f$, then, assuming $b > 1$: $$ a^b \bmod c = g^b \times d^b \bmod (g \times f) = ( g \times (g^{b-1} d^b \bmod f) ) \bmod c $$ In the example given, $\gcd(6,14) = 2$. So $2^{102} \times 3^{103} \mod 7$, using Euler'r theorem, with $\phi(7) = 6$, and $102 \equiv 0 \mod 6$, $2^{102} \times 3^{103} \equiv 3 \mod 7$, so $6^{103} \equiv (2 \times 3) \equiv 6 \mod 14 $.

66
2022-06-29 01:39:48
Source