How do you solve problems with the Chinese remainder of the sentence

Mr. A. celebrated a milestone birthday this year; at the same time he has also completed a full seven-year period. How old did Mr. A. get? The answer - 70 years old - is not difficult to guess. Mr L., on the other hand, completed the last full year seven two years ago; his last big birthday was already 8 years ago. How old is Mr. L.?

It is interesting that the age of Mr. L. is actually clearly determined by these two details, at least if one assumes a realistic age of a person, namely years.

problem

The number results in the remainder 2 if the whole number is divided by 7 and the remainder 8 if the whole number division by 10 is used. Which number is?

So the number can be represented as

  =   ·7 + 2   =   ·10 + 8

or in general

  =   · +    =   · + 

In other words, the following applies

  (mod) and

  (mod).

The numbers and are referred to as modules in this context, the numbers and as the associated remainders.

The so-called Chinese remainder of the law states that if the modules and are relatively prime, there is modulo · a unique solution.

 

Using the Chinese remainder, calculations can be made in based on calculations in 0 ×  ...  × -1, in which 0, ..., -1 are the prime powers of.

calculation

Since and are coprime, the greatest common factor 1 can be represented as

1   =   · + ·

The coefficients and are not clearly determined here, but there are many values ​​for and that satisfy the equation. The extended Euclidean algorithm calculates the greatest common divisor and a possible value for and from and.

 

Multiplication with (-) gives

-   =   (-)·· + (-)··

Rearranging results

(-)·· +    =   -(-)·· + 

The searched coefficients and for and are found. So is

  =  (-)·· + 

a possible solution.

 

However, we are looking for the unambiguous solution modulo ·. To calculate the value of modulo · it is sufficient to reduce the product (-) · modulo, because it is

(-) mod +

<(-) mod + (da <)

= ((-) mod + 1)

 ((-1) + 1 ) ·

=  ·

So is

= (-) mod +

the uniquely determined number sought.

implementation

The Chinese remainder theorem can be formulated in general for coprime modules and associated remainders.

Sentence: (Chinese remainder sentence)

Given are  coprime modules 0, ..., -1 and associated remnants 0, ..., -1. The number that gives the remainder modulo is uniquely determined modulo the product of all.

The following recursive function chineseRemainder receives a list of modules and a list of associated remainders as parameters. If these lists consist of only one item at a time, the function returns those items. Otherwise it recursively first calculates the number modulo, which results from the first half of and according to the Chinese remainder, and then the number modulo, which results from the second half of and. The products and are coprime, since they are all coprime to one another. The value is given by the function extgcd calculated using the extended Euclidean algorithm; the other two calculated values ​​and are not used. From and as well as the associated residues and the solution can then be calculated using the method given above. In addition to this solution, the function also returns the associated module.

The implementation in the Python programming language follows. Again, use is made of the option of assigning tuple values. The notation nn [: k] denotes an excerpt (slice) from the list nn from start to index (only). Similarly, nn [k:] denotes a section from the index (inclusive) to the end of the list.

 

 

algorithm ChineseRemainder
Input:List of coprime modules, list of remainders
Output:Product of the modules, number according to the Chinese remainder theorem
Method:
def chineseRemainder (nn, rr): if len (nn) == 1: return nn [0], rr [0] else: k = len (nn) // 2 m, a = chineseRemainder (nn [: k], rr [: k]) n, b = chineseRemainder (nn [k:], rr [k:]) g, u, v = extgcd (m, n) x = (ba) * u% n * m + a return m * n, x

 

The advantage of this implementation based on the divide-and-conquer principle is that in the lower recursion levels there are many calculations with small numbers and only a few calculations with large numbers in the upper recursion levels.

Implementation in Haskell

One possible implementation in the functional programming language Haskell is given below. The parameters of the function are in turn a list of modules and a list of associated remainders. If these lists only consist of one element or one element, (,) is returned. Otherwise, the calculation is recursive according to the procedure given above.

 

- Chinese remainder sentence chineseRemainder :: [Integer] -> [Integer] -> (Integer, Integer) chineseRemainder [n] [r] = (n, r) chineseRemainder nn rr = (m * n, x) where k = length nn `div` 2 (m, a) = chineseRemainder (take k nn) (take k rr) (n, b) = chineseRemainder (drop k nn) (drop k rr) (g, u, v) = extgcd mnx = (ba) * u `mod` n * m + a

 

The function extgcd performs the calculation of the extended Euclidean algorithm.

 

example

 

 

exercise

On the demo

If we line up in rows of ten, one is not enough. If we line up in rows of nine, one is also too few. It continues like this up to rows of two, where one is also missing. How much are we? (Under 3000).

Note: When using the Chinese remainder theorem, the modules must be coprime.

In this case, the solution is even easier. If the remainder are all equal, the solution is the least common multiple (lcm) of the modules plus this remainder. This remainder is -1 here.

 

literature

[AHU 74]A.V. Aho, J.E. Hopcroft, J.D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley (1974)
[CLRS 01]T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms. 2nd edition, The MIT Press (2001)
[Lan 12]H.W. Lang: Algorithms in Java. 3rd edition, Oldenbourg (2012)

[Additional Information]

  
[Lan 18]H.W. Lang: Cryptography for Dummies. Wiley (2018)

[Additional Information]