SharedCrypto_Fall_19 / slides / day18 / cyclic_groups.sagewsOpen in CoCalc
Author: Hunter Johnson
Views : 17
Description: Cryptography lesson on cyclic groups

### Group theory

Recall the definition of a group:

https://en.wikipedia.org/wiki/Group_(mathematics)#Definition

There are tons and tons of groups.

Some are infinite and some are finite.

Cryptography is mostly concerned with finite groups.

### Common groups in cryptography

• $\mathbb{Z}_n$ is addition modulo $n$.
• $\mathbb{Z}_n^*$ is multiplication modulo $n$ on elements coprime to $n$.
• The multiplicative part of $GF(p^k)$.
• Elliptic curve groups.

When we talk about a generic group $G$ we will sometimes think of the operation as being multiplication.

Other times we will think of it as being more like addition.

Additive notation: $(G,+)$

• The identity is 0
• The inverse of $a$ is $-a$
• $na = \underbrace{a+a+a+\cdots+a}_{n\,times}$.
• The DLP: Solve for $n$ in the equation: $na = b$.

When we talk about a generic group $G$ we will sometimes think of the operation as being multiplication.

Other times we will think of it as being more like addition.

Multiplicative notation: $(G,\cdot)$

• The identity is 1
• The inverse of $a$ is $a^{-1}$
• $a^n = \underbrace{a\cdot a \cdot a \cdots a}_{n\,times}$.
• The DLP: Solve for $n$ in the equation: $a^n = b$.

### The order of an element

Given $a$ in $G$, the order of $a$ is the smallest positive integer $k$ such that $a^k = 1$.

G = Zmod(397)
g = G.random_element()
g

198
g.multiplicative_order()

44
for k in range(g.multiplicative_order()+1):
print("g^{:2} = {:3}".format(k,g^k))

g^ 0 = 1 g^ 1 = 198 g^ 2 = 298 g^ 3 = 248 g^ 4 = 273 g^ 5 = 62 g^ 6 = 366 g^ 7 = 214 g^ 8 = 290 g^ 9 = 252 g^10 = 271 g^11 = 63 g^12 = 167 g^13 = 115 g^14 = 141 g^15 = 128 g^16 = 333 g^17 = 32 g^18 = 381 g^19 = 8 g^20 = 393 g^21 = 2 g^22 = 396 g^23 = 199 g^24 = 99 g^25 = 149 g^26 = 124 g^27 = 335 g^28 = 31 g^29 = 183 g^30 = 107 g^31 = 145 g^32 = 126 g^33 = 334 g^34 = 230 g^35 = 282 g^36 = 256 g^37 = 269 g^38 = 64 g^39 = 365 g^40 = 16 g^41 = 389 g^42 = 4 g^43 = 395 g^44 = 1
## The order of g is the size of the set it can generate

len(set([g^k for k in range(G.order())]))

44
euler_phi(397)/44

9
## The order of g divides |G|

euler_phi(397)%g.multiplicative_order()

0

### Cyclic groups

The group $G$ is cyclic if it contains an element of order $|G|$.

In other words some single element generates $G$.

There is some $\alpha \in G$ such that every $\beta \in G$ is $\alpha^x$ for some index $x$.

### Theorem

For every prime $p$, the group $(\mathbb{Z}_p^*,\cdot)$ is a finite cyclic group.

## Empirical check:
r = randint(0,2193821983798217)
p = next_prime(r)
G = Zmod(p)
G.multiplicative_group_is_cyclic()

True
## Not true for all composite numbers:

Zmod(8).multiplicative_group_is_cyclic()

False

def show_orders(n):
"""Print the orders of the elements of Z_n^*"""
print("The multiplicative orders of the elements of Z_{}".format(n))
for g in Zmod(n):
if gcd(g,n) != 1:
continue
print("the order of {} is {}".format(g,g.multiplicative_order()))

show_orders(19)

The multiplicative orders of the elements of Z_19 the order of 1 is 1 the order of 2 is 18 the order of 3 is 18 the order of 4 is 9 the order of 5 is 9 the order of 6 is 9 the order of 7 is 3 the order of 8 is 6 the order of 9 is 9 the order of 10 is 18 the order of 11 is 3 the order of 12 is 6 the order of 13 is 18 the order of 14 is 18 the order of 15 is 18 the order of 16 is 9 the order of 17 is 9 the order of 18 is 2

### Theorem

For every element $g$ of a finite group $G$, the order of $g$ divides $|G|$.

#### Proof:

Let $g \in G$ be given:

$\displaystyle \prod_{a \in G} a = \prod_{a \in G} ga = g^{|G|} \prod_{a\in G} a$

Therefore

$1 = g^{|G|}$

This implies that the order of $g$ divides $|G|$.

It also generalizes FLT to finite groups.

### Theorem

Let $G$ be a finite cyclic group. Then

1. The number of primitive elements of $G$ is $\varphi(|G|)$.
2. If $|G|$ is prime, then all elements $a \neq 1$ in $G$ are primitive.
p = next_prime(293847)
G = Zmod(p)
generators = [g for g in G if g != 0 and g.multiplicative_order()==p-1]
len(generators) == euler_phi(p-1)

True

Note that if $p$ is prime then $|\mathbb{Z}_p^*| = p-1$ is never prime.

But when $p$ is prime and $G=\mathbb{Z}_p$, then $|G|=p$, and any element is a generator.

# Any element is a generator of the additive group Z_p
n=7
r = randint(1,7)
for g in range(1,7):
print((g*r)%n)

