liveBook · Manning

Generator

As explained in Hacking Cryptography

A generator of a finite multiplicative group is an element whose successive powers produce every element of the group.

A generator of the finite multiplicative group modulo a prime p is an element g whose successive powers produce every member of {1, 2, ..., p−1} modulo p. For Z₁₃*, the generators are 2, 6, 7, and 11; each generator's powers contain every group element exactly once. section 8.3.1

Table 8.1 Exponentiation table for multiplicative group modulo 13
Base \ Exponent (n) 0 1 2 3 4 5 6 7 8 9 10 11 12
\(1^n \bmod 13\) 1 1 1 1 1 1 1 1 1 1 1 1 1
\(2^n \bmod 13\) 1 2 4 8 3 6 12 11 9 5 10 7 1
\(3^n \bmod 13\) 1 3 9 1 3 9 1 3 9 1 3 9 1
\(4^n \bmod 13\) 1 4 3 12 9 10 1 4 3 12 9 10 1
\(5^n \bmod 13\) 1 5 12 8 1 5 12 8 1 5 12 8 1
\(6^n \bmod 13\) 1 6 10 8 9 2 12 7 3 5 4 11 1
\(7^n \bmod 13\) 1 7 10 5 9 11 12 6 3 8 4 2 1
\(8^n \bmod 13\) 1 8 12 5 1 8 12 5 1 8 12 5 1
\(9^n \bmod 13\) 1 9 3 1 9 3 1 9 3 1 9 3 1
\(10^n \bmod 13\) 1 10 9 12 3 4 1 10 9 12 3 4 1
\(11^n \bmod 13\) 1 11 4 5 3 7 12 2 9 8 6 10 1
\(12^n \bmod 13\) 1 12 1 12 1 12 1 12 1 12 1 12 1

Use the exponentiation table modulo 13 to compare bases: generator rows visit all twelve nonzero residues, while other rows repeat a smaller cycle. section 8.3.1

Generator 2 modulo 13

The powers of 2 modulo 13 are 1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, and 7 before returning to 1. They therefore cover every element of Z₁₃*. In contrast, powers of 3 repeat the shorter cycle 1, 3, 9. section 8.3.1

How Hacking Cryptography covers it

How deep it goes
Defines generators and demonstrates them with a complete exponentiation table modulo 13.
Examples
Uses powers modulo 13, identifying 2, 6, 7, and 11 as generators and contrasting them with shorter repeating cycles.
What it assumes
Assumes modular arithmetic and multiplicative groups while explaining the generator definition through explicit residues.
What you can do after
Evaluate whether a base generates every nonzero residue modulo a prime using its modular-power sequence.
How it connects
Connects generators to multiplicative groups, primitive roots, Fermat’s Little Theorem, discrete logarithms, and Diffie–Hellman key exchange.

Also explained in

Compare how 2 books explain generator →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Hacking Cryptography. The section links point to the parts of the book it draws on.