Modular Multiplication

Modular multiplication involves multiplying two numbers and then taking the remainder when the result is divided by the modulus.

The formula for modular multiplication of two numbers \(a\) and \(b\) with modulus \(m\) is:

\[ (a \times b) \mod m \]

Steps:

1. Multiply the numbers \(a\) and \(b\).

2. Apply the modulus \(m\) to find the remainder.

Functions

Show code cell source Hide code cell source

import sympy as sp
from sympy import *
from math import gcd
import random

def modular_multiplication(a, b, modulus):
    result = (a * b) % modulus
    print(f"{a} * {b} ≡ {result} (mod {modulus})")
    return result

Examples

Find \((23 \times 7)~mod~26\)

a = 23
b = 7
modulus = 26

result = modular_multiplication(a, b, modulus)

23 * 7 ≡ 5 (mod 26)

Explanation

To find the result of ( 23 \times 7 ) modulo ( 26 ), follow these steps:

1. Perform the multiplication:

\[ 23 \times 7 = 161 \]

2. Find the remainder when divided by the modulus:

Now, calculate the remainder when ( 161 ) is divided by ( 26 ):

\[ 161 \div 26 = 6 \text{ remainder } 5 \]

3. Express the division:

\[ 161 = 26 \times 6 + 5 \]

4. The remainder is the result of the modulo operation:

\[ 161 \mod 26 = 5 \]

Therefore:

\[ 23 \times 7 \equiv 5 \mod 26 \]

Finding \((182 \times 39)~mod~8\)

a = 182
b = 39
modulus = 8

result = modular_multiplication(a, b, modulus)

Explanation

To find the result of ( 182 \times 39 ) modulo ( 8 ), follow these steps:

1. Perform the multiplication:

\[ 182 \times 39 = 7104 \]

2. Find the remainder when divided by the modulus:

Now, calculate the remainder when ( 7104 ) is divided by ( 8 ):

\[ 7104 \div 8 = 888 \text{ remainder } 0 \]

3. Express the division:

\[ 7104 = 8 \times 888 + 0 \]

4. The remainder is the result of the modulo operation:

\[ 7104 \mod 8 = 0 \]

Therefore:

\[ 182 \times 39 \equiv 0 \mod 8 \]

Finding \((123 \times 291)~mod~39\)

a = 123
b = 291
modulus = 39

result = modular_multiplication(a, b, modulus)

123 * 291 ≡ 30 (mod 39)

Explanation

To find the result of ( 123 \times 291 ) modulo ( 39 ), follow these steps:

1. Perform the multiplication:

\[ 123 \times 291 = 35853 \]

2. Find the remainder when divided by the modulus:

Now, calculate the remainder when ( 35853 ) is divided by ( 39 ):

\[ 35853 \div 39 = 919 \text{ remainder } 32 \]

3. Express the division:

\[ 35853 = 39 \times 919 + 32 \]

4. The remainder is the result of the modulo operation:

\[ 35853 \mod 39 = 32 \]

Therefore:

\[ 123 \times 291 \equiv 32 \mod 39 \]