| Discrete Log Calculator | Complex Discrete Logarithms |
| Residue Roots and CDLs | Complex Linear Congruence |
| Indexed Complex Discrete Logarithms | DLP solver for some primes |
This is an explanation of how to use Complex Discrete Logarithms to find residue roots. Possibly CDLs are an approximate superset of the complex number system that has been used on this problem. The python code used to generate the examples is here:
I had trouble keeping the variables associated with the CDLs straight, so I wrote a Python class, so I could reference the variables by name instead of as a position in an array. I put the variables with least possible states first in the class print function, but I will offer the explanation in the opposite order for ease of understanding.
| Variable | Explanation |
| num | This is simply the real number we used to calculate the CDL |
| vlg | This is the virtual logarithm. It is the solution to the linear congruence involved in the CDL as previously explained.. |
| exp | This is the exponent part of the CDL |
| rut | This is the primitive root part of the CDL. To calculate the value of the CDL in Python where xmxm is the product of the radices used for the CDL: (rut*(2**exp))%xmxm. |
| dif | If you multiply num by 2 mod xmxm, take the virtual log of the result and subtract the virtual log of num from the result, you get dif. CDLs that have the same dif will have the same sequence length. If dif is greater than one, that means that num is zero mod one or more of the radices used to generate the CDL. Or to put it another way, one or more of the digits of the residue number system representation of num are equal to zero. Since every number in the sequence has one of the radices as a factor, the number can be analyzed using all the radices except the ones that are zero. That requires calculating a new set of translation constants. That discussion is beyond the scope of this post |
Like most logarithms, CDLs are fairly easy to multiply and divide. Modular addition and subtraction handle the exponents, and modular multiplication and division handle the roots. The functions cmul and cdiv illustrate how this can be done. Of course, you can just multiply the num members of the CDLs and take a new CDL of the result, but there are times when understanding how to multiply and divide CDLs without translation is helpful.
To understand how to take residue roots using CDLs, it is helpful to understand some basic concepts about primitive roots.
By definition, the square of any primitive root is one.
The modular multiplication of two primitive roots is a primitive root.
If R=M-N where R is the residue complement of N with respect to M, then any two residue complement roots multiplied together equal M-1.
If the total range of a CDL is xmxm, then any number less than xmxm can be a member of one and only one of the sequences described by the CDL. Therefore sequences whose dif is 1 can only have even roots if rut is also equal to 1, and if exp is an even number.
Below are the modules used in the examples:
| [11, 19, 59, 83, 107, 179] |
The total range of a CDL using these modules is 19602578369.
The first function called is the example is: odrut(strt,trg). The first argument, strt, is simply any odd integer from 1 to the maximum range for the number of modules selected. The second argument, trg, describes the type of odd rut for which we are searching. In this example we are asking the odrut function to start with the number 4900644592 and search upward until it finds a number that has a dif of 1 and a 41st root, then calculate that root. If we specify a larger trg, the function is likely to scan through more candidates until it finds one that meets the specification.
| odrut |
| start 4900644592 |
| 4900644612=(12789887699^41)mod(19602578369) |
In this case the odrut function had to scan about 20 numbers before it found one with a 41st root.
The sqrut function works in a similar way, except that it is looking for a number that has a square root.
| sqrut |
| start 4900644592 |
| 4900644642=(7003801348^2)mod(19602578369) |
The sqrut function had to scan about 50 numbers to find one with a square root. The root shown is the one associated with the primitive root one. It seems likely that there would also be a square root associated with each of the other 63 primitive roots of this six module system.
There are many more questions to be investigated about CDLs. Any comments, criticisms, or bug reports will be appreciated.