Skip to main content

Week - 4

TITLE

Lecture 16:
Modular Inverse​

Modular Inverse in (Zn\mathbb{Z}_n)​

Multiplicative Operation​

  • Defied as: a⋅b≡(a×b) mod n a \cdot b \equiv (a \times b) \bmod n

  • ( a,b∈Zna, b \in \mathbb{Z}_n )

Multiplicative Inverse​

Definition​

  • A element ( b ) is inverse of ( a ) if: a⋅b≡1(modn) a \cdot b \equiv 1 \pmod{n}

Key Condition​

gcd⁡(a,n)=1⟺a−1 exists mod n\gcd(a,n) = 1 \Longleftrightarrow a^{-1} \text{ exists mod } n

✓\checkmark Only coprime elements have inverses

Why Inverse May Not Exist​

Example: ( Z8\mathbb{Z}_8 )​

  • Take ( a = 2 )

2⋅b≡1(mod8)2 \cdot b \equiv 1 \pmod{8}

  • o such ( b ) exists
  • Because: gcd⁡(2,8)≠1 \gcd(2,8) \ne 1

Theorem (Existence of Inverse)​

Statement​

a−1 exists mod n  ⟺  gcd⁡(a,n)=1a^{-1} \text{ exists mod } n \iff \gcd(a,n)=1

Proof Idea​

(⇒) If inverse exists:​

ax≡1(modn)⇒ax−1=y⇒1=ax−y ax \equiv 1 \pmod{n} \\ \Rightarrow ax - 1 = y \\ \Rightarrow 1 = ax - y

✓\checkmark So gcd = 1

(⇐) If gcd = 1:​

1=ax+y⇒ax≡1(mod)1 = ax + y \\ \Rightarrow ax \equiv 1 \pmod{}

✓\checkmark So iverse exists

Special Case: (Zp\mathbb{Z}_p) (p is Prime)​

Set​

Zp={0,1,2,...,p−1}\mathbb{Z}_p = \{0,1,2,...,p-1\}

Define: Zp∗=Zp∖{0}\mathbb{Z}_p^* = \mathbb{Z}_p \setminus \{0\}

Property​

  • For prime ( p ): gcd⁡(a,p)=1∀a≠0 \gcd(a,p)=1 \quad \forall a \ne 0

✓\checkmark Every o-zero element has inverse

Result​

  • ( Zp∗\mathbb{Z}_p^* ) forms:

    • Multiplicative group
    • Cyclic group

Importat Isights​

  • ( Zn\mathbb{Z}_n ) under multiplication:

    • ❌ not always a group

  • ( Zp∗\mathbb{Z}_p^* ) (p prime):

    • ✅ Group
    • ✅ Every element is invertible

Key Takeaways​

  • Modular inverse exists only for coprime elements

  • Prime modulus → guarantees inverses

  • ( Zp∗\mathbb{Z}_p^* ):

    • Finite
    • Cyclic
    • Used in cryptography

Final Conclusion​

  • Modular inverse is core to:

    • RSA
    • Diffie-Hellman
    • ECC

  • Prime fields ( Zp\mathbb{Z}_p ) are heavily used because:

    • Every o-zero element is invertible
TITLE

Lecture 17:
Extended Euclidean Algorithm​

Extended Euclidean Algorithm (EEA)​

Goal​

  • Find: gcd⁡(a,b)=ax+by \gcd(a,b) = ax + by
  • Also compute modular inverse

Key Idea​

If: gcd⁡(a,n)=1\gcd(a,n)=1

The:

ax+y=1⇒ax≡1(modn)ax + y = 1 \Rightarrow ax \equiv 1 \pmod{n}

checkmarkcheckmark So:

x=a−1(modn)x = a^{-1} \pmod{n}

Step 1: Euclidean Algorithm (GCD)​

Example​

Find inverse of 41 mod 54

