# Generators in Zp

(By Alyssa Vorpahl and Prof. Gregory V. Bard)

## Overview

This page will discuss what it means for a member of the group Z mod p to be a generator of that group.

## Discussion

You may recall from the previous interact that we discussed the idea of analyzing the sequence g0=1, g1=g, g2, g3, ... looking for repetitions, and how it led to the concept of 'generators'. For an element g in a group G to generate G, the following two equivalent statements must be true:

• Every element of the group G can be found in the sequence g0=1, g1=g, g2, g3, ... . Moreover, we can stop checking the first time there is any repetition in that sequence.
• For every integer i such that 0≤i≤Phi(p), we need gi to be a distinct value. Note, Phi(p) is the order of the group - the number of elements in the group.
• Note, for primes p, Phi(p)=p-1, so we always know the size of the group. In other cases it can be more complicated. For example, if N=pq where p and q are distinct primes, then Phi(N)=(p-1)(q-1). Also, if N = p2 the square of a prime, then Phi(N)=p(p-1).

In other words, gi must repeat itself at the last possible moment. Then, since there is a number of distinct gi's equal to the number of group elements, each element of the group can be written as gi for some i. Thus, by g being raised to increasing powers, the sequence g0=1, g1=g, g2, g3, ... has listed the entire group.

## Instructions

This app will allow you to select a base number (g) and the modulus (p). It will then raise g to each power between 0 and Phi(p), marking any repeated results. If there are no repeats, then it will notify you that the group element g is, in fact, a generator.

Also, notice that we refer to the modulus as p instead of N here. This is because we are only considering prime values for the modulus.

Once you load the applet, there will be two sliders: one to control the g value, and one to control the modulus p.

• g must be < p because it has to be an element of the group Zp.

Last modified by Alyssa Vorpahl on December 6th, 2018. Updated to Python 3 by Prof. Bard on April 7th, 2020.