| Discrete Log Calculator | Complex Discrete Logarithms |
| Residue Roots and CDLs | Complex Linear Congruence |
| Indexed Complex Discrete Logarithms | DLP solver for some primes |
The code is here:
ICDLS are an abbreviated version of Complex Discrete Logarithms (CDLs). Both are based on a residue arithmetic space defined by a series of prime modules. For a system of N modules, the CDL and ICDL systems have 2^N roots. Any residue number where each residue digit is either 1 or the module -1 is a root.
Some roots for the modules 11, 19, 59, and 83 are:
| 11 | 19 | 59 | 83 |
| 1 | 1 | 1 | 82 |
| 10 | 18 | 58 | 1 |
To derive an ICLD from a CLD we need to correlate the possible digits to the binary digits 0 and 1. There are two ways to do this. Here we will use:
| Residue | Binary |
| -1 | 1 |
| 1 | 0 |
Assuming we have 4 modules, the root index is a 4 bit binary number derived from the residue arithmetic representation of the root using the above binary mapping.
Thus 1,1,1,82 residue would translate as 0001 binary.
10,18,58,1 residue would translate as 1110 binary.
Here is a residue multiplication table for a single digit of a root:
| arg0 | arg1 | product |
| -1 | -1 | 1 |
| -1 | 1 | -1 |
| 1 | -1 | -1 |
| 1 | 1 | 1 |
Map that table to binary:
| arg0 | arg1 | product |
| 1 | 1 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
That is the truth table for the exclusive or function, and that means that the indices of the ICDL can be multiplied using a single bit-wise exclusive or instruction. That can replace the integer multiplication and division required to do a modular multiply of the CDL root.
It also seems that you can divide ICDLs using exactly the same bit-wise or function. Use the exclusive or instruction on the index, but use addition of the exponents for the multiply, and subtraction to divide ICDLs.
Below is a printout from the code associated with this article:
|
Residue range: 1023473 Modules: [11, 19, 59, 83] multiply 149088*465605=85488 (1,14,24424)*(1,4,18053)=(1,10,42477)=85488 749140*443690=788174 (1,3,43482)*(1,1,33589)=(1,2,77071)=788174 818799*545410=1000716 (1,6,33458)*(1,7,32528)=(1,1,65986)=1000716 divide 149088/465605=192194 (1,14,24424)/(1,4,18053)=(1,10,6371)=192194 749140/443690=881680 (1,3,43482)/(1,1,33589)=(1,2,9893)=881680 818799/545410=434598 (1,6,33458)/(1,7,32528)=(1,1,930)=434598 |
The program does residue multiplication and division for three sets of operands. First the results of doing the residue division the standard way are shown, and then the two operands are translated into ICDLs and multiplied using the exclusive or technique and modular addition or subtraction on the exponents of the ICDLs. The results translated into decimal are shown to the right of each line. The only difference between the ICDL multiplication and division is that multiplication uses modular addition on the exponents, and division uses modular subtraction on the exponent.
Because of the overhead of translating to and from ICDLs, this technique would be most useful for situations where several multiply operations could be chained.