Damn! "phi" below should be "lambda": At 04:46 AM 12/28/2019, Henry Baker wrote:

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.

Sould be: lambda(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.