Advanced Mathematics for Computer Science HNCST409 KTU BTech Honors 2024 Scheme- Dr Binu V P

  What Is an Equivalence Relation? Let A A  be a set. A relation \sim ∼ on A A  is called an equivalence relation if it satisfies three properties : 1. Reflexive For every a ∈ A a \in A , a ∼ a a \sim a 2. Symmetric For all a , b ∈ A a, b \in A , a ∼ b ⇒ b ∼ a a \sim b \Rightarrow b \sim a 3. Transitive For all a , b , c ∈ A a, b, c \in A , a ∼ b  and  b ∼ c ⇒ a ∼ c a \sim b \text{ and } b \sim c \Rightarrow a \sim c Why Equivalence Relations Are Important Equivalence relations allow us to: Group elements into equivalence classes Treat different objects as “essentially the same” Build structures like modular arithmetic , finite fields , and quotient sets Congruence Modulo n n n Let n ∈ Z , n > 0 n \in \mathbb{Z}, n > 0 . For integers a a  and b b , we say: a ≡ b ( m o d n ) a \equiv b \pmod{n} if and only if: n ∣ ( a − b ) n \mid (a - b) That is, a − b a - b  is divisible by n n . Claim Congruence modulo n n n is...

AKS Primality Testing Algorithm Short Description The AKS (Agrawal–Kayal–Saxena) algorithm is a deterministic polynomial-time algorithm used to test whether a given number is prime. Unlike probabilistic methods such as the Fermat or Miller–Rabin tests, AKS always produces a correct result without relying on randomness. Introduced in 2002 by Agrawal, Kayal, and Saxena, this algorithm resolved a long-standing open problem in computer science by proving that primality testing belongs to the complexity class P . 2. Mathematical Foundation 2.1 Fermat’s Little Theorem (Classical) If p p p is prime and a a a is not divisible by p p p : a p ≡ a ( m o d p ) a^{p} \equiv a \pmod{p} This is the basis of many probabilistic tests. ❗ Problem: Some composite numbers (Carmichael numbers) also satisfy this. 3. Key Insight Behind AKS Instead of working with numbers , AKS works with polynomials . AKS Theorem For an integer n > 1 n > 1 n > 1 , n  is prime     ⟺    ( ...

  What Is a Galois Field? A Galois Field , or finite field , is a mathematical system with a finite number of elements in which the operations of addition, subtraction, multiplication, and division (except by zero) are well defined and satisfy all field properties. Galois fields are denoted by GF(pⁿ) , where: p is a prime number (called the characteristic) n is a positive integer They are named after Évariste Galois , whose work laid the foundation of modern algebra. Types of Galois Fields 1. Prime Fields: GF(p) A prime field contains exactly p elements : G F ( p ) = { 0 , 1 , 2 , … , p − 1 } GF(p) = \{0, 1, 2, \ldots, p-1\} All arithmetic is performed modulo p . Arithmetic Operations in GF(p) (Mod p Arithmetic) Let us consider GF(7) as an example. 1. Addition (mod p) Add normally and reduce modulo p. 5 + 4 = 9 ≡ 2 ( m o d 7 ) 5 + 4 = 9 \equiv 2 \pmod{7} 2. Subtraction (mod p) Subtract normally and reduce modulo p. 3 − 5 = − 2 ≡ 5 ( m o d 7 ) 3 - 5 = ...

  Hash Functions: A Number Theory Perspective Introduction A hash function is a mathematical function that takes an input of arbitrary length and maps it to a fixed-size output , called a hash value or digest . Hash functions are fundamental in computer science and cryptography, playing a vital role in data integrity, authentication, digital signatures, and secure storage . From a number theory viewpoint, hash functions rely heavily on modular arithmetic, prime numbers, finite fields, and algebraic structures , making them an interesting and practical application of abstract mathematics. What Is a Hash Function? Formally, a hash function is a function: h : { 0 , 1 } ∗ → { 0 , 1 } n h : \{0,1\}^* \rightarrow \{0,1\}^n that maps an input of any length to a fixed-length output of n n n bits. Key Characteristics A good hash function should satisfy: Determinism – The same input always produces the same output Efficiency – The hash is computed quickly Uniformity –...