# Multiplicative Generator

# Finding a Multiplicative Generator for $GF(2_{k})$

To find a generator of the multiplicative group $GF(2_{k})_{โ}$, which includes all nonzero elements of the field $GF(2_{k})$, 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 $x$ does not reside in any proper subgroup of $GF(2_{k})_{โ}$. The condition checked within the loop, $x_{d}๎=1$, ensures that $x$ has the maximal possible order, which is necessary for it to be a generator of the group.

## Background:

**Group Structure**: $GF(2_{k})_{โ}$ is the multiplicative group of the field $GF(2_{k})$, containing all field elements except 0. Its order is $2_{k}โ1$, which is prime to 2.**Maximal Proper Divisors**: These divisors are crucial as testing powers for these values ensures that $x$ is not a member of any smaller cyclic subgroup. The divisors of $2_{k}โ1$ 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 $GF(2_{16})_{โ}$, $โฃF_{โ}โฃ=2_{16}โ1=3ร5ร17ร257$
- For $GF(2_{32})_{โ}$, $โฃF_{โ}โฃ=2_{32}โ1=3ร5ร17ร257ร65537$
- For $GF(2_{64})_{โ}$, $โฃF_{โ}โฃ=2_{64}โ1=3ร5ร17ร257ร65537ร6700417$

# Maximal Proper Divisors

A maximal proper divisor of a number $n$ is a divisor $d$ of $n$ which is neither $1$ nor $n$ itself, and there are no other divisors of $n$ that divide $d$ except $1$ and $d$. Essentially, $d$ is a divisor that is not a multiple of any smaller divisor other than $1$ 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 $n$ involves identifying all divisors of $n$ and then selecting those which do not have other divisors besides $1$ and themselves. The steps are as follows:

**Find All Divisors**: First, list all divisors of $n$ by checking for every integer $i$ from $1$ to $nโ$ if $i$ divides $n$. If $i$ divides $n$, then both $i$ and $n/i$ are divisors.**Filter Maximal Divisors**: From this list of divisors, exclude $1$ and $n$. For each remaining divisor, check if it can be expressed as a multiple of any other divisor from the list (other than $1$ 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:
divisors.append(i)
if i != n / i:
divisors.append(n / i)
divisors.remove(1)
divisors.remove(n)
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
break
if is_maximal:
maximal_proper_divisors.append(d)
return maximal_proper_divisors
```