4 1 5 2 6 3

### Subgroups

A subgroup is a subset of a group that is closed under the group operation.

#### Example of a subgroup

The powers of $7$ are a subgroup of the group $\mathbb{Z}_n^*$, whenever $\gcd(7,n)=1$.

Check closure:

Let $7^j$ and $7^k$ be two powers of 7 mod $n$ for integers $j,k$.

Then

$7^j\cdot 7^k \equiv 7^{j+k} \mod n$.

But $7^{j+k}$ is obviously a power of $7$.

Therefore the powers of 7 are closed under the group operation.

Therefore the powers of 7 form a subgroup.

In the above example there is nothing special about 7 (or even $\mathbb{Z}_n^*$) and so we get the following theorem of group theory:

#### Theorem: Cyclic subgroup theorem

Let $(G,\circ)$ be a finite group. Then every element $a \in G$ with $ord(a)=s$ is the generator of a cyclic subgroup with $s$ elements.

Proof:

In our subgroup example, replace $\mathbb{Z}_n^*$ with $G$ and $7$ with $a$.

### Enumerating all cyclic subgroups

It's possible for two different elements of $G$ to generate the same cyclic subgroup.

Here is an example of that happening.

## Enumerate all cyclic subgroups of Z_n^*

n = 16
G = Zmod(n)
print("Working modulo {}".format(n))
for a in range(n):
if gcd(a,n) != 1:
continue
print("The subgroup generated by {} is:".format(a))
subgroup = [power_mod(a,k,n) for k in range(G(a).multiplicative_order())]
print(sorted(subgroup))

Working modulo 16 The subgroup generated by 1 is: [1] The subgroup generated by 3 is: [1, 3, 9, 11] The subgroup generated by 5 is: [1, 5, 9, 13] The subgroup generated by 7 is: [1, 7] The subgroup generated by 9 is: [1, 9] The subgroup generated by 11 is: [1, 3, 9, 11] The subgroup generated by 13 is: [1, 5, 9, 13] The subgroup generated by 15 is: [1, 15]

### Observation

Notice that the group $\mathbb{Z}_{16}^*$ is not cyclic.

Also observe that some distinct subgroups have the same cardinality.

An example of this is $H=\{1,9\}$ and $K=\{1,15\}$.

We will see below that in a cyclic group this never happens: No two distinct subgroups have the same cardinality in a cyclic group.

### Studying cyclic subgroups

In the above example where $n=16$, you can see that 3 and 11 generate the same subgroup.

This happens because 3 is itself a primitive element of the subgroup generated by 11 (and vice versa).

Observe that the intersection of two subgroups is always a subgroup!

$\mathbb{Z}_{16}^*$ is not cyclic and so no subgroup is equal to the whole group.

But the whole group is always a subgroup of itself.

Let's try the same experiment with a cyclic group.

## Enumerate all cyclic subgroups of Z_n^*

n = 23
G = Zmod(n)
print("Working modulo {}".format(n))
for a in range(n):
if gcd(a,n) != 1:
continue
print("The subgroup generated by {} is:".format(a))
subgroup = [power_mod(a,k,n) for k in range(G(a).multiplicative_order())]
print(sorted(subgroup))

Working modulo 23 The subgroup generated by 1 is: [1] The subgroup generated by 2 is: [1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18] The subgroup generated by 3 is: [1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18] The subgroup generated by 4 is: [1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18] The subgroup generated by 5 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22] The subgroup generated by 6 is: [1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18] The subgroup generated by 7 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22] The subgroup generated by 8 is: [1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18] The subgroup generated by 9 is: [1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18] The subgroup generated by 10 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22] The subgroup generated by 11 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22] The subgroup generated by 12 is: [1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18] The subgroup generated by 13 is: [1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18] The subgroup generated by 14 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22] The subgroup generated by 15 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22] The subgroup generated by 16 is: [1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18] The subgroup generated by 17 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22] The subgroup generated by 18 is: [1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18] The subgroup generated by 19 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22] The subgroup generated by 20 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22] The subgroup generated by 21 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22] The subgroup generated by 22 is: [1, 22]

In the above example we saw that most subgroups of $\mathbb{Z}_{23}^*$ are big.

That is because the orders of the elements determine the orders of the subgroups.

So any subgroup must be a size that divides $23-1 = 22$.

But $23$ is a safe prime because $22=2\cdot11$ ($p-1$ is twice a prime).

The point of a safe prime is exactly that $\mathbb{Z}_p^*$ only has big subgroups (except for the unique subgroup of size 2, $\{1,-1\}$).

Let's try the same experiment with an "unsafe" prime.

## Enumerate all cyclic subgroups of Z_n^*

n = 37
G = Zmod(n)
print("Working modulo {}".format(n))
for a in range(n):
if gcd(a,n) != 1:
continue
print("The subgroup generated by {} is:".format(a))
subgroup = [power_mod(a,k,n) for k in range(G(a).multiplicative_order())]
print(sorted(subgroup))

