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.
