Number Theoretic Algorithms
Number Theoretic Algorithms Number theory is a branch of mathematics which studies numbers, specifically integers. Number theory was once viewed as a beautiful but largely useless subject in pure mathematics. Today number-theoretic algorithms are used widely, due in large part to the invention of cryptographic schemes based on large prime numbers. Since numbers are the heart of computer science, these concepts of number theory have a wide extension to a lot of standard computational problems. A variety of these properties of integers studied in number theory are used to design efficient and statistically sound algorithms to solve these computational problems. In this blog, we will take a deep dive into some of the most famous number theory algorithms and learn how they are used to solve real world problems. Contents Euclidean Algorithm for GCD Extended Euclidean Algorithm Chinese Remainder Theorem Euler’s Theorem The Sieve of Eratosthenes Euclidean Algorithm for GCD One of the wo...