Working modulo 37 The subgroup generated by 1 is: [1] The subgroup generated by 2 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The subgroup generated by 3 is: [1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36] The subgroup generated by 4 is: [1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36] The subgroup generated by 5 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The subgroup generated by 6 is: [1, 6, 31, 36] The subgroup generated by 7 is: [1, 7, 9, 10, 12, 16, 26, 33, 34] The subgroup generated by 8 is: [1, 6, 8, 10, 11, 14, 23, 26, 27, 29, 31, 36] The subgroup generated by 9 is: [1, 7, 9, 10, 12, 16, 26, 33, 34] The subgroup generated by 10 is: [1, 10, 26] The subgroup generated by 11 is: [1, 10, 11, 26, 27, 36] The subgroup generated by 12 is: [1, 7, 9, 10, 12, 16, 26, 33, 34] The subgroup generated by 13 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The subgroup generated by 14 is: [1, 6, 8, 10, 11, 14, 23, 26, 27, 29, 31, 36] The subgroup generated by 15 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The subgroup generated by 16 is: [1, 7, 9, 10, 12, 16, 26, 33, 34] The subgroup generated by 17 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The subgroup generated by 18 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The subgroup generated by 19 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The subgroup generated by 20 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The subgroup generated by 21 is: [1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36] The subgroup generated by 22 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The subgroup generated by 23 is: [1, 6, 8, 10, 11, 14, 23, 26, 27, 29, 31, 36] The subgroup generated by 24 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The subgroup generated by 25 is: [1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36] The subgroup generated by 26 is: [1, 10, 26] The subgroup generated by 27 is: [1, 10, 11, 26, 27, 36] The subgroup generated by 28 is: [1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36] The subgroup generated by 29 is: [1, 6, 8, 10, 11, 14, 23, 26, 27, 29, 31, 36] The subgroup generated by 30 is: [1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36] The subgroup generated by 31 is: [1, 6, 31, 36] The subgroup generated by 32 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The subgroup generated by 33 is: [1, 7, 9, 10, 12, 16, 26, 33, 34] The subgroup generated by 34 is: [1, 7, 9, 10, 12, 16, 26, 33, 34] The subgroup generated by 35 is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36] The subgroup generated by 36 is: [1, 36]

In the case of $p=37$, $p-1=36$ has lots of divisors.

For that reason it has many subgroups, and some of them are too small to be safe from brute force on DLP.

The following is an interesting group theoretic fact that is true even when $G$ and $H$ are not cyclic:

### Theorem (Lagrange's Theorem)

Let $H$ be a subgroup of $G$. Then $|H|$ divides $|G|$.

Proof sketch

Sets of the form $gH = \{gh: h \in H\}$ partition $G$.

### Cyclic Subgroup Theorem:

Let $G$ be a finite cyclic group of order $n$ and let $\alpha$ be a generator of $G$.

Then for every integer $k$ that divides $n$ there exists exactly one cyclic subgroup $H$ of $G$ of order $k$.

This subgroups is generated by $\alpha^{n/k}$.

$H$ consists exactly of the elements $a \in G$ that satisfy $a^k = 1$.

There are no other subgroups.

## Sage example

p = 101
G = Zmod(p)
alpha = G.multiplicative_generator()
alpha

2
divisors(p-1)

