| Discrete Log Calculator | Complex Discrete Logarithms |
| Residue Roots and CDLs | Complex Linear Congruence |
| Indexed Complex Discrete Logarithms | DLP solver for some primes |
The python script, invlog, was a step forward for me. It correctly calculated n for any member of the sequence x=2^n mod p given x and p where p is a number with factors small enough to store a discrete log table. That was good, but it was disappointing that it did not work for numbers less than p that were not in this sequence.
It turns out that in addition to the sequence 1*2^n mod p, there are also sequences of the for r*2^n mod p, and every number less than p must be a member of one and only one of these sequences. These r*2^n mod p sequences are the complex discrete logarithms.
Below is the result of that analysis on the number 12331, which is 11*18*59. There are 13 sequences with a total of 12330 entries.
| Length of sequences | Sequence count | Count times length | Sequence start | Sequence start factored | Sequence ratios | |||
| 10 | 1 | 10 | 1121 | 19*59 | 1 | |||
| 18 | 1 | 18 | 649 | 11*59 | 1 | |||
| 58 | 1 | 58 | 209 | 11*19 | 1 | |||
| 90 | 2 | 180 | 59 | 59 | 1 | 3 | ||
| 290 | 2 | 580 | 19 | 19 | 1 | 7 | ||
| 522 | 2 | 1044 | 11 | 11 | 1 | 3 | ||
| 2610 | 4 | 10440 | 1 | 1 | 1 | 3 | 7 | 21 |
In the bottom line of the chart, the Sequence start is one, and the sequence ratios are 1, 3, 7, and 21. That tells us there are four sequences 2610 entries long starting with 1, 3, 7, and 21.
In the second line from the bottom, the sequence start is 11 and the sequences ratios are 1 and three. That means there are two sequences 522 entries long starting with 11 and 33.
I got this data from my setana program which gives interesting results, but is very slow. To get results shortly after you enter them, the number p needs to be less than about 100,000.
I also have a very slow brute force complex log program, blog. Below are a couple of results from that program.
If x=r*(2^n) mod p:
| x | r | n | p |
| 24 | 3 | 3 | 12331 |
| 23 | 1 | 10 | 1001 |
I wanted to make a program that worked like the brute force blog, but was much faster. I called it clog, for complex logarithm. I was partially successful. Clog is much faster. It does a 300 decimal digit number in Python on my computer in about 40 milliseconds, and it does produce an answer that can be plugged into the complex log formula and produce the desired results. But setana gives us a total of 13 sequences for the number 12331, and a similar analysis using clog gives us well over a hundred sequences for the number 12331.
To put it another way, blog gives results that are completely unambiguous with no overlap of sequences. Clog gives ambiguous results with lots of sequence overlap. I'm guessing that I could disambiguate the clog algorithm in some small number of weeks, but I'm not sure that is my best next move.
Here is the top level Python function for the clog algorithm.
The variable, strt, would be n in the discrete log formula. The variable, xmxm is p. The function dudif uses ilg which is a function I have explained in previous posts. If we calculate ilg(strt) and ilg((strt*2)%xmxm), and subtract the two results, we get the difference that dudif is looking for. If gcd(strt,xmxm) is 1, then this difference will be one, and the sequence will with be the max for this xmxm, which in the case of 12331 is 2610. If not the sequence will be one of the shorter ones. The exact length of the short sequence is determined by the dudif difference and the max sequence length. The function dudif returns the output of ilg(strt) and the difference as discussed above.
The fnd function uses a linear congruence in the log domain to find the smallest result of the ilg algorithm that is in the sequence of which strt is a member. This is the part of the algorithm that can possibly be improved to reduce the level of ambiguity in clog.
The function, duof, uses the product of squares algorithm to compute xp, or r in the complex log formula, r*2^n mod p. The variable, locx, corresponds to the n in the formula.
The rest of the function just checks the results. So far it has not found any errors since I got the code working, but that has only been a few days.
I wrote a separate program, ducons, to compute the constants needed for this algorithm. To use ducons to get the constants:
ducons >cons.py
That will produce constants that give clog a range of about 350 decimal digits. You can change that in the ducons code, of course.
The algorithm could use other sets of radices, of course, or it could be designed for variable radices. This particular radix set is designed for maximum computational efficiency.
Below is a sample run of clog. We are asking clog to get a complex discrete log for 1000 using 10 radices.
The clog script tells us:
35723762789612788353*(2^ 168549820180347435) mod 286606661257088753537=1000
I have added the txt extension to the python source code to avoid downloading difficulties: