Modular Forward and Backward Transformation (Menu Individual Procedures \ Chinese Remainder Theorem Applications)

The dialog window modular transformation shows the Chinese Remainder Theorem calculation with the modular remainders. In addition, the original numbers are transformed into these remainders and after the calculation of the remainders, their result is reconverted again into a “normal“ number.

The dialog offers multiplication, addition or subtraction of two numbers A and B as mathematical operation. In normal practice it is used, if the memory for the representation of large numbers and their intermediate results is not sufficient and to speed up calculations.

In comparison to conventional number notation the idea of the modular arithmetic consists in selecting t different modules m1, m2, …, mt , which are pairwise relatively prime and to perform the calculation on remainders x mod m1, x mod m2, ..., x mod mt instead of directly with the whole number x.

This is possible, because the modular representation uses the same arithmetic rules (addition, subtraction and multiplication). The range, that can be represented by modular arithmetic, goes from 0 to (m1 ∙ m2 ∙ … ∙ mt)-1.

This procedure has the additional advantage of allowing operations to be distributed to different computers and carrying them out in parallel.

Further details about modular arithmetic can be found in the CrypTool script , chapter 4.