What is modular arithmetic?

Modular arithmetic is a system of arithmetic for integers, whose values reset to zero and begin to increase again, after reaching a certain predefined value, called the modulus (modulo). Modular arithmetic is widely used in computer science and cryptography.

Let ZN be a set ofall non-negative integers that are smaller than N    ZN =0,1,2,...,N-1

where:

  • N is a positive integer.
  • if N is a prime, it will be denoted p (and the whole set as Zp).

Modular linear equations

Let d = gcd(n, m) and let j and i be the integers where, d= in + jm.  Suppose further d | k, then the equation [m]n X = [k]n has the solution as, x=jkdn.

Example

Consider [6]8 X = [4]8then gcd(8,6) = 22= (1) 8 + (-1)6 and 2 |4so the solutions is, X =-1(4)28 = -28 =68The following equation is used to solve the other,j +wndn for w=0, 1, ., d-1And the other equation is, 6 +1(8)/28 =108 =28.

Euclid’s algorithm

The gcd algorithms are explained in terms of the Euclid elements. It is written as a recursive algorithm or program based on a and b (positive integers). However, the inputs b and a are non-negative integers.

EUCLID-ALG (a, b)

  1. if b = 0
  2. then return a
  3. else return EUCLID-ALG (b, a mod b)

Example

The running of EUCLID-ALG  will consider the calculation of gcd (30, 21)

EUCLID-ALG (30, 21) 

=  EUCLID-ALG (21, 9)

=  EUCLID-ALG (9, 3)

=  EUCLID-ALG (3, 0)

=  3

This computation has three different recursive invocations of EUCLID-ALG. The fact that when the EUCLID-ALG algorithm returns a at line 2, then b with 0, whereas,  gcd (a, b) = gcd (a, 0) = a. The algorithm cannot recurse indefinitely and the second argument gets decreased in all recursive calls. Therefore, EUCLID -ALG always ends with the exact answer.

Solving modular linear equations

Consider the following problem and find the solution to the given equation,

ax  b (mod n)

To solve the ax  b (mod n) equation the following algorithm is used to print the solutions to the given equation. The inputs both n and a are arbitrary positive integers, whereas, b will be an arbitrary integer.

Algorithm

MODULARLINEAREQUATIONSOLVE (a, b, n)

  1. (d, x′, y′)  EXTENDED-EUCLIDALG(a, n)
  2. if d | b
  3. then x0  x' bd mod n
  4. for i  0 to d - 1
  5. do print x0 + i nd mod n
  6. else print "no solutions"

Consider the following examples

Example 1

14x30(mod100) where b = 30, n = 100, and a = 14. By calling EXTENDED_EUCLIDALG at line 1, then the user can simply obtain (d, x, y) = (2, -7, 1). However, 2 | 30, then the line 3 to 5 are executed. At the line 3, calculate x0 = (-7)(15) mod 100 and x0 = 95. The loop at line 4 to 5 prints the two different solutions such as 45 and 95.

From Theorem 1, the equation  axb(mod n) has a solution if and only if gcd (a, n) | b. The solution to the equation is unique if and only if gcd (a, n) = 1.

Example 2:  Solve 3x ≡ 5 (mod 6), Note that gcd (3, 6) = 3 and 3 - 5. Thus this equation has no solution.

The procedure of MODULARLINEAREQUATIONSOLVE works as follows,

Line 1 computes the value of d as gcd(a, n) and also other two values like x and y such that d = ax + ny while demonstrating, the equation ax  d (mod n) results in x. If d cannot divide b, then ax  b (mod n) will not have any solution. Line 2 verifies if d | b; if not, then line 6 will report that there are no solutions. Otherwise, line 3 calculates the solution x0 to ax  b (mod n). The other d - 1 solution can be obtained by just adding many nd, modulo n. The for loop in lines 4 to 5 prints all solutions related to d, beginning with x0 and spaced nd apart, modulo n.

MODULARLINEAREQUATIONSOLVE performs the arithmetic operations O(lg n + gcd (a, n)) since EXTENDED-EUCLIDALG performs the arithmetic operations O(lg n), and each iteration of the for loop at lines 4 to 5 performs a constant number of arithmetic operations.

Pseudocode for solving modular linear equation

