How does one choose modulus when doing large exponents?

Question

I'm having some trouble understanding how to calculate large exponentials, such as $41^{9182}$. I want to learn the modular exponentiation technique but one thing is not clear to me: How do you choose what modulus $m$ to work in when calculating something this large, or does it matter so long as the $gcd(41,m) = 1$?

I've seen people use $100$ in cases of large numbers and wondering if that is just a standard thing to do or if there is a deeper reasoning behind it. Thanks in advance for the help!

Answer 1

In a comment you reveal that you seek the $\rm\color{#c00}{two}$ least significant digits, so it suffices to compute the integer $\!\bmod 100\,$ since, for example

$$ 54\cdots \color{#c00}{21}\, =\, \overbrace{5\cdot10^5\!+4\cdot10^4\!+\cdots}^{\large \equiv\,\ 0\pmod{\!100}}\, \!+\color{#c00}2\cdot 10+\color{#c00}1\, \equiv\, \color{#c00}{21}\!\!\pmod{\!100}$$

Since the modulus $100 = 4\cdot 25$ we can compute it mod $4$ and mod $25$ and then combine the results by CRT = Chinese Remainder Theorem. Further, if the base shares factors with $100$ then we can factor them out using mod distributivity, often yielding great simplifications, i.e.

note: $ \ ca\bmod cn\:=\: \color{#c00}c\,(a\bmod n)\, =\,$ mod Distributive Law, $ $ so e.g. factoring out $\,\color{#c00}{c=4}\,$ in

$\! \begin{align} 5312^{\large 442}\!\bmod 100\, &=\, \color{#c00}4\,(\color{}{12}^{\large 442}/4\bmod 25)\ \ {\rm by}\,\ 4\mid 12\mid 12^{442} \\ &=\,4\,(\color{}{12}^{\large 2}/\,2^{\large 2}\, \bmod 25)\ \ {\rm by}\,\ 12^{\large 440}\!\equiv (12^{\large\color{#c00}{20}})^{\large 22}\!\equiv 1^{\large 22}\rm \ by\ Euler\ \phi(25)\!=\!\color{#c00}{20}\\ &=\,4\,(6^{\large 2} \bmod 25)\\ &=\, 4\,(11) \end{align}$

Answer 2

It depends on what you want to further do with this value. If you are only interested in $n$ digits in base $b$, you would choose $m=b^n$ (e.g. $10^3$ for the last three digits in decimal system).

In the case of cryptography (like the RSA algorithm) one would use primes or prime products like $m=pq$ ($p,q$ prime), depending on the algorithm.

Answer 3

If you want to compute $41^{9182}$, choosing a modulus has nothing^* to do with the calculation.

When people talk about modular exponentiation because they are specifically talking about things like $41^{9182} \pmod{713}$. If the thing you are specifically interested in is $41^{9182}$, then there isn't much use in knowing anything about $41^{9182} \pmod{713}$ doesn't tell

The "mod 100" examples you refer to are an example of this. A typical problem this applies to is "find the last two digits of the following number". For all intents and purposes, this is the same problem as "find a reduced representative of this number modulo $100$".

So, the question "find the last two digits of $41^{9182}$" is the same question as "find a reduced representative for $41^{9182} \pmod{100}$", which is why they consider modular exponentiation for this problem.

_{*: There are tricks for doing multiplication by using modular arithmetic, but these only apply if your multiplication algorithm involves doing things like writing numbers as values of polynomials and using fast Fourier transforms to multiply polynomials}