I've been playing around with arithmetic mod a composite number, and I needed to extend discrete logs to the entire set -- not just those elements representable as g^i for some primitive root g. Consider, for example, Zn, for n = p*q = 47*59 = 2773. We also need phi(n) = lcm(p-1,q-1) = 46*58/2 = 1334. So we have 1334 elements in the multiplicative group. We also have another 1334 *negatives* of this group. We also have 58 powers of 47, and 46 powers of 59. Counting them up, we have 1334 1334 58 46 ---- 2772 non-zero elements of Zn. I.e., p*q = (p-1)*(q-1)+(p-1)+(q-1)+1 We can represent these elements as a quad*: [s,i,j,k] which represents the product (-1)^s * 47^i * (-59)^j * 2^k because "2" happens to be a generator/primitive root for the multiplicative group. (* Different composite n's may require more than 4 elements.) (We use -59 instead of 59 because -59 generates the full subgroup, while +59 only generates half of the subgroup.) Note also that we will never see i>0 and j>0 at the same time, because 47*59 = n = 0 (mod n). So we now define the discrete log of m in Zn to be log(m) = log((-1)^s*47^i*(-59)^j*2^k) = [s,i,j,k] Also, exp([s,i,j,k]) = (-1)^s*47^i*(-59)^j*2^k (mod n) So we can now do multiplications via logs: m1*m2 = exp(log(m1)+log(m2)) where "+" is element-wise addition. I'm certain that others have done this same thing before, but I don't recall seeing this representation.