| Discrete Log Calculator | Complex Discrete Logarithms |
| Residue Roots and CDLs | Complex Linear Congruence |
| Indexed Complex Discrete Logarithms | DLP solver for some primes |
If N is 2 to the L, and R is the remainder of N divided by Q, this program can compute L from the remainder R. Q is restricted to a product of primes Pn such that series 2^n mod Pn must have a length of Pn-1. Possibly, it could be generalized so that Q could be any number, but that is not covered here.
The first few primes that meet that condition are: [5, 11, 13, 29, 53, 59, 67, 83]
The algorithm requires another set of radices: [4, 5, 3, 7, 13, 29, 11, 41]. I have been calling these log radices.
Each log radix is associated with a prime radix. Each log radix is derived from the associated prime radix by first subtracting one, and then dividing the subtracted radix by any common factors with the product of all previously assigned log radices. 4 is 5-1. 5 is 11-1 divided by the common factor two. 3 is 13-1 divided by the common factor 4, and so on. Occasionally this process yields a log radix that is already in the list of log radices. In that case, either the new prime radix, or the previous prime radix can be used, but not both. This is all done so the log radices can be mutually prime.
The effective range of the algorithm is restricted to the product of the log radices used. Below is a table with the first few ranges.
| rads | range |
| 0 | 1 |
| 1 | 4 |
| 2 | 20 |
| 3 | 60 |
| 4 | 420 |
| 5 | 5,460 |
| 6 | 158,340 |
| 7 | 1,741,740 |
If we use the three radices 5, 11, and 13, range of that residue number system is 715. But the algorithm requires an associated residue number system which in this case has a range of only 60, covering the powers of two up to around 2 to the 60. The program will output the power of two needed to produce those numbers. 2^30 is 1,073,741,824. That number is 4 mod 5, 1 mod 11, and 12 mod 13. Using that information the program calculates that the power of two required is 30.
So with a 3 radices we can go to 2^60. Four radices can go to 2^420, and 7 radices takes us to 2^1,741,740. With the constants supplied, the program has a range of a little greater than two to the ten to the 500th power, or 2**(10**500) in python notation.
The function that actually does the conversion from residue to logarithmic residue, durut(res), is quite simple. It looks up the appropriate discrete logarithm for each residue digit, and then disambiguates that logarithm by taking it's modulus with respect to the associated logarithmic radix.
The function ilgr(pres) takes the residue coded input and finds the appropriate exponent encoded in logarithmic radices. The function ilg(val) is a convenience function that extracts the necessary residue digits from the large power of two. In a real world application of this principle, if any such will ever exist, the residue digits would be derived from some mechanism dictated by the requirements of the intended use.
The function, chk(), prints out the input exponent and the output exponent as as calculated by ilg. The two numbers should be the same over the range. This is much too slow for larger ranges, of course.
The functions shodif and dif illustrate the organization of the series created by running ilg over a series of integers. I'll save the long winded explantions until someone shows an interest. The code is set up to print out that series for three radices. Change the variable, lim, in the source code for a different number of radices.
Click the link below to get the source. I changed the extension to .txt to disable the Python warning.