Modular Exponentiation


Modular exponentiation is a fundamental operation in number theory and cryptography. It involves calculating the remainder when an integer, raised to a positive integer power, is divided by another positive integer, known as the modulus.

Mathematically, if we have three integers $a$, $b$, and $m$, where $a$ is the base, $b$ is the exponent, and $m$ is the modulus, then modular exponentiation computes:

$$a^b \pmod{m}$$

The straightforward approach to calculate this involves computing $a^b$ first and the finding the modulo $m$, which can become impractical for large numbers. However, by exploiting modular arithmetic properties, we can perform the calculation more efficiently.

One common algorithm for modular exponentiation is the binary exponentiation method, also known as exponentiation by squaring. This algorithm reduces the number of multiplications required to compute the result.

Here's how the binary exponentiation algorithm works:
  • Start with the result $r$ initialized to 1.
  • Iterate through the binary representation of the exponent $b$ from right to left.
  • At each step, square the base $a$ modulo $m$ (i.e., $a^2 \pmod{ m}$).
  • If the current bit of $b$ is 1, multiply the current result $r$ by $a \pmod{m}$.
  • Continue this process until all bits of $b$ are processed.
  • The final result $r$ is the modular exponentiation of $a^b \pmod{m}$.

Example:

lets compute $5^{13} \pmod{7}$

$13=1101 $ in binary

So we start from LSB and compute powers of 5.

$5^8.5^4.5^2.5^1=4.2.4.5$

wherever the bit is 1 we multiply the result to $r$ So $r= 4.2.5=40 \equiv 5 \pmod{7}$

Python code

def square_and_multiply(base, exponent, modulus):
    result = 1
    base = base % modulus
while exponent > 0:

    # If current bit is 1, multiply result by base modulo modulus
    if exponent % 2 == 1:
        result = (result * base) % modulus
print(exponent,":",base,":",result)
# Square the base modulo modulus
base = (base * base) % modulus
# Divide the exponent by 2 (right shift)
exponent = exponent >> 1
return result

result = square_and_multiply(5, 13, 7)
print("Result of 5^13 mod 7 =", result)

print("using the pow function=",pow(5,13,7))

13 : 5 : 5
6 : 4 : 5
3 : 2 : 3
1 : 4 : 5
Result of 5^13 mod 7 = 5
using the pow function=5

Comments

Post a Comment

Popular posts from this blog

Number Theory CST 292 KTU IV Semester Honors Course Notes Dr Binu V P 9847390760

About me Syllabus Scheme Teaching Plan Model Question Paper University Question Papers Assignment-1 Module-1  Introduction Well ordering principle Group Ring Fields Group Ring Fields in detail Divisibility Modular Arithmetic GCD- Euclidean Algorithm Bezout's Identity Extended Euclidean Algorithm LCM-Least Common Multiple Linear Diophantine Equations Modular Division Module-II Prime Numbers and Prime-Power Factorisation Fermat and Mersenne Prime Primality Testing and Factorization Miller Rabin Primality Testing Algorithm Fermat  Factorization Congruence Modular Exponentiation Linear Congruences Simultaneous Linear Congruences- Chinese Remainder Theorem Fermat's Little Theorem and Euler's Theorem Wilson's Theorem Module-III Congruence with Prime modulus Congruence with Prime power modulus Pseudoprime and Carmichael Numbers Euler's Totient Function Cryptography The Group of Units - Primitive Roots Module-IV Quadratic Residues-Legendre and Jacobi Symbols Arithmetic Func
Read more

Sum of Squares

Image
In this our aim is to determine which integers can be expressed as the sum of given number of squares ie; which have the form $x_1^2+x_2^2+\cdots+x_k^2$, where each $x_i \in \mathbb{Z}$, for a given $k$. Definition: For each integer $k \ge 1$, let $S_k=\{n|n=x_1^2+x_2^2+\cdots+x_k^2$ for some $x_1,x_2,\ldots,x_k \in \mathbb{Z} \}$ , the set of all sum of $k$ squares. Example: $S_1=\{0,1,4,9,\ldots\}$ is the set of all squares. By inspection $S_2$, the set of sum of two squares contains 0,1,2,4,5 and 8 but not 3,6, or 7. Lemma: The set $S_2$ contains, the sum of two squares is closed under multiplication ie; if $s,t \in S_2$ , then $st \in S_2$. Proof:Let $s=a_1^2+b_1^2$ and $t=a_2^2+b_2^2$ be the elements of $S_2$, where $a_1,b_1,a_2,b_2 \in \mathbb{Z}$. Then the identity $$(a_1^2+b_1^2)(a_2^2+b_2^2)=(a_1a_2-b_1b_2)^2+(a_1b_2+b_1a_2)^2$$ This shows that $st \in S_2$ Example: We have $8=2^2+2^2$ and $10=3^2+1^2$ so $8.10=80=(2.3-2.1)^2+(2.1+2.3)^2=4^2+8^2$ Note: an equivalent ident
Read more

Quadratic Residues-Legendre and Jacobi Symbols

Image
Quadratic Congruence   There is a general question whether an integer $a$ has a square root $\pmod{n}$ and if so, how many are there and how one can find them. We know that the solution of the quadratic equation can be found by  $$x=\frac{-b \pm \sqrt{b^2-4ac}}{2a}$$ If we want to apply this to the case where $a,b,c \in Z_n$, then $2a$ to be unit in $\pmod{n}$, so that we can divide by $2a$. We can write the equation in the form $$(2ax+b)^2=b^2-4ac$$ If we can find all the square roots $s$ of $b^2-4ac$ in $\mathbb{Z}_n$, we can then find all the solutions $x \in \mathbb{Z}_n$ of the quadratic equation of the form $2ax+b=s$, or equivalently $x=(s-b)/2a$. If we look at the square roots at $\mathbb{Z}_{15}$, then  1 and 4 have four square roots each($\pm 1 ,\pm 4$ and $\pm 2,\pm 7$ respectively, while the other units have none. Example: Find all the solutions of $x^2-3x+2 \equiv 0 \pmod{15}$ given $a=1, b=−3$ and $c=2,$ we have: $b^2−4ac=(−3)^2−4(1)(2)=9−8=1$ So, $b^2−4ac=1.$ Now, we ne
Read more