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 world’s oldest algorithms is Euclid’s algorithm for computing the greatest common divisor of two integers. 

GCD (Greatest Common Divisor) or HCF (Highest Common Factor) of two numbers is the largest number that divides both of them.

Let’s look at a simple algorithm for GCD, find all prime factors of both numbers, then find the intersection of all factors present in both numbers. Finally, return the product of elements in the intersection.

Program to find GCD or HCF of two numbers

30 = 2x2x3x3

60 = 2x2x3x5

GCD = Multiplication of common factor = 2x2x3 = 12

For example, GCD of 20 and 28 is 4, and GCD of 98 and 56 is 14.

The Algorithm

The Euclidean Algorithm for finding GCD (A, B) is as follows:

• If A = 0 then GCD (A, B) =B, since the GCD (0, B) =B, and we can stop.

• If B = 0 then GCD (A, B) =A, since the GCD(A,0) =A, and we can stop.

• Write A in quotient remainder form (A = B⋅Q + R)

• Find GCD (B, R) using the Euclidean Algorithm since GCD (A, B) = GCD (B, R)

Extended Euclidean Algorithm

The extended Euclidean algorithm is an algorithm to compute integers x and y such that ax + by = gcd(a,b)

given a and b

The existence of such integers is guaranteed by Bézout’s lemma.

The extended Euclidean algorithm can be viewed as the reciprocal of modular exponentiation.

By reversing the steps in the Euclidean algorithm, it is possible to find these integers xx and yy. The whole idea is to start with the GCD and recursively work our way backward. This can be done by treating the numbers as variables until we end up with an expression that is a linear combination of our initial numbers.

Chinese Remainder Theorem

The Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.

Theorem:

Given pairwise coprime positive integers n1,n2, n3….. , nk and integers a1,a2,a3…., ak, the system of simultaneous congruence

X= a1(mod n1)

X= a2(mod n2)

X =a3(mod n3)

.

.

.

X=ak(mod ak)

Has a solution and a unique solution is N= n1*n2*n3…. *nk

The Algorithm:

int findMinX()

{

while (true){

1. Check if remainder of x % num[j] is rem[j] or not (for all j from 0 to k-1)

2. If all remainders matched, we found x

3. Else try next number

Increment x

}

return x;

}

Applications

1 ) Range ambiguity resolution

The range ambiguity resolution techniques used with medium pulse repetition frequency radar can be seen as a special case of the Chinese remainder theorem.

2) Encryption

Most implementations of RSA use the Chinese remainder theorem during signing of HTTPS certificates and during decryption.

The Chinese remainder theorem can also be used in secret sharing, which consists of distributing a set of shares among a group of people who, all together (but no one alone), can recover a certain secret from the given set of shares.

Each of the shares is represented in a congruence, and the solution of the system of congruences using the Chinese remainder theorem is the secret to be recovered.

Secret sharing using the Chinese remainder theorem uses, along with the Chinese remainder theorem, special sequences of integers that guarantee the impossibility of recovering the secret from a set of shares with less than a certain cardinality.

3) Fast Fourier transform

· The prime-factor FFT algorithm (also called Good-Thomas algorithm) uses the Chinese remainder theorem for reducing the computation of a fast Fourier transform of size n1,n2 to the computation of two fast Fourier transforms of smaller sizes n1 and n2.The prime-factor FFT algorithm (also called Good-Thomas algorithm) uses the Chinese remainder theorem for reducing the computation of a fast Fourier transform of size n1,n2 to the computation of two fast Fourier transforms of smaller sizes n1 and n2

Euler’s Theorem

Definition & Significance of the Euler Theorem!

Let q be a positive integer, and let p be an integer that is relatively prime to q. Then

pf(q) º 1(mod q)

where f(q) is Euler’s totient function, which counts the number of positive integers ≤ q which are relatively prime to q.

Euler Theorem deals with the concept of prime numbers, modulus/remainder, & congruency. It aims to provide a concept where coprime numbers can be correlated somehow to provide a value that can be used later as a hash value or for encryption keys in cryptography.

Example:

Suppose p is relatively prime to 10. Since f(10) = 4, Euler’s theorem says that p4º1 (mod 10), i.e. the unit digits of p4 is always 1.

Proof of Euler’s theorem:

Consider the set of non-negative numbers,

These elements are relatively (co-prime) to q.

Consider another set of non-negative numbers,

Since the sets are congruent to each other,

Since the set of numbers are relatively prime to q, dividing by the term is permissible.

Hence proved.

The Sieve of Eratosthenes

There are various algorithms for printing all prime numbers less than a specified no with various complexity and one of them is sieve of Eratosthenes. The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n is smaller than values near to 10 million. It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that is equal to that prime. This is the sieve’s key distinction from using trial division to sequentially test each candidate number for divisibility by each prime. Once all the multiples of each discovered prime have been marked as composites, the remaining unmarked numbers are primes.

The Algorithm :

Let us look at the algorithm more clearly:

1. Create a list of consecutive integers from 2 to n: (2, 3, 4, …, n).

2. Initially, let p equal 2, the first prime number.

3. Starting from p2, count up in increments of p and mark each of these numbers greater than or equal to p2 itself in the list. These numbers will be p(p+1), p(p+2), p(p+3), etc..

4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3.

When the algorithm terminates, all the numbers in the list that are not marked are prime.

Conclusion

So this was a small tour of the most famous and amazing number theoretic algorithms with their applications to the field of computer science. Number theory is a universe in itself and we have tried to give a glimpse of it in this blog. Hope you liked reading it!