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.

- $\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$.

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

198

44

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

44

9

0

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$.

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

True

False

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

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

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.

Let $G$ be a finite cyclic group. Then

- The number of primitive elements of $G$ is $\varphi(|G|)$.
- If $|G|$ is prime, then all elements $a \neq 1$ in $G$ are primitive.

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.

4
1
5
2
6
3

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

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:

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$.

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

Here is an example of that happening.

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]

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.

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.

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.

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:

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

*Proof sketch*

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

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.

2

[1, 2, 4, 5, 10, 20, 25, 50, 100]

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]

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.

(103, 2 * 3 * 17)
(107, 2 * 53)
107

2

[1, 2, 53, 106]

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]

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.

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:
ad:dc:dc:62:41:2a:aa:92:bb:52:02:a0:37:14:0b:
cc:fa:2d:36:43
generator: 2 (0x2)
-----BEGIN DH PARAMETERS-----
MEYCQQDi6FTTdfEKLZDBXVSCHrV19yMGQXzT2SOcObeu+6Drnb6T2mUK6hOESesE
Ea3c3GJBKqqSu1ICoDcUC8z6LTZDAgEC
-----END DH PARAMETERS-----
```

11884112392174931525551803878284316468547743675014443360835956479033078578449820213217260145091693859837332463855747972651088419742292198211998500015388227L

True

5942056196087465762775901939142158234273871837507221680417978239516539289224910106608630072545846929918666231927873986325544209871146099105999250007694113

True

11884112392174931525551803878284316468547743675014443360835956479033078578449820213217260145091693859837332463855747972651088419742292198211998500015388226

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 DLP is a problem that can be stated in any group (not just our simple "mod p") groups.

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$

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?

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.

Elliptic Curve defined by y^2 = x^3 + 2*x + 5 over Finite Field of size 11

10

(0 : 7 : 1)

(9 : 9 : 1)

(3 : 7 : 1)

(8 : 4 : 1)

(4 : 0 : 1)

(8 : 7 : 1)

(3 : 4 : 1)

(9 : 2 : 1)

(0 : 4 : 1)

(0 : 1 : 0)

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.

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

4

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)]

It turns out Galois Fields are cyclic. paper

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]