Examples
Example One
Consider the simple set of simultaneous congruences
- x ≡ 3 (mod 4)
- x ≡ 5 (mod 6)
Now, for x ≡ 3 (mod 4) to be true, x = 3 + 4j for some integer j. Substitute this in the second equation
- 3+4j ≡ 5 (mod 6)
since we are looking for a solution to both equations.
Subtract 3 from both sides (this is permitted in modular arithmetic)
- 4j ≡ 2 (mod 6)
We simplify by dividing by the greatest common divisor of 4,2 and 6. Division by 2 yields:
- 2j ≡ 1 (mod 3)
The Euclidean modular multiplicative inverse of 2 mod 3 is 2. After multiplying both sides with the inverse, we obtain:
- j ≡ 2 × 1 (mod 3)
or
- j ≡ 2 (mod 3)
For the above to be true: j = 2 + 3k for some integer k. Now substitute back into 3 + 4j and we obtain
- x = 3 + 4(2 + 3k)
Expand:
- x = 11 + 12k
to obtain the solution
x ≡ 11 (mod 12)
Example 2 (An Easier Method)
Although the method utilized in the preceding example is coherent, it does not work for every problem.
Consider these four systems of congruences:
- x ≡ 1 (mod 2)
- x ≡ 2 (mod 3)
- x ≡ 3 (mod 5)
- x ≡ 4 (mod 11)
In order to proceed in finding an expression that represents all the solutions that satisfies this system of linear congruences, it is important to know that a (mod b) has an analogous identity:
- a (mod b) ⇔ bk + a, ∀k ∈ Z, where k is an arbitrary constant.
PROCEDURE
1. Begin by rewriting the first congruence as an equation:
2. Rewrite the second congruence as an equation, and set the equation found in the first step equal to this equation, since x will substitute the x in the second congruence:
- x ≡ 2 (mod 3)
- x = 2a + 1 ≡ 2 (mod 3)
- 2a ≡ 1 (mod 3)
- a ≡ 2-1 (mod 3)
- a = -1.
Because a must be a positive nonnegative inverse, we need a positive a. Thus, we add whatever our current modulus is to a, which is a = -1 + 3 = 2.
3. We now rewrite a = 2 in terms of our current modulus:
- a = 2 (mod 3)
- ∴ a = 3b + 2
4. We now substitute our current value of a into our equation that we found in step 1 with respect to x:
- x = 2a + 1
- = 2(3b + 2) + 1, ∀b ∈ Z
- = 6b + 5.
∴ x = 6b + 5.
5. We now substitute our new value for x into the x in our third linear congruence, and rewrite 3 (mod 5) to its equivalent expression:
- x ≡ 3 (mod 5)
- =6b + 5 ≡ 3 (mod 5)
- =6b + 5 = 5b + 3
- = b = -2.
Because b = -2, we add our current to modulus to it in order to obtain b = 3.
∴ b = 5c + 3.
6. We again substitute our new value for b into our equation that we found in step 4 with respect to x:
- x = 6b + 5
- = 6(5c + 3) + 5
- = 30c + 23
∴ x = 30c + 23, ∀c ∈ Z
7. We now substitute our new value for x into the x of our final linear congruence, rewriting 4 (mod 11) to its equivalent expression:
- x ≡ 4 (mod 11)
- = 30c + 18 ≡ 4 (mod 11)
- = 30c + 23 = 11c + 4
- = 19c = -19
- = c = -1.
Adding our current modulus to the value that c represents, our new c= 10.
∴ c = 11d + 10, ∀d ∈ Z.
8. Our final step is to substitute c into the equation with respect to x that we found in step 6:
- x = 30c + 23
- = 30(11d + 10) + 23
- = 330d + 323.
∴ 330d + 323 represents all solutions that satisfies the system of congruences with which we began.
Checking Our Work
To check that our answer is correct, we deduce whether each respective residue is conceived when we compute 323 by the modulo of each congruence:
323 ≡ 1 (mod 2)
323 ≡ 2 (mod 3)
323 ≡ 3 (mod 5)
323 ≡ 4 (mod 11)
An alternative method would be to deduce whether each modulus divides the difference of 323 and each congruence's respective residue:
2 | (323 - 1) is true.
3 | (323 - 2) is true.
5 | (323 - 3) is true.
11 | (323 - 4) is true.
Another way to solve the system of linear congruences is to use the Chinese Remainder Theorem, and it will give us the same result.
Example 3 (Similar Method Utilized Above but with a Twist)
When solving a system of linear congruences using the method utilized in the above example, there will be situations where solving for a variable will produce a rational.
The key to solving for the variable is to add the current modulus to the other side of the equation, until a multiple of the coefficient of the variable that is being solved for
is procured. Here is an example:
- x ≡ 2 (mod 3)
- x ≡ 3 (mod 5)
- x ≡ 2 (mod 7)
PROCEDURE
1. Rewrite the first linear congruence to its equivalent equation:
- x ≡ 2 (mod 3)
- x = 3a + 2, ∀a ∈ Z.
2. Rewrite the second congruence as an equation, and set the expression equal to the expression found in the preceding step:
- x ≡ 3 (mod 5)
- x = 5a + 3, ∀a ∈ Z
- 3a + 2 = 5a + 3
- -1 = 2a
This is where the method used in example 2 appears to have troubles, but I found a solution: Add whatever the current modulus is to the side of the equation where the variable is not, until the coefficient is able to divide it. The reason why we can do this is because of the definition of a congruence class Thus,
3. Add 5, which is our modulus, to -1, to obtain:
4. Rewrite a = 2 as its equivalent modular equation
- a = 2 becomes a = 5b + 2, ∀b ∈ Z.
5. Substitute our current a into the equation procured in step 1 with respect to x:
- x = 3a + 2 = 3 (5b + 2) + 2 = 15b + 8.
- ∴ x = 15b + 8.
6. Finally, rewrite the third congruence, and set it equal to the equation incurred in the preceding step, solving for b.
- x ≡ 2 (mod 7) can be rewritten as x = 7b + 2
Substituting for x, we have
Add our current modulus, which is 7, to -6, until a multiple of 8 is conceived:
Thus,
Rewriting b in terms of its modulus, we have
7. Substitute our new equation b for b in the equation with respect to x we conceived in step 6:
- x = 15b + 8
- = 15 (7c + 1) + 8
- = 105c + 23
- ∴ x = 105c + 23.
∴ 105c + 23 represents all solutions that satisfies the system of congruences with which we began.
Checking Our Work
To check that our answer is correct, we deduce whether each respective residue is conceived when we compute 23 by the modulo of each congruence:
23 ≡ 2 (mod 3)
23 ≡ 3 (mod 5)
23 ≡ 2 (mod 7)
General algorithm
In general:
- write the first equation in its equivalent form
- substitute it into the next
- continue until the last equation
- back substitute, then simplify
- rewrite back in the congruence form
If the moduli are coprime, the Chinese remainder theorem gives a straightforward formula to obtain the solution.
In number theory, 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.
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.
In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard statement is:
In mathematics, a system of linear equations is a collection of one or more linear equations involving the same set of variables. For example,
In mathematics, for given real numbers a and b, the logarithm logb a is a number x such that bx = a. Analogously, in any group G, powers bk can be defined for all integers k, and the discrete logarithm logb a is an integer k such that bk = a. In number theory, the more commonly used term is index: we can write x = indra (mod m) for rx ≡ a (mod m) if r is a primitive root of m and gcd(a,m) = 1.
In mathematics, the modular group is the projective special linear group PSL(2, Z) of 2 × 2 matrices with integer coefficients and determinant 1. The matrices A and −A are identified. The modular group acts on the upper-half of the complex plane by fractional linear transformations, and the name "modular group" comes from the relation to moduli spaces and not from modular arithmetic.
In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. The objects of focus for this article include rewriting systems. In their most basic form, they consist of a set of objects, plus relations on how to transform those objects.
The affine cipher is a type of monoalphabetic substitution cipher, where each letter in an alphabet is mapped to its numeric equivalent, encrypted using a simple mathematical function, and converted back to a letter. The formula used means that each letter encrypts to one other letter, and back again, meaning the cipher is essentially a standard substitution cipher with a rule governing which letter goes to which. As such, it has the weaknesses of all substitution ciphers. Each letter is enciphered with the function (ax + b) mod 26, where b is the magnitude of the shift.
In mathematics, to solve an equation is to find its solutions, which are the values that fulfill the condition stated by the equation, consisting generally of two expressions related by an equals sign. When seeking a solution, one or more variables are designated as unknowns. A solution is an assignment of values to the unknown variables that makes the equality in the equation true. In other words, a solution is a value or a collection of values such that, when substituted for the unknowns, the equation becomes an equality. A solution of an equation is often called a root of the equation, particularly but not only for polynomial equations. The set of all solutions of an equation is its solution set.
The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second fastest method known. It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties. It was invented by Carl Pomerance in 1981 as an improvement to Schroeppel's linear sieve.
Modular exponentiation is a type of exponentiation performed over a modulus. It is useful in computer science, especially in the field of public-key cryptography.
In number theory, Dixon's factorization method is a general-purpose integer factorization algorithm; it is the prototypical factor base method. Unlike for other factor base methods, its run-time bound comes with a rigorous proof that does not rely on conjectures about the smoothness properties of the values taken by polynomial.
In classical cryptography, the Hill cipher is a polygraphic substitution cipher based on linear algebra. Invented by Lester S. Hill in 1929, it was the first polygraphic cipher in which it was practical to operate on more than three symbols at once.
In computational number theory, the index calculus algorithm is a probabilistic algorithm for computing discrete logarithms. Dedicated to the discrete logarithm in where is a prime, index calculus leads to a family of algorithms adapted to finite fields and to some families of elliptic curves. The algorithm collects relations among the discrete logarithms of small primes, computes them by a linear algebra procedure and finally expresses the desired discrete logarithm with respect to the discrete logarithms of small primes.
In mathematics, the rational sieve is a general algorithm for factoring integers into prime factors. It is a special case of the general number field sieve. While it is less efficient than the general algorithm, it is conceptually simpler. It serves as a helpful first step in understanding how the general number field sieve works.
The Tonelli–Shanks algorithm is used in modular arithmetic to solve for r in a congruence of the form r2 ≡ n, where p is a prime: that is, to find a square root of n modulo p.
In mathematics, particularly in the area of number theory, a modular multiplicative inverse of an integer a is an integer x such that the product ax is congruent to 1 with respect to the modulus m. In the standard notation of modular arithmetic this congruence is written as
Secret sharing consists of recovering a secret S from a set of shares, each containing partial information about the secret. The Chinese remainder theorem (CRT) states that for a given system of simultaneous congruence equations, the solution is unique in some Z/nZ, with n > 0 under some appropriate conditions on the congruences. Secret sharing can thus use the CRT to produce the shares presented in the congruence equations and the secret could be recovered by solving the system of congruences to get the unique solution, which will be the secret to recover.
In cryptography, Very Smooth Hash (VSH) is a provably secure cryptographic hash function invented in 2005 by Scott Contini, Arjen Lenstra and Ron Steinfeld. Provably secure means that finding collisions is as difficult as some known hard mathematical problem. Unlike other provably secure collision-resistant hashes, VSH is efficient and usable in practice. Asymptotically, it only requires a single multiplication per log(n) message-bits and uses RSA-type arithmetic. Therefore, VSH can be useful in embedded environments where code space is limited.
Pocklington's algorithm is a technique for solving a congruence of the form