54=1⋅41+1354 = 1 \cdot 41 + 13 41=3⋅13+241 = 3 \cdot 13 + 2 13=6⋅2+113 = 6 \cdot 2 + 1 2=2⋅1+02 = 2 \cdot 1 + 0

✓\checkmark gcd = 1

Step 2: Back Substitution​

1=13−6⋅21 = 13 - 6 \cdot 2

Substitute:

2=41−3⋅132 = 41 - 3 \cdot 13 1=13−6(41−3⋅13)=19⋅13−6⋅411 = 13 - 6(41 - 3 \cdot 13) = 19 \cdot 13 - 6 \cdot 41

Now substitute:

13=54−4113 = 54 - 41 1=19(54−41)−6⋅41=19⋅54−25⋅411 = 19(54 - 41) - 6 \cdot 41 = 19 \cdot 54 - 25 \cdot 41

Result​

1=54⋅19+41⋅(−25)1 = 54 \cdot 19 + 41 \cdot (-25)

So:

  • ( x = -25 )
  • ( y = 19 )

Modular Inverse​

41−1≡−25≡29(mod54)41^{-1} \equiv -25 \equiv 29 \pmod{54}

✓\checkmark Final Answer:

41−1≡29(mod54)41^{-1} \equiv 29 \pmod{54}

General Algorithm (EEA)​

Input: a, b
Output: gcd, x, y such that ax + by = gcd

r0 = a, r1 = b
x0 = 1, x1 = 0
y0 = 0, y1 = 1

while r1 != 0:
    q = r0 // r1
    r2 = r0 - q*r1
    x2 = x0 - q*x1
    y2 = y0 - q*y1

    r0, r1 = r1, r2
    x0, x1 = x1, x2
    y0, y1 = y1, y2

return r0, x0, y0

Important Insight​

  • If gcd = 1 → inverse exists
  • If gcd ≠ 1 → inverse does not exist

Key Takeaways​

  • EEA gives:

    • gcd
    • coefficients ( x, y )

  • Used to compute:

    • Modular inverse

  • Core for:

    • RSA
    • Cryptographic algorithms

Final Conclusion​

  • Extended Euclidean Algorithm is the standard method to compute modular inverses efficiently
  • Essential tool in modern cryptography
TITLE

Lecture 18:
Fermat's Little Theorem, Euler Phi Function​

Fermat’s Little Theorem​

Statement​

Let ( p ) be a prime and ( a ) be an integer such that ( \gcd(a,p)=1 )

ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}

Key Idea​

  • Work in:

    Zp∗=1,2,...,p−1\mathbb{Z}_p^* = {1,2,...,p-1}

  • Multiply all elements by ( a ):

a,2a,3a,...,(p−1)amod  p{a,2a,3a,...,(p-1)a} \mod p
  • This is just a permutation of: 1,2,...,p−1{1,2,...,p-1}

Proof Sketch​

Multiply all elements:

a⋅2a⋅3a⋯(p−1)a≡1⋅2⋅3⋯(p−1)(modp)a \cdot 2a \cdot 3a \cdots (p-1)a \equiv 1 \cdot 2 \cdot 3 \cdots (p-1) \pmod{p} ap−1(p−1)!≡(p−1)!(modp)a^{p-1}(p-1)! \equiv (p-1)! \pmod{p}

Cancel ((p-1)!):

ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}

Euler’s Totient Function​

Definition​

ϕ(n)=number of integers <n that are coprime to n\phi(n) = \text{number of integers } < n \text{ that are coprime to } n

Examples​

  • If ( p ) is prime:
ϕ(p)=p−1\phi(p) = p - 1

Example​

Z21∗=1,2,4,5,8,10,11,13,16,17,19,20\mathbb{Z}_{21}^* = {1,2,4,5,8,10,11,13,16,17,19,20} ϕ(21)=12\phi(21) = 12

Euler’s Theorem (Generalization)​

If:

gcd⁡(a,n)=1\gcd(a,n)=1

Then:

