Residue Roots and CDLs

Discrete Log Calculator
Complex Discrete Logarithms
Residue Roots and CDLs
Unitary Prime Test

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:

rutx.txt

cons2.py.txt

Remove the .txt extensions before running the files under Python. This version of cons2.py only supports about 20 radices. It's easy enough to extend the range by generating a different constant file as previously explained.

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.