Complex Linear Congruence

The linear congruence suffers from a major defect. It only works on sets of mutually prime modules. But if any two of the desired modules have a common factor, it will not work. I set out to create an algorithm that computed results even when there were common factors.

The complex linear congruence, CLC, is the result of that effort It works on modules with common factors and also sets of modules where some of the modules are duplicates. Those who think in terms of the residue number system, RNS, could call this CLC a complex RNS. The CLC is not as simple as the mutually prime linear congruence, or the plain RNS, but it does convert numbers from polynomial to residue and back using fast linear algorithms.

The CLC uses multiple sets of mutually prime modules to compute its results. Here is the result of a sample run:

These are the modules we will use. The last three modules and the first three are duplicates:

[71, 83, 18, 99, 19, 67, 9, 71, 83, 18]

This is the same list of modules separated into mutually prime groups:

[71, 83, 18, 19, 67] 135032202
[99, 71, 83] 583407
[9] 9
[18] 18

The number at the end of a module list is the product of all the modules in that list.

This is the result of translating the decimal number 1,000,000,000 into the complex RNS.

[[3, 64, 10, 18, 9], [7, 7, 7]]

The program only needed the first two lists of mutually prime modules to express that number.

The code demonstrates that the complex residue number translates back into decimal.

The total range of the whole CLC is:

12762154563298668

That number minus 1 is:

12762154563298667

Below is 12762154563298667 in complex RNS notation:

[[70, 82, 17, 18, 66], [98, 70, 82], [8], [17]]

As expected, all the residue digits equal their respective modules minus one.

The complex linear congruence uses the mixed-radix concept to provide ordering. Any RNS has an associated mixed radix number system with the same range as the RNS. In essence the RNS is translated into mixed radix notation and then to decimal, hex, octal, binary or etc. The complex RNS also uses a mixed radix number system that is mapped into to the total range of the complex RNS.

In trying to correlate RNS systems to discrete logs, I kept having to deal with sets of modules that were not mutually prime. This is my attempt to solve that problem.

Now I hope to be able to correlate complex residue number systems to complex discrete log systems.

Here is the code:

upt.txt