aϕ(n)≡1(modn)a^{\phi(n)} \equiv 1 \pmod{n}

Multiplicative Property of Totient​

If:

gcd⁡(m,n)=1\gcd(m,n)=1

Then:

ϕ(mn)=ϕ(m)⋅ϕ(n)\phi(mn) = \phi(m)\cdot \phi(n)

Special Case (Prime Powers)​

If:

n=pkn = p^k

Then:

ϕ(pk)=pk−pk−1\phi(p^k) = p^k - p^{k-1}

Example (Fermat)​

Let:

  • ( a = 5 )
  • ( p = 7 )
56≡1(mod7)5^{6} \equiv 1 \pmod{7}

Key Takeaways​

  • Fermat’s theorem:

    • Special case of Euler’s theorem

  • Euler function:

    • Counts coprime integers

  • Used in:

    • Modular exponentiation
    • RSA

Final Conclusion​

  • For prime modulus:

    ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}

  • For general modulus:

    aϕ(n)≡1(modn)a^{\phi(n)} \equiv 1 \pmod{n}

✔ Fundamental results in number theory and cryptography

TITLE

Lecture 19:
Euler's theorem, Quadratic Residue​

Euler’s Theorem​

Statement​

Let (n∈Z n \in \mathbb{Z} ) and (gcd⁡(a,n)=1 \gcd(a,n)=1 )

aϕ(n)≡1(modn)a^{\phi(n)} \equiv 1 \pmod{n}

Proof Idea​

  • Consider reduced residue system:
R=r1,r2,...,rϕ(n)R = {r_1, r_2, ..., r_{\phi(n)}}
  • Multiply each element by ( a ):
aR=ar1,ar2,...,arϕ(n)aR = {ar_1, ar_2, ..., ar_{\phi(n)}}
  • Since ( \gcd(a,n)=1 ), multiplication is a permutation:
aR=RaR = R

Multiply all elements​

∏ri≡∏(ari)(modn)\prod r_i \equiv \prod (a r_i) \pmod{n} ∏ri≡aϕ(n)∏ri(modn)\prod r_i \equiv a^{\phi(n)} \prod r_i \pmod{n}

Cancel:

aϕ(n)≡1(modn)a^{\phi(n)} \equiv 1 \pmod{n}

Quadratic Residue​

Definition​

An integer ( a ) is a quadratic residue mod p if:

∃y such that y2≡a(modp)\exists y \text{ such that } y^2 \equiv a \pmod{p}

Otherwise​

  • ( a ) is quadratic non-residue

Example (p = 11)​

Squares mod 11:

12=1,;22=4,;32=9,;42=5,;52=31^2 = 1,; 2^2 = 4,; 3^2 = 9,; 4^2 = 5,; 5^2 = 3

So:

QR11=1,3,4,5,9QR_{11} = {1,3,4,5,9}
  • Remaining → non-residues

✔ Both sets have equal size

Euler’s Criterion​

Statement​

Let ( p ) be prime and ( a≢0(modp)a \not\equiv 0 \pmod{p} )

ap−12≡{1(modp)if a is QR −1(modp)if a is non-QRa^{\frac{p-1}{2}} \equiv \begin{cases} 1 \pmod{p} & \text{if } a \text{ is QR} \ -1 \pmod{p} & \text{if } a \text{ is non-QR} \end{cases}

Proof Idea​

Part 1 (⇒)​

If:

y2≡a(modp)y^2 \equiv a \pmod{p}

Then:

ap−12=(y2)p−12=yp−1≡1(modp)a^{\frac{p-1}{2}} = (y^2)^{\frac{p-1}{2}} = y^{p-1} \equiv 1 \pmod{p}

(using Fermat)

Part 2 (⇐)​

  • ( Zp∗\mathbb{Z}_p^* ) is cyclic
  • Let generator ( g )
a≡gia \equiv g^i

Then:

  • If ( i = 2k ) (even):
a=g2k=(gk)2a = g^{2k} = (g^k)^2

✔ So ( a ) is QR

Key Takeaways​

  • Euler’s theorem → generalization of Fermat

  • Quadratic residues:

    • Important in cryptography

  • Euler’s criterion:

    • Efficient test for QR

Final Conclusion​

  • Euler’s theorem:

    aϕ(n)≡1(modn)a^{\phi(n)} \equiv 1 \pmod{n}

  • Euler’s criterion:

    ap−12≡±1(modp)a^{\frac{p-1}{2}} \equiv \pm 1 \pmod{p}

✔ Core tools in number theory and cryptography

TITLE

Lecture 20:
Polynomial Arithmetic​

Polynomial Arithmetic (Cryptography Context)​

Definition​

A polynomial of degree ( n ):

f(x)=a0+a1x+a2x2+⋯+anxnf(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n
  • ( a_i ) → coefficients (from a ring/field)
  • ( a_n \ne 0 )

Special Types​

  • Monic Polynomial:

    an=1a_n = 1

  • Constant Polynomial:

    n=0n = 0

Polynomials over Finite Field​

  • Work over:

    Zp=0,1,...,p−1\mathbb{Z}_p = {0,1,...,p-1}

  • Common case:

    F2=0,1\mathbb{F}_2 = {0,1}

Example (Used in AES)​

m(x)=x8+x4+x3+x2+x+1m(x) = x^8 + x^4 + x^3 + x^2 + x + 1
  • Coefficients in ( F2\mathbb{F}_2 )
  • Irreducible polynomial

Polynomial Operations​

Addition​

f(x)+g(x)=∑(ai+bi)xif(x) + g(x) = \sum (a_i + b_i)x^i
  • Done coefficient-wise
  • In ( F2\mathbb{F}_2 ): XOR

Subtraction​

f(x)−g(x)=∑(ai−bi)xif(x) - g(x) = \sum (a_i - b_i)x^i

Multiplication​

f(x)⋅g(x)f(x)\cdot g(x)
  • Normal polynomial multiplication
  • Reduce coefficients mod ( p )

Division​

f(x)=q(x)m(x)+r(x)f(x) = q(x)m(x) + r(x)
  • ( deg⁡(r)<deg⁡(m)\deg(r) < \deg(m) )

Finite Field using Polynomials​

Construction​

  • Take:

    Z2[x]\mathbb{Z}_2[x]

  • Modulo irreducible polynomial ( m(x)m(x) ):

Z2[x]/m(x)\mathbb{Z}_2[x] / m(x)

Resulting Set​

b0+b1x+⋯+b7x7,bi∈0,1{b_0 + b_1 x + \cdots + b_7 x^7}, \quad b_i \in {0,1}

Field Size​

∣GF(28)∣=28=256|\text{GF}(2^8)| = 2^8 = 256

Galois Field (Finite Field)​

  • Denoted as:
GF(2n)\text{GF}(2^n)

  • Properties:

    • Closed under + and ×
    • Additive & multiplicative inverses
    • Finite number of elements

Irreducible Polynomial​

Definition​

  • Cannot be factored into lower-degree polynomials

✔ Required to construct field

Primitive Polynomial​

Definition​

  • Irreducible polynomial
  • Also generates entire multiplicative group

Key Property​

  • Every primitive polynomial is irreducible
  • Not every irreducible polynomial is primitive

Connection to LFSR​

  • LFSR feedback defined by polynomial

  • Primitive polynomial ⇒

    • Maximum-length sequence
    • Good pseudorandomness

Key Takeaways​

  • Polynomial arithmetic used in:

    • AES
    • LFSR

  • Finite fields:

    • Built using irreducible polynomials

  • Primitive polynomials:

    • Important for sequence generation

Final Conclusion​

  • Cryptography uses:
GF(2n)\text{GF}(2^n)

  • Built using:

    • Polynomial arithmetic
    • Irreducible polynomials

✔ Foundation of modern symmetric cryptography (like AES)