In Discrete Logs, What Should g Be?

In Discrete Logs, What Should g Be?

In reading about cryptography, have you ever come across the term of a cyclic group G of order p and with a generator g? This article will hopefully explain what this means.

The world of public key encryption is currently dominated by two things: discrete logarithms and elliptic curve methods. RSA is becoming a thing of the past for new applications, but it is only hanging on as it has such a monopoly in digital certificates. And so with discrete logarithms and the Diffie-Hellman method we end up with:

Y = gˣ mod p

where we have a generator value (g) and a prime number p. The challenge is that even though we know Y, g and p, it is extremely difficult to determine the x value if we use a large prime number.

So can we use any value of g, and should it be as large as possible? The answer to both of these questions is no. If select a prime number of 7, and then select g values of 2, 3, 4 …9, and then calculate the results we get [spreadsheet]:

Now look at g=2, we get an output of 2, 4, 1, 2, 4 … for the sequence values of 1, 2, … This means that we do not get a unique output for the values from 1 to 6(where the maximum value will be six as we take the modulus of 7). But look at g=3, we get 3 (3¹ mod 7), 2 (3² mod 7), 6 (3³ mod 7), 4 (3⁴ mod 7), 5 (3⁵ mod 7), and 1 (3⁶ mod 7), which means that we get a unique value for all the possible outputs from 1 to 6, and which then repeats. For a prime number of 7, the valid values of g are 3 and 5.

But, in order to demonstrate the principle, I have done this is a long-handed way, so how do I find out all the possible values of G for a given prime number (p)? Well here’s a nice simple method in Python that I created to test up to p):

import sys
import random

p=11

def getG(p):

  for x in range (1,p):
	rand = x
	exp=1
	next = rand % p

	while (next <> 1 ):
		next = (next*rand) % p
		exp = exp+1
		

	if (exp==p-1):
		print rand

print getG(p)

Try and example:

So what are the G values for p=11?

2, 6, 7 and 8

A value of 2 or 3 is often used for g value, such as with the Diffie Hellman method. Overall this is defined as a cyclic group G of order p with a generator g.

Here is an example of how we can generate the g value based on the prime number:

Conclusions

Discrete logarithms are everywhere just now in public key methods, along with areas such as in zero knowledge proofs.