Void solvemodlinear (int m, int n, int k)

{

index I;

int j, I, d;

Euclid (n, m, d, I, j);

If (d | k)

{

For (w = 0; w <= d-1; w++ )

{

Cout<<jkd +wnn

}

}

}

In the above solvemodlinear method, an index I along with other integers are declared. The method Euclid (n, m, d, I, j) is called. When the if codition is true then it will execute the for loop to print the value of jkd + wnn, when the value of w is less than d-1, then for loop will be terminated.

Time complexity analysis

The running time of the Euclidean algorithm is estimated by Lame's theorem, which establishes a surprising connection between the Euclidean algorithm and the Fibonacci sequence:

If a>b1 a>b1 and b< Fnb<Fn for some n, the Euclidean algorithm performs at most n−2n−2 recursive calls.

Moreover, it is possible to show that the upper bound of this theorem is optimal. When a = Fna = Fn  and  b = Fn − 1b = Fn − 1, gcd(a,b) will perform exactly n−2n−2 recursive calls. In other words, consecutive Fibonacci numbers are the worst-case input for Euclid's algorithm.

Given that Fibonacci numbers grow exponentially, we get that the Euclidean algorithm works in O(log min(a,b)).


Context and Applications

This topic is important for postgraduate and undergraduate courses, particularly for,

  • Bachelors in computer science engineering.
  • Masters in computer science.


Practice problems

Question 1:  For any n > 1 if gcd( a, n ) =1 then the equation ax ≡ 1 mod n will have

a) No solution

b) Unique solution

c) Same solution

d) None of the above

Answer: Option b is correct.

Explanation: For any n > 1 if gcd( a, n ) =1 then the equation ax ≡ 1 mod n has exactly one unique
solution.

Question 2: What is the time complexity to perform the modular exponentiation of a  c8 (mod m)?

a) O(m +a)

b) O(gm)

c) O(g)

d) O(ag)

Answer: Option c is correct.

Explanation: The modular exponentiation is based on the operating system environment and its performance. The given method requires a time complexity of O(g) for its completion, where g is a primitive root modulo. 

Question 3: How many solutions are there for the equation 35 x ≡ 10 (mod 50).

a) 5

b) 4

c) 3

d) 8

Answer: Option a is correct.

Explanation: When a = 35, b = 10 and n = 50. We know gcd(35, 50) = 5. Thus there are 5 solutions
to the given equation. Since 3 x 35 + (-2) x 50 = 5 we have x' = 3. Thus x0 = x' ( b / d ) mod n = 3 x (10/5) mod 50 = Other solutions are xi = x0 + i nd [ i = 1, 2, , 4 ] i.e., x1 = 16, x2 = 26, x3 = 36, x4 = 46.

Question 4: A modular linear arithmetic group can hold _______property.

a) Closure

b) Identity

c) Associativity

d) All the above

Answer: Option d is correct.

Explanation: A group is a set S together with a binary operation, defined on S for which
holds Inverses, Associativity, Closure, and Identity properties.

Question 5: For any n > 1, if gcd( a, n ) =1 then the equation ax ≡ b mod n, has how many solutions?

a) 2

b) 3

c) 6

d) 1

Answer: Option d is correct.

Explanation: For any n > 1 if gcd( a, n ) =1 then the equation ax ≡ b mod n has exactly one
solution.

Want more help with your computer science homework?

We've got you covered with step-by-step solutions to millions of textbook problems, subject matter experts on standby 24/7 when you're stumped, and more.
Check out a sample computer science Q&A solution here!

*Response times may vary by subject and question complexity. Median response time is 34 minutes for paid subscribers and may be longer for promotional offers.

Search. Solve. Succeed!

Study smarter access to millions of step-by step textbook solutions, our Q&A library, and AI powered Math Solver. Plus, you get 30 questions to ask an expert each month.

Tagged in
EngineeringComputer Science

Algorithms

Number Theoretic Algorithm

Modular Linear equation

Search. Solve. Succeed!

Study smarter access to millions of step-by step textbook solutions, our Q&A library, and AI powered Math Solver. Plus, you get 30 questions to ask an expert each month.

Tagged in
EngineeringComputer Science

Algorithms

Number Theoretic Algorithm

Modular Linear equation