Number Theory for Cryptography Questions

Comprehensive mastery of the number theoretic and algebraic foundations that underpin modern cryptography. Core topics include modular arithmetic and modular exponentiation, prime number theory and primality testing, integer factorization problems, the discrete logarithm problem in multiplicative groups, quadratic residues and Legendre and Jacobi symbols, Euler theorem, group theory, ring theory, finite fields, and elliptic curve groups. Candidates should be able to apply these concepts to analyze and explain public key systems such as Rivest Shamir Adleman, Diffie Hellman key exchange, ElGamal, and elliptic curve cryptography, and to show why security reduces to the hardness of integer factorization or discrete logarithm in the appropriate group. The scope covers algorithmic tools and their practical complexity including the extended Euclidean algorithm, fast modular exponentiation, Chinese remainder theorem, Miller Rabin and deterministic primality tests, trial division, Pollard rho and Pollard p minus one factorization methods, elliptic curve method for factorization, quadratic sieve, general number field sieve, baby step giant step, Pollard rho for discrete logarithm, and index calculus approaches. Candidates should be comfortable solving representative problems by hand or with small code examples such as computing modular inverses, performing modular exponentiation, applying the Chinese remainder theorem, solving small discrete logarithm instances, and reasoning about how algorithmic advances translate into concrete key size and security recommendations.