Multiplicative Generator

Finding a Multiplicative Generator for

To find a generator of the multiplicative group , which includes all nonzero elements of the field , a probabilistic method is used. This method iteratively tests random elements to determine if they are generators of the group. The process is summarized below.

Probabilistic Method Algo

while true:
    # sample random nonzero element x
    for each maximal proper divisor d of |๐”ฝ*|:
        if xแตˆ == 1: continue
    return x

This algorithm ensures that the element does not reside in any proper subgroup of . The condition checked within the loop, , ensures that has the maximal possible order, which is necessary for it to be a generator of the group.


  • Group Structure: is the multiplicative group of the field , containing all field elements except 0. Its order is , which is prime to 2.
  • Maximal Proper Divisors: These divisors are crucial as testing powers for these values ensures that is not a member of any smaller cyclic subgroup. The divisors of are used to verify the generator property.
  • Probabilistic Success Rate: The likelihood of a random element being a generator is significant, given the structure of the group. This can be supported by the [[chinese-remainder-theorem]], which suggests that the intersection of several smaller groups (subgroups corresponding to divisors) is likely non-trivial only when all subgroup conditions are simultaneously satisfied.

Example Divisors:

  • For ,
  • For ,
  • For ,

Maximal Proper Divisors

A maximal proper divisor of a number is a divisor of which is neither nor itself, and there are no other divisors of that divide except and . Essentially, is a divisor that is not a multiple of any smaller divisor other than and itself, making it 'maximal' under the set of proper divisors.

Algorithm for Finding

The algorithm to find the maximal proper divisors of a given number involves identifying all divisors of and then selecting those which do not have other divisors besides and themselves. The steps are as follows:

  1. Find All Divisors: First, list all divisors of by checking for every integer from to if divides . If divides , then both and are divisors.
  2. Filter Maximal Divisors: From this list of divisors, exclude and . For each remaining divisor, check if it can be expressed as a multiple of any other divisor from the list (other than and itself). If it cannot, then it is a maximal proper divisor.
function findMaximalProperDivisors(n):
    divisors = []
    for i from 1 to sqrt(n):
        if n % i == 0:
            if i != n / i:
                divisors.append(n / i)

    maximal_proper_divisors = []
    for d in divisors:
        is_maximal = true
        for e in divisors:
            if d != e and e != 1 and d % e == 0:
                is_maximal = false
        if is_maximal:

    return maximal_proper_divisors