(Z/nZ)* — the multiplicative group of Z / nZ and Qn — the subgroup of squares in (Z/nZ)*

I published an article on a Discrete Logarithm of Equivalence:

Non-Interactive Proof of DLEQ using the Decision Diffie-Hellman (DDH) Assumption

Part of this is the selection of values from Qn and which is the subgroup of squares in (Z/nZ)*. Now let’s analyse.

Theory

The multiplicative group of integers modulo n is represented by ℤ∗n, and represents the numbers which do not share a factor with n. If n is a prime number, the values will range from 1 to n−1. If n=6, we have two factors of 2 and 3, and where ℤ∗6 will thus be {1,5}, and the other values share 2 or 3 as a factor. For Qn we represent with (Z/nZ)* is the subgroup of squares, and where we determine the valid values for x=y² (mod N) and where GCD(x,N)==1.

Let’s try n=10, and which has the prime factors of 2 and 5:

Computing Z_n (showing first 50) and Z^*_n
p=10
Z_10= {1, 2, 3, 4, 5, 6, 7, 8, 9}
Z*_10= [1, 3, 7, 9]
phi(n)= 4

In this case, φ is 4, as there are four elements in ℤ∗10. As 2, 4, 5, 6, and 8 share a factor with 10, they are not included in Z∗10. For a prime number, ℤ∗n will be the same as ℤn. For example, for n=13:

Computing Z_n (showing first 100) and Z^*_n…