Posts

Advanced Mathematics for Computer Science HNCST409 KTU BTech Honors 2024 Scheme

About Me Syllabus Advanced Mathematics for Computer Science HNCST409 BTech Honors 2024 Model Question Paper and Answers University Question Paper HNCST409 BTech Honors-April 2026 and Answer Scheme Module- I Number Theory  Introduction Group , Ring and Fields Divisibility Modular Arithmetic and Congruences Equivalence Relation - Congruence Linear Congruences Solving simultaneous congruences- CRT Modular Inverses      Euclidean algorithm      Extended Euclidean algorithm  Euler’s and Fermat’s little theorem  Euler's Totient Function Prime Numbers and Prime-Power Factorization Fermat and Mersenne Prime Primality Testing and Factorization Wilson's Theorem Pseudo Primes and Carmichael Numbers Primality testing       Miller-Rabin      AKS Galois Field (introduction and basic operations) RSA cryptosystem: key generation - encryption/decryption  Hash functions (introduction) Module - II Optimiza...
Post a Comment
Read more

Equivalence Relation

  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...
1 comment
Read more

AKS Primality Testing

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     ⟺    ( ...
Post a Comment
Read more

Galois Field and Operations

  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 = ...
Post a Comment
Read more