[1, 2, 4, 5, 10, 20, 25, 50, 100]
for k in divisors(p-1):
generator = alpha^((p-1)//k)
subgroup = [generator^j for j in range(generator.multiplicative_order())]
print("The following subgroup has generator = {} = alpha^{}  (n={} and k={})".format(generator,(p-1)//k,p-1,k))
print(sorted(subgroup))

The following subgroup has generator = 1 = alpha^100 (n=100 and k=1) [1] The following subgroup has generator = 100 = alpha^50 (n=100 and k=2) [1, 100] The following subgroup has generator = 10 = alpha^25 (n=100 and k=4) [1, 10, 91, 100] The following subgroup has generator = 95 = alpha^20 (n=100 and k=5) [1, 36, 84, 87, 95] The following subgroup has generator = 14 = alpha^10 (n=100 and k=10) [1, 6, 14, 17, 36, 65, 84, 87, 95, 100] The following subgroup has generator = 32 = alpha^5 (n=100 and k=20) [1, 6, 10, 14, 17, 32, 36, 39, 41, 44, 57, 60, 62, 65, 69, 84, 87, 91, 95, 100] The following subgroup has generator = 16 = alpha^4 (n=100 and k=25) [1, 5, 16, 19, 24, 25, 31, 36, 37, 52, 54, 56, 58, 68, 71, 78, 79, 80, 81, 84, 87, 88, 92, 95, 97] The following subgroup has generator = 4 = alpha^2 (n=100 and k=50) [1, 4, 5, 6, 9, 13, 14, 16, 17, 19, 20, 21, 22, 23, 24, 25, 30, 31, 33, 36, 37, 43, 45, 47, 49, 52, 54, 56, 58, 64, 65, 68, 70, 71, 76, 77, 78, 79, 80, 81, 82, 84, 85, 87, 88, 92, 95, 96, 97, 100] The following subgroup has generator = 2 = alpha^1 (n=100 and k=100) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]

### Safe primes again

Okay, so what are the subgroups of a safe prime?

Recall that $p$ is safe if $p-1 = 2q$ where $q$ is prime.

You can see from the definition that the only divisors of $p-1$ are 1, 2, $q$, and $p-1$.

Let's see an example.


def next_safe_prime(n):
n = next_prime(n)
while True:
if is_prime((n-1)//2):
break
n = next_prime(n+1)
print(n,factor(n-1))
return n

next_safe_prime(100)

(103, 2 * 3 * 17) (107, 2 * 53) 107
p = 107
G = Zmod(p)
alpha = G.multiplicative_generator()
alpha

2
divisors(p-1)

[1, 2, 53, 106]
for k in divisors(p-1):
generator = alpha^((p-1)//k)
subgroup =   [generator^j for j in range(generator.multiplicative_order())]
print("The following subgroup has generator = {} = alpha^{}  (n={} and k={})".format(generator,(p-1)//k,p-1,k))
print(sorted(subgroup))

The following subgroup has generator = 1 = alpha^106 (n=106 and k=1) [1] The following subgroup has generator = 106 = alpha^53 (n=106 and k=2) [1, 106] The following subgroup has generator = 4 = alpha^2 (n=106 and k=53) [1, 3, 4, 9, 10, 11, 12, 13, 14, 16, 19, 23, 25, 27, 29, 30, 33, 34, 35, 36, 37, 39, 40, 41, 42, 44, 47, 48, 49, 52, 53, 56, 57, 61, 62, 64, 69, 75, 76, 79, 81, 83, 85, 86, 87, 89, 90, 92, 99, 100, 101, 102, 105] The following subgroup has generator = 2 = alpha^1 (n=106 and k=106) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106]

### Safe primes

You can see from the above output that the only really dangerous base for the DLP in this group is the element of order 2.

The number of bits in $q$ is only one less than $p$, so even if the base is in the subgroup of size $q$, this is okay.

And it's really easy to check whether $\alpha$ has order 2:

Just see if $\alpha^2 = 1$.

And since $p$ is prime this is only true for $\alpha = p-1$.

It's similarly easy to see if the order of $\alpha$ is $q$.

Thus for a safe prime we can find a verifiable generator.

### Diffie Helman in openssl

Below we will verify that the Diffie Hellman parameters produced by OpenSSL yield a safe prime.

Because of this fact generating DH params takes much longer than RSA params, even if the bit length is the same.

[email protected]:~/.ssh$openssl dhparam -out dh.pem 512 Generating DH parameters, 512 bit long safe prime, generator 2 This is going to take a long time ......................................................+......................+........++*++*++*++*++* [email protected]:~/.ssh$ openssl dhparam -text -in dh.pem
DH Parameters: (512 bit)
prime:
00:e2:e8:54:d3:75:f1:0a:2d:90:c1:5d:54:82:1e:
b5:75:f7:23:06:41:7c:d3:d9:23:9c:39:b7:ae:fb:
a0:eb:9d:be:93:da:65:0a:ea:13:84:49:eb:04:11:
cc:fa:2d:36:43
generator: 2 (0x2)
-----BEGIN DH PARAMETERS-----
MEYCQQDi6FTTdfEKLZDBXVSCHrV19yMGQXzT2SOcObeu+6Drnb6T2mUK6hOESesE
Ea3c3GJBKqqSu1ICoDcUC8z6LTZDAgEC
-----END DH PARAMETERS-----




p = """00:e2:e8:54:d3:75:f1:0a:2d:90:c1:5d:54:82:1e:
b5:75:f7:23:06:41:7c:d3:d9:23:9c:39:b7:ae:fb:
a0:eb:9d:be:93:da:65:0a:ea:13:84:49:eb:04:11:
cc:fa:2d:36:43"""
p = p.replace(':','').replace('\n','').replace('\t','').replace(' ','')
p = int(p,16)
p

11884112392174931525551803878284316468547743675014443360835956479033078578449820213217260145091693859837332463855747972651088419742292198211998500015388227L
is_prime(p)

True
q = (p-1)//2
q

5942056196087465762775901939142158234273871837507221680417978239516539289224910106608630072545846929918666231927873986325544209871146099105999250007694113
is_prime(q)

True
G=Zmod(p)
alpha = G(2)
alpha^(q)

11884112392174931525551803878284316468547743675014443360835956479033078578449820213217260145091693859837332463855747972651088419742292198211998500015388226

### Safe prime

In the above experiment $\alpha^q = p-1$.

Thus we can be sure that the order of $\alpha$ is $p$, because if it were in the subgroup of size $q$ its order would have to divide $q$.

But in that case we would have observed $\alpha^q =1$.

### The general DLP

The DLP is a problem that can be stated in any group (not just our simple "mod p") groups.

### Definition: The Generalized Discrete Logarithm Problem

Given is a finite cyclic group $G$ with the group operation $\circ$ and cardinality $n$.

We consider a primitive element $\alpha \in G$ and another element $\beta \in G$.

The DLP is finding the integer $x$ where $1 \leq x \leq n$ such that :

$\beta = \underbrace{\alpha\circ \alpha \circ \cdots \circ \alpha}_{x\, times} = \alpha^x$

### Elliptic Curve groups

In particular you can have the DLP in an elliptic curve group.

We won't give the details for this.

But: If we use DLP in $\mathbb{Z}_p^*$ and also DLP in elliptic curve groups, why are the keys for elliptic curve groups so much shorter?

We've seen that for elliptic curves, 256 bits gives 128 bit security, while for $\mathbb{Z}_p^*$ we need about 3000 bits.

Why is one group vulnerable to DLP attacks and the other group not?

### Index calculus

The main reason key sizes for elliptic curve groups are smaller is that $\mathbb{Z}_p^*$ is vulnerable to an attack called the index calculus.

Again, we won't go into the details, but you can study this on your own if you want.

No one knows of any way to apply this attack to the DLP in elliptic curve groups.

There is some speculation however that the parameters for elliptic curve groups are backdoored by NSA.

However if this is true, they have not yet bothered to destroy any of the dozens of cryptocurrencies based on a NIST curve.

### Below we use Sage to investigate an elliptic curve E with 10 elements.

### We show that (0:7:1) is a generator.
### Note that elliptic curve groups use additive notation.


E=EllipticCurve(GF(11),[2,5])
E

Elliptic Curve defined by y^2 = x^3 + 2*x + 5 over Finite Field of size 11
E.cardinality()

10
g = E.an_element()
g

(0 : 7 : 1)
2*g

(9 : 9 : 1)
3*g

(3 : 7 : 1)
4*g

(8 : 4 : 1)
5*g

(4 : 0 : 1)
6*g

(8 : 7 : 1)
7*g

(3 : 4 : 1)
8*g

(9 : 2 : 1)
9*g

(0 : 4 : 1)
10*g

(0 : 1 : 0)

### Cyclic group theorem applied to elliptic curves...

The Cyclic Group theorem still applies to $E$ even though $E$ is "weird".

That's because the theorem applies to any cyclic group, no matter how weird.



for g in E:
print("The order of {} is {}".format(g,g.order()))

The order of (0 : 1 : 0) is 1 The order of (0 : 4 : 1) is 10 The order of (0 : 7 : 1) is 10 The order of (3 : 4 : 1) is 10 The order of (3 : 7 : 1) is 10 The order of (4 : 0 : 1) is 2 The order of (8 : 4 : 1) is 5 The order of (8 : 7 : 1) is 5 The order of (9 : 2 : 1) is 5 The order of (9 : 9 : 1) is 5
euler_phi(10)

4
alpha = E.an_element()
for k in divisors(10):
generator = (10//k)*alpha
subgroup =   [j*generator for j in range(generator.order())]
print("The following subgroup has generator = {} = {}*alpha   (n={} and k={})".format(generator,(10//k),10,k))
print(sorted(subgroup))

The following subgroup has generator = (0 : 1 : 0) = 10*alpha (n=10 and k=1) [(0 : 1 : 0)] The following subgroup has generator = (4 : 0 : 1) = 5*alpha (n=10 and k=2) [(0 : 1 : 0), (4 : 0 : 1)] The following subgroup has generator = (9 : 9 : 1) = 2*alpha (n=10 and k=5) [(0 : 1 : 0), (8 : 4 : 1), (8 : 7 : 1), (9 : 2 : 1), (9 : 9 : 1)] The following subgroup has generator = (0 : 7 : 1) = 1*alpha (n=10 and k=10) [(0 : 1 : 0), (0 : 4 : 1), (0 : 7 : 1), (3 : 4 : 1), (3 : 7 : 1), (4 : 0 : 1), (8 : 4 : 1), (8 : 7 : 1), (9 : 2 : 1), (9 : 9 : 1)]

### The cyclic group theorem applied to $GF(2^8)$

It turns out Galois Fields are cyclic. paper

n = 256

G = GF(n,'x')
alpha = [f for f in G if f != 0 and f.multiplicative_order()==n-1][0]  ## Get a generator
print("alpha = {}, alpha.order() = {}".format(alpha,alpha.multiplicative_order()))
for k in divisors((n-1)):
generator = alpha^((n-1)//k)
subgroup =   [generator^j for j in range(generator.multiplicative_order())]
print("The following subgroup has generator = {} = alpha^{}   (|G|={} and k={})".format(generator,((n-1)//k),(n-1),k))
print(sorted(subgroup))

alpha = x, alpha.order() = 255 The following subgroup has generator = 1 = alpha^255 (|G|=255 and k=1) [1] The following subgroup has generator = x^7 + x^6 + x^4 + x^2 + x = alpha^85 (|G|=255 and k=3) [1, x^7 + x^6 + x^4 + x^2 + x, x^7 + x^6 + x^4 + x^2 + x + 1] The following subgroup has generator = x^3 + x = alpha^51 (|G|=255 and k=5) [1, x^3 + x, x^6 + x^2, x^7 + x^4 + x, x^7 + x^6 + x^4 + x^3 + x^2 + 1] The following subgroup has generator = x^7 + x^4 + x^3 = alpha^17 (|G|=255 and k=15) [1, x^3 + x, x^3 + x + 1, x^6 + x^2, x^6 + x^2 + 1, x^6 + x^3 + x^2 + x, x^6 + x^3 + x^2 + x + 1, x^7 + x^4 + x, x^7 + x^4 + x + 1, x^7 + x^4 + x^3, x^7 + x^4 + x^3 + 1, x^7 + x^6 + x^4 + x^2 + x, x^7 + x^6 + x^4 + x^2 + x + 1, x^7 + x^6 + x^4 + x^3 + x^2, x^7 + x^6 + x^4 + x^3 + x^2 + 1] The following subgroup has generator = x^5 + x^2 + x = alpha^15 (|G|=255 and k=17) [1, x^3 + x^2 + x + 1, x^4 + x^3 + x, x^5 + x^2, x^5 + x^2 + x, x^5 + x^3 + x^2, x^5 + x^4 + x^3 + x + 1, x^6 + x^4 + x^2 + 1, x^6 + x^4 + x^3 + 1, x^6 + x^5, x^6 + x^5 + x^2, x^7 + x^4 + 1, x^7 + x^4 + x^2 + x, x^7 + x^5 + x^3 + 1, x^7 + x^5 + x^4 + x^3 + 1, x^7 + x^6 + 1, x^7 + x^6 + x^4 + x^3 + x^2 + x + 1] The following subgroup has generator = x^5 = alpha^5 (|G|=255 and k=51) [1, x + 1, x^2 + 1, x^3 + x^2 + x + 1, x^4 + 1, x^4 + x^3 + x, x^4 + x^3 + x^2, x^5, x^5 + x^2, x^5 + x^2 + x, x^5 + x^3 + x^2, x^5 + x^3 + x^2 + x, x^5 + x^4 + x + 1, x^5 + x^4 + x^2 + x + 1, x^5 + x^4 + x^3 + x + 1, x^6 + x^3 + x^2 + 1, x^6 + x^4 + x^2 + 1, x^6 + x^4 + x^3 + 1, x^6 + x^4 + x^3 + x^2 + x, x^6 + x^5, x^6 + x^5 + x^2, x^6 + x^5 + x^2 + x + 1, x^6 + x^5 + x^3 + x, x^6 + x^5 + x^3 + x^2, x^6 + x^5 + x^4 + x, x^6 + x^5 + x^4 + x^2, x^6 + x^5 + x^4 + x^3 + x^2, x^7 + x^2, x^7 + x^4 + 1, x^7 + x^4 + x^2 + x, x^7 + x^4 + x^3 + x^2, x^7 + x^5, x^7 + x^5 + x^2 + x + 1, x^7 + x^5 + x^3 + 1, x^7 + x^5 + x^3 + x^2, x^7 + x^5 + x^3 + x^2 + x, x^7 + x^5 + x^4 + x^2, x^7 + x^5 + x^4 + x^3 + 1, x^7 + x^5 + x^4 + x^3 + x^2 + x, x^7 + x^6 + 1, x^7 + x^6 + x^4 + x^2 + x, x^7 + x^6 + x^4 + x^2 + x + 1, x^7 + x^6 + x^4 + x^3 + x^2 + x + 1, x^7 + x^6 + x^5 + x, x^7 + x^6 + x^5 + x^2 + x, x^7 + x^6 + x^5 + x^3 + 1, x^7 + x^6 + x^5 + x^3 + x + 1, x^7 + x^6 + x^5 + x^3 + x^2 + x + 1, x^7 + x^6 + x^5 + x^4 + x^2, x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + 1, x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1] The following subgroup has generator = x^3 = alpha^3 (|G|=255 and k=85) [1, x^2 + x + 1, x^3, x^3 + x, x^3 + x^2, x^3 + x^2 + x + 1, x^4 + x^2 + 1, x^4 + x^2 + x + 1, x^4 + x^3 + x, x^5 + 1, x^5 + x^2, x^5 + x^2 + 1, x^5 + x^2 + x, x^5 + x^2 + x + 1, x^5 + x^3 + 1, x^5 + x^3 + x^2, x^5 + x^3 + x^2 + 1, x^5 + x^3 + x^2 + x + 1, x^5 + x^4 + x^2 + 1, x^5 + x^4 + x^2 + x, x^5 + x^4 + x^3, x^5 + x^4 + x^3 + x, x^5 + x^4 + x^3 + x + 1, x^5 + x^4 + x^3 + x^2 + 1, x^5 + x^4 + x^3 + x^2 + x, x^6, x^6 + x^2, x^6 + x^2 + x, x^6 + x^4, x^6 + x^4 + x^2 + 1, x^6 + x^4 + x^2 + x, x^6 + x^4 + x^2 + x + 1, x^6 + x^4 + x^3 + 1, x^6 + x^5, x^6 + x^5 + 1, x^6 + x^5 + x^2, x^6 + x^5 + x^2 + 1, x^6 + x^5 + x^2 + x, x^6 + x^5 + x^3 + x + 1, x^6 + x^5 + x^3 + x^2 + x, x^6 + x^5 + x^4 + x + 1, x^6 + x^5 + x^4 + x^2 + 1, x^6 + x^5 + x^4 + x^3, x^6 + x^5 + x^4 + x^3 + x^2 + 1, x^6 + x^5 + x^4 + x^3 + x^2 + x + 1, x^7 + x, x^7 + x^2 + x, x^7 + x^3 + x, x^7 + x^3 + x + 1, x^7 + x^3 + x^2 + x + 1, x^7 + x^4 + 1, x^7 + x^4 + x, x^7 + x^4 + x^2 + x, x^7 + x^5 + 1, x^7 + x^5 + x^2 + x, x^7 + x^5 + x^3, x^7 + x^5 + x^3 + 1, x^7 + x^5 + x^3 + x^2 + 1, x^7 + x^5 + x^4 + x + 1, x^7 + x^5 + x^4 + x^2 + 1, x^7 + x^5 + x^4 + x^2 + x, x^7 + x^5 + x^4 + x^3, x^7 + x^5 + x^4 + x^3 + 1, x^7 + x^5 + x^4 + x^3 + x, x^7 + x^5 + x^4 + x^3 + x^2 + x + 1, x^7 + x^6 + 1, x^7 + x^6 + x + 1, x^7 + x^6 + x^2, x^7 + x^6 + x^2 + 1, x^7 + x^6 + x^3 + x^2 + 1, x^7 + x^6 + x^3 + x^2 + x, x^7 + x^6 + x^3 + x^2 + x + 1, x^7 + x^6 + x^4, x^7 + x^6 + x^4 + x^3 + 1, x^7 + x^6 + x^4 + x^3 + x + 1, x^7 + x^6 + x^4 + x^3 + x^2 + 1, x^7 + x^6 + x^4 + x^3 + x^2 + x + 1, x^7 + x^6 + x^5 + x^2, x^7 + x^6 + x^5 + x^2 + x + 1, x^7 + x^6 + x^5 + x^3 + x^2 + 1, x^7 + x^6 + x^5 + x^4 + 1, x^7 + x^6 + x^5 + x^4 + x, x^7 + x^6 + x^5 + x^4 + x^2 + 1, x^7 + x^6 + x^5 + x^4 + x^3 + x + 1, x^7 + x^6 + x^5 + x^4 + x^3 + x^2] The following subgroup has generator = x = alpha^1 (|G|=255 and k=255) [1, x, x + 1, x^2, x^2 + 1, x^2 + x, x^2 + x + 1, x^3, x^3 + 1, x^3 + x, x^3 + x + 1, x^3 + x^2, x^3 + x^2 + 1, x^3 + x^2 + x, x^3 + x^2 + x + 1, x^4, x^4 + 1, x^4 + x, x^4 + x + 1, x^4 + x^2, x^4 + x^2 + 1, x^4 + x^2 + x, x^4 + x^2 + x + 1, x^4 + x^3, x^4 + x^3 + 1, x^4 + x^3 + x, x^4 + x^3 + x + 1, x^4 + x^3 + x^2, x^4 + x^3 + x^2 + 1, x^4 + x^3 + x^2 + x, x^4 + x^3 + x^2 + x + 1, x^5, x^5 + 1, x^5 + x, x^5 + x + 1, x^5 + x^2, x^5 + x^2 + 1, x^5 + x^2 + x, x^5 + x^2 + x + 1, x^5 + x^3, x^5 + x^3 + 1, x^5 + x^3 + x, x^5 + x^3 + x + 1, x^5 + x^3 + x^2, x^5 + x^3 + x^2 + 1, x^5 + x^3 + x^2 + x, x^5 + x^3 + x^2 + x + 1, x^5 + x^4, x^5 + x^4 + 1, x^5 + x^4 + x, x^5 + x^4 + x + 1, x^5 + x^4 + x^2, x^5 + x^4 + x^2 + 1, x^5 + x^4 + x^2 + x, x^5 + x^4 + x^2 + x + 1, x^5 + x^4 + x^3, x^5 + x^4 + x^3 + 1, x^5 + x^4 + x^3 + x, x^5 + x^4 + x^3 + x + 1, x^5 + x^4 + x^3 + x^2, x^5 + x^4 + x^3 + x^2 + 1, x^5 + x^4 + x^3 + x^2 + x, x^5 + x^4 + x^3 + x^2 + x + 1, x^6, x^6 + 1, x^6 + x, x^6 + x + 1, x^6 + x^2, x^6 + x^2 + 1, x^6 + x^2 + x, x^6 + x^2 + x + 1, x^6 + x^3, x^6 + x^3 + 1, x^6 + x^3 + x, x^6 + x^3 + x + 1, x^6 + x^3 + x^2, x^6 + x^3 + x^2 + 1, x^6 + x^3 + x^2 + x, x^6 + x^3 + x^2 + x + 1, x^6 + x^4, x^6 + x^4 + 1, x^6 + x^4 + x, x^6 + x^4 + x + 1, x^6 + x^4 + x^2, x^6 + x^4 + x^2 + 1, x^6 + x^4 + x^2 + x, x^6 + x^4 + x^2 + x + 1, x^6 + x^4 + x^3, x^6 + x^4 + x^3 + 1, x^6 + x^4 + x^3 + x, x^6 + x^4 + x^3 + x + 1, x^6 + x^4 + x^3 + x^2, x^6 + x^4 + x^3 + x^2 + 1, x^6 + x^4 + x^3 + x^2 + x, x^6 + x^4 + x^3 + x^2 + x + 1, x^6 + x^5, x^6 + x^5 + 1, x^6 + x^5 + x, x^6 + x^5 + x + 1, x^6 + x^5 + x^2, x^6 + x^5 + x^2 + 1, x^6 + x^5 + x^2 + x, x^6 + x^5 + x^2 + x + 1, x^6 + x^5 + x^3, x^6 + x^5 + x^3 + 1, x^6 + x^5 + x^3 + x, x^6 + x^5 + x^3 + x + 1, x^6 + x^5 + x^3 + x^2, x^6 + x^5 + x^3 + x^2 + 1, x^6 + x^5 + x^3 + x^2 + x, x^6 + x^5 + x^3 + x^2 + x + 1, x^6 + x^5 + x^4, x^6 + x^5 + x^4 + 1, x^6 + x^5 + x^4 + x, x^6 + x^5 + x^4 + x + 1, x^6 + x^5 + x^4 + x^2, x^6 + x^5 + x^4 + x^2 + 1, x^6 + x^5 + x^4 + x^2 + x, x^6 + x^5 + x^4 + x^2 + x + 1, x^6 + x^5 + x^4 + x^3, x^6 + x^5 + x^4 + x^3 + 1, x^6 + x^5 + x^4 + x^3 + x, x^6 + x^5 + x^4 + x^3 + x + 1, x^6 + x^5 + x^4 + x^3 + x^2, x^6 + x^5 + x^4 + x^3 + x^2 + 1, x^6 + x^5 + x^4 + x^3 + x^2 + x, x^6 + x^5 + x^4 + x^3 + x^2 + x + 1, x^7, x^7 + 1, x^7 + x, x^7 + x + 1, x^7 + x^2, x^7 + x^2 + 1, x^7 + x^2 + x, x^7 + x^2 + x + 1, x^7 + x^3, x^7 + x^3 + 1, x^7 + x^3 + x, x^7 + x^3 + x + 1, x^7 + x^3 + x^2, x^7 + x^3 + x^2 + 1, x^7 + x^3 + x^2 + x, x^7 + x^3 + x^2 + x + 1, x^7 + x^4, x^7 + x^4 + 1, x^7 + x^4 + x, x^7 + x^4 + x + 1, x^7 + x^4 + x^2, x^7 + x^4 + x^2 + 1, x^7 + x^4 + x^2 + x, x^7 + x^4 + x^2 + x + 1, x^7 + x^4 + x^3, x^7 + x^4 + x^3 + 1, x^7 + x^4 + x^3 + x, x^7 + x^4 + x^3 + x + 1, x^7 + x^4 + x^3 + x^2, x^7 + x^4 + x^3 + x^2 + 1, x^7 + x^4 + x^3 + x^2 + x, x^7 + x^4 + x^3 + x^2 + x + 1, x^7 + x^5, x^7 + x^5 + 1, x^7 + x^5 + x, x^7 + x^5 + x + 1, x^7 + x^5 + x^2, x^7 + x^5 + x^2 + 1, x^7 + x^5 + x^2 + x, x^7 + x^5 + x^2 + x + 1, x^7 + x^5 + x^3, x^7 + x^5 + x^3 + 1, x^7 + x^5 + x^3 + x, x^7 + x^5 + x^3 + x + 1, x^7 + x^5 + x^3 + x^2, x^7 + x^5 + x^3 + x^2 + 1, x^7 + x^5 + x^3 + x^2 + x, x^7 + x^5 + x^3 + x^2 + x + 1, x^7 + x^5 + x^4, x^7 + x^5 + x^4 + 1, x^7 + x^5 + x^4 + x, x^7 + x^5 + x^4 + x + 1, x^7 + x^5 + x^4 + x^2, x^7 + x^5 + x^4 + x^2 + 1, x^7 + x^5 + x^4 + x^2 + x, x^7 + x^5 + x^4 + x^2 + x + 1, x^7 + x^5 + x^4 + x^3, x^7 + x^5 + x^4 + x^3 + 1, x^7 + x^5 + x^4 + x^3 + x, x^7 + x^5 + x^4 + x^3 + x + 1, x^7 + x^5 + x^4 + x^3 + x^2, x^7 + x^5 + x^4 + x^3 + x^2 + 1, x^7 + x^5 + x^4 + x^3 + x^2 + x, x^7 + x^5 + x^4 + x^3 + x^2 + x + 1, x^7 + x^6, x^7 + x^6 + 1, x^7 + x^6 + x, x^7 + x^6 + x + 1, x^7 + x^6 + x^2, x^7 + x^6 + x^2 + 1, x^7 + x^6 + x^2 + x, x^7 + x^6 + x^2 + x + 1, x^7 + x^6 + x^3, x^7 + x^6 + x^3 + 1, x^7 + x^6 + x^3 + x, x^7 + x^6 + x^3 + x + 1, x^7 + x^6 + x^3 + x^2, x^7 + x^6 + x^3 + x^2 + 1, x^7 + x^6 + x^3 + x^2 + x, x^7 + x^6 + x^3 + x^2 + x + 1, x^7 + x^6 + x^4, x^7 + x^6 + x^4 + 1, x^7 + x^6 + x^4 + x, x^7 + x^6 + x^4 + x + 1, x^7 + x^6 + x^4 + x^2, x^7 + x^6 + x^4 + x^2 + 1, x^7 + x^6 + x^4 + x^2 + x, x^7 + x^6 + x^4 + x^2 + x + 1, x^7 + x^6 + x^4 + x^3, x^7 + x^6 + x^4 + x^3 + 1, x^7 + x^6 + x^4 + x^3 + x, x^7 + x^6 + x^4 + x^3 + x + 1, x^7 + x^6 + x^4 + x^3 + x^2, x^7 + x^6 + x^4 + x^3 + x^2 + 1, x^7 + x^6 + x^4 + x^3 + x^2 + x, x^7 + x^6 + x^4 + x^3 + x^2 + x + 1, x^7 + x^6 + x^5, x^7 + x^6 + x^5 + 1, x^7 + x^6 + x^5 + x, x^7 + x^6 + x^5 + x + 1, x^7 + x^6 + x^5 + x^2, x^7 + x^6 + x^5 + x^2 + 1, x^7 + x^6 + x^5 + x^2 + x, x^7 + x^6 + x^5 + x^2 + x + 1, x^7 + x^6 + x^5 + x^3, x^7 + x^6 + x^5 + x^3 + 1, x^7 + x^6 + x^5 + x^3 + x, x^7 + x^6 + x^5 + x^3 + x + 1, x^7 + x^6 + x^5 + x^3 + x^2, x^7 + x^6 + x^5 + x^3 + x^2 + 1, x^7 + x^6 + x^5 + x^3 + x^2 + x, x^7 + x^6 + x^5 + x^3 + x^2 + x + 1, x^7 + x^6 + x^5 + x^4, x^7 + x^6 + x^5 + x^4 + 1, x^7 + x^6 + x^5 + x^4 + x, x^7 + x^6 + x^5 + x^4 + x + 1, x^7 + x^6 + x^5 + x^4 + x^2, x^7 + x^6 + x^5 + x^4 + x^2 + 1, x^7 + x^6 + x^5 + x^4 + x^2 + x, x^7 + x^6 + x^5 + x^4 + x^2 + x + 1, x^7 + x^6 + x^5 + x^4 + x^3, x^7 + x^6 + x^5 + x^4 + x^3 + 1, x^7 + x^6 + x^5 + x^4 + x^3 + x, x^7 + x^6 + x^5 + x^4 + x^3 + x + 1, x^7 + x^6 + x^5 + x^4 + x^3 + x^2, x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + 1, x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x, x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1]