CENG 514

Computational Number Theory

Fundamentals, Algorithms for Congruences, Equations, and Powers, Euler’s Φ Function and Coding, Second Degree Congruences, Prime Numbers, Quadratic Residues, Continued Fractions, Algorithms for Primality Testing, Finding Large Primes, Elliptic Curves, Factoring Algorithms, Algorithms for Exponential Methods of Factoring Integers, Subexponential Factoring Algorithms, Computing Discrete Logarithms.

Topics
Introduction
Basic Properties of Integers
Congruences
Congruences
Basic Integer Arithmetic, Faster Integer Arithmetic
Computation with large integers
Asymptotic notation, Machine models and complexity theory
Euclid s Algorithm
Prime Numbers
Abelian Groups
Rings
Finite and Discrete Probability
Hash Functions
Probabilistic Algorithms