Computing signatures of logarithms and inverse trigonometrics

Computing signatures of logarithms is more complicated in the sense that we do not know how to compute them in time polynomial in the size of the problem. The signatures will be computed as

$$S_n(\log a) = \log_E( S_m(a) ) \pmod{n}$$

where n and m = kn+1 are primes, E=S_m(e)=p^k is the base of the exponential function and p is a primitive root (mod m). The $\log$ is the discrete logarithm, sometimes called the index function. It is defined by

$$\log_E b=c \pmod{n}\;\; \Longleftrightarrow \;\; E^c=b \pmod{m}$$

Notice the different ground fields on which we are computing here. This is similar to the $\exp$ function, where the exponent arithmetic was done on a different field, but in reverse.

If the signature of the argument is 0, we cannot compute the discrete logarithm. This is a case analogous to a division by zero, and we will proceed as with it. I.e. we will recursively test whether the argument is 0. If it is, then the computation does not make sense and it is aborted. If it is not, then we have found an n for which the signature is non-zero, and we continue the computation in this field.

With such a value for E, not being a primitive root, there will be discrete logarithms that will not be possible to compute. This problem is tricky to solve, but we can use the fact that the range of the discrete logarithm is normally 0 ... m-2, and we fold this range to 0 ... n-1. Let r=pⁿ, then r is a k^th root of unity, and $\log_pr=n$. Multiplying the arguments of the logarithms by any power of rwill not change their signature. If the base of the logarithms is p, then it is clear that

$$S_n(\log rx) = n+S_n(\log x) = S_n(\log x) \pmod{n}$$

In other words, the signatures of logarithms group values of the arguments in equivalence classes of size k. The generator of these classes of equivalence is r. When we compute discrete logarithms base E, then this class of equivalence will have one member having a logarithm, and all the others being not representable. We will use as a signature of any argument, the signature of any of the members of its equivalence class. It turns out that this is equivalent to computing the discrete logarithms as:

$$S_n( \log a ) = \frac{\log_p a}{k} \pmod{n}$$

A numerical example helps to understands all these computations and problems. Assume that n=13 and m=53 and hence k=4. Let p=2 which is a primitive root (mod 53). Then $E=S_{53}(e)=p^k=16 \pmod{53}$ and $r=p^n \pmod{53}=30$. We would like to prove that

$$\log 8e^9 = \log 8 + 9 \;\;\Longrightarrow\;\; S_n( \log S_m(8e^9) ) = S_n( \log S_m(8)) + 9$$

The signatures of the arguments are $S_m(8e^9) = 8E^9 = 23 \pmod{53}$and S_m(8)=8. Now, $\log_E8 \pmod{53}$ does not exist. I.e. there is no value c such that $E^c=8 \pmod{53}$. But 8 is in a class of equivalence $\{8,8r,8r^3,8r^3\} = \{8,28,45,25\} \pmod{53}$. Of the four components of this equivalence class, only 28 has a discrete logarithm base E, $\log_E28 = 4 \pmod{53}$. Similarly for 23, $\{23,23r,23r^3,23r^3\} = \{23,1,30,52\} \pmod{53}$, and only 1 has a logarithm, $\log_E1=0$. Notice that $\frac{\log_p8}{4} = 3/4 = 4 \pmod{13}$ and $\frac{\log_p23}{4} = 39/4 = 0 \pmod{13}$. This gives $0 = 4+9 \pmod{13}$ which verifies the initial equation.