Introduction to group, field, finite field of the form GF(p)

Introduction to Group

What is a Group?

A group is a set of elements combined with an operation that follows four fixed rules.

A *group (G, ) is a set G with an operation * such that:

Rule	Meaning	Real-Life Example
Closure	Result stays in group	2 + 3 = 5 (still integer)
Associativity	Order doesn’t change result	(2+3)+4 = 2+(3+4)
Identity	One element does nothing	0 in addition
Inverse	Every element cancels	5 + (−5) = 0

Example: Set of integers Z under addition (+) forms a group.

Real-Life Analogy

Bank balance

• Deposit (+)
• Withdraw (−)
• Zero balance = identity

Introduction to Field

What is a Field?

A field is a group with two operations:

• Addition (+)
• Multiplication (×)

Key Properties

• Addition → forms a group
• Multiplication → forms a group (except zero)
• Division is possible (except by zero)

Examples of Fields

Field	Example
Real numbers	R
Rational numbers	Q
Finite fields	GF(p)

Real-Life Example: Calculator operations  - You can add, subtract, multiply, and divide numbers easily

Finite Field of the Form GF(p)

What is GF(p)?

• GF(p) = Galois Field
• p must be a prime number
• Elements are {0, 1, 2, ..., p−1}

Example: GF(7)

Operation	Result
5 + 4	9 mod 7 = 2
3 × 5	15 mod 7 = 1

Why Prime is Important?

• Guarantees multiplicative inverse
• Required for cryptography

Real-Life Example: Clock system - After 12 comes 1 → modular arithmetic

Modular Arithmetic

Modular arithmetic works on remainders.

Formula: a mod n = remainder when a is divided by n

Example

Expression	Result
17 mod 5	2
24 mod 7	3

Real-Life Example

• Digital clock - 14:00 = 2 PM
• Car number plates
• Cryptography keys

Prime and Relative Prime Numbers

Prime Number

A number divisible only by 1 and itself

| Prime Numbers | 2, 3, 5, 7, 11 |

Relative Prime (Coprime)

Two numbers whose GCD = 1

Numbers	Relative Prime?
8 and 15	Yes
12 and 18	No

Real-Life Use

• Encryption algorithms
• Key generation
• Digital security

Extended Euclidean Algorithm

Purpose

• Finds GCD
• Finds multiplicative inverse

Formula: ax + by = gcd(a, b)

Example: Find inverse of 3 mod 11

Steps:

11 = 3×3 + 2
3 = 2×1 + 1
2 = 1×2 + 0

Back substitute → Inverse of 3 mod 11 = 4

Real-Life Example

• Used in RSA encryption
• Secure key exchange

Advanced Encryption Standard (AES)

What is AES?

AES is a symmetric encryption algorithm used worldwide.

Feature	Details
Block size	128 bits
Key size	128, 192, 256 bits
Speed	Very fast
Security	Very high

AES Working Steps

Step	Description
SubBytes	Byte substitution
ShiftRows	Row shifting
MixColumns	Column mixing
AddRoundKey	Key addition

Real-Life Examples

• ATM transactions
• WhatsApp messages
• Wi-Fi passwords
• Online banking

Simple Analogy

• Message = locked box
• Key = password
• Only correct key opens the box

Summary Table (Quick Revision)

Topic	Key Use
Group	Mathematical structure
Field	Supports division
GF(p)	Used in cryptography
Modular Arithmetic	Security calculations
Prime Numbers	Key strength
Euclidean Algorithm	Modular inverse
AES	Data encryption

Fermat’s Little Theorem

Statement: If p is a prime number and a is not divisible by p, then:

$$a^{p-1}\equiv 1(\text{mod }p)$$

Simple Meaning: When you raise a number to (prime − 1) and divide by that prime, the remainder is 1.

Example: Let: a = 3, p = 7

$$3^{6} = 729$$
$$729\mathrm{m}\mathrm{o}\mathrm{d}7=1$$

Real-Life Use

• Used in RSA
• Used in primality testing
• Helps reduce large power calculations

Euler’s Theorem

Statement: If gcd(a, n) = 1, then:

$$a^{\phi (n)}\equiv 1(\text{mod }n)$$

Where φ(n) is Euler’s Totient Function.

Euler Totient Function φ(n)

n	φ(n)
7	6
10	4
15	8

Example

$$3^{\varphi(10)} = 3^4 = 81$$
$$81\mathrm{m}\mathrm{o}\mathrm{d}10=1$$

Difference from Fermat

Fermat	Euler
Only for prime	Works for composite
Simpler	More general

Primality Testing

Checking whether a number is prime or composite.

Types

Method	Description
Trial Division	Check all divisors
Fermat Test	Based on Fermat theorem
Miller-Rabin	Probabilistic test

Fermat Primality Test

If:

$$a^{n-1}\equiv ̸1(\text{mod }n)$$

Then n is composite.

Real-Life Use

• RSA key generation
• Secure encryption systems

Chinese Remainder Theorem (CRT)

Statement: If moduli are pairwise coprime, a system of congruences has a unique solution.

Example

Solve:

$$x \equiv 1 \ (\text{mod } 3)$$
$$x\equiv 2(\text{mod }5)$$

Solution:

$$x=7$$

Real-Life Example

• Calendar systems
• Parallel computation
• Used in RSA speed optimization

Discrete Logarithmic Problem (DLP)

Given:

$$a^x\equiv b(\text{mod }p)$$

Find x.

Why It Is Hard

• No fast solution for large numbers
• Easy to compute forward, hard to reverse

Used In

• Diffie-Hellman
• ElGamal encryption

Real-Life Analogy

• Easy to lock a door
• Very hard to break without key

Principles of Public Key Cryptosystems

Basic Concept

Uses two keys:

• Public Key (shared)
• Private Key (secret)

Working

Action	Key Used
Encrypt	Public key
Decrypt	Private key

Advantages

• Secure communication
• No need to share secret key

RSA Algorithm

RSA Full Steps

Step 1: Choose primes

$$p=11,q=17$$

Step 2: Compute n

$$n=p\times q=187$$

Step 3: Compute φ(n)

$$\phi (n)=(p-1)(q-1)=160$$

Step 4: Choose e

$$gcd(e,160)=1$$

Choose e = 7

Step 5: Find d

$$d\times e\equiv 1(\text{mod }\phi (n))$$

d = 23

Encryption Formula

$$C=M^e\mathrm{m}\mathrm{o}\mathrm{d}n$$

Decryption Formula

$$M=C^d\mathrm{m}\mathrm{o}\mathrm{d}n$$

Security of RSA

Why RSA Is Secure?

Reason	Explanation
Large primes	Hard to factor
One-way function	Easy forward, hard reverse
DLP hardness	No fast algorithm

Security Depends On

$$n=p\times q$$

Factoring n into p and q is computationally infeasible for large values.

Common Attacks

• Brute force
• Mathematical factorization
• Side-channel attacks

Final Revision Table

Topic	Key Idea
Fermat Theorem	Prime modulus
Euler Theorem	Totient based
Primality Test	Prime checking
CRT	Multiple congruences
DLP	One-way hardness
Public Key Crypto	Two keys
RSA	Secure encryption
RSA Security	Factoring problem

MCA Exam Tip

• Always write formula
• Add small numerical example
• Mention real-life application