A
Abelian 1
accepted language 1
accepting run 1
addition chain 1
addition law on elliptic curve 1
addition theorem 1
Adleman, L. V, 1
Advanced Encryption Standard 1
AES see Advanced Encryption Standard
Agrawal, M. VI, 1
AKS primality test 1
algebraic closure 1
algebraic number 1
algebraically closed field 1
algorithm
–AKS 1
–baby-step giant-step 1
–Brzozowski’s minimization 1
–Cipolla 1
–Dehn 1
–division 1
–elliptic curve integer factorization 1
–Euclidean 1
–extended Euclidean 1
–fast exponentiation 1
–fast Fourier transform 1
–fast modular exponentiation 1
–index calculus 1
–Karatsuba 1
–marking 1
–Moore’s minimization 1
–Pohlig–Hellman 1
–Pollard’s ρ (factorization) 1
–Pollard’s ρ (logarithm) 1
–probabilistic primality test 1
–quadratic sieve 1
–Schönhage–Strassen 1
–Tonelli 1
Alice VIII, 1
almost all 1
alternating group 1
amalgamated product 1
antichain 1
aperiodic monoid 1
arc 1
Artin, E. 1
associativity 1
asymptotic estimate 1
Atkin, A.O. L. 1
attack
–brute-force 1
–chosen-ciphertext 1
–chosen-plaintext 1
–ciphertext-only 1
–known-plaintext 1
–man-in-the-middle 1
–Shamir 1
–Wiener 1
augmented monoid 1
automata minimization 1
–Brzozowski 1
–Moore 1
automaton 1
–Büchi 1
–complement 1
–deterministic Büchi 1
–equivalent 1
–minimal 1
–minimization 1
–nondeterministic 1
–product 1
–subset 1
–trim 1
–with rational labels 1
automorphism 1
–graph 1
–inner 1
–Whitehead 1
automorphism group 1
axiom of choice 1
B
baby-step giant-step algorithm 1
bad sequence 1
basis of a free group 1
Bass, H. 1
Baumslag, G. 1
Baumslag group 1
Baumslag–Gersten group 1
Baumslag–Solitar group 1
Benois’ theorem 1
Bézout, É. 1
Bézout’s lemma 1
big- see -notation
binomial coefficient 1
binomial expansion see binomial theorem
binomial theorem 1
Birkhoff, G. 1
birthday paradox 1
birthday paradox algorithm see ρ algorithm
Bob VIII, 1
Bombelli, R. 1
Boone, W. W. 1
Brandt monoid 1
bridge 1
Britton, J. L. 1
Britton reduction 1
brute-force attack 1
Brzozowski, J. A. 1
Brzozowski’s minimization algorithm 1
Büchi automaton 1
–deterministic 1
–run 1
Büchi, J. R. VII, 1, 2, 3, 4, 5
C
Caesar, G. J. 1
Caesar’s cipher 1
cancellative monoid 1
Cardano, G. 1
Carmichael number 1
Carmichael, R. D. 1
Cauchy, A. L. 1
Cauchy’s theorem 1
centralizer 1
chain 1
channel encoding 1
characteristic 1
chinese remainder theorem 1
Chomsky, A. N. 1
Church, A. 1
Church–Rosser property 1
cipher 1
–Caesar 1
–monoalphabetic 1
–polyalphabetic 1
–shift 1
–Vigenère 1
ciphertext 1
Cipolla, M. 1
Cipolla’s algorithm 1
closed formula see sentence
coarsening 1
coefficient 1
–leading 1
coincidence index 1
collision resistant function 1
commutative 1
commutative ring 1
comparable elements 1
complement automaton 1
complete rewriting system 1
complex product 1
compression see data compression
compression function 1
computational security 1
concurrency 1
confluent 1
–locally 1
–strongly 1
conjugacy problem 1
conjugate element 1
constant polynomial 1
construction
–subset 1
–Thompson 1
content see alphabet
convergent rewriting system 1
convolution product 1
coset 1
–left 1
–right 1
cover 1
covering 1
Coxeter group 1
–right-angled 1
Coxeter, H. 1
critical pair 1
–factor 1
–overlap 1
cryptanalysis 1
cryptographic system 1
cryptography 1
cryptosystem 1
–asymmetric 1
–Caesar’s cipher 1
–elliptic Diffie–Hellman 1
–elliptic ElGamal 1
–key exchange 1
–monoalphabetic cipher 1
–multi-prime RSA 1
–polyalphabetic cipher 1
–public-key 1
–shift cipher 1
–symmetric 1
–Vernam one-time pad 1
–Vigenére cipher 1
curve 1
–pseudo- 1
cyclic group 1
cyclic semigroup 1
cyclically reduced word 1
D
?-class 1
Damgård, I. B. 1
Davis, M. 1
De Morgan, A. 1
decoding function 1
decomposition
decreasing sequence 1
decryption function 1
defining relation 1
degree
–divisor 1
–endomorphism 1
degree formula 1
Dehn function 1
Dehn, M. 1
Dehn’s algorithm 1
del Ferro, S. 1
dependence alphabet 1
Descartes, R. 1
Descartes’ rule of signs 1
deterministic Büchi automaton 1
deterministic graphical realization 1
deterministic language 1
DFA see deterministic automaton
DFT see discrete Fourier transform
Dickson, L. E. 1
Dickson’s lemma 1
differentiation rules 1
Diffie–Hellman key exchange 1, 2
–on elliptic curves 1
digital commitment 1
digital signature 1
Digital Signature Algorithm 1
dihedral group 1
direct product 1
directed edge 1
discrete Fourier transform 1, 2
–baby-step giant-step algorithm 1
–index calculus 1
–Pohlig–Hellman algorithm 1
–Pollard’s ρ algorithm 1
distributivity 1
divide 1
division 1
–polynomial 1
–greatest common 1
–group 1
–principal 1
–zero 1
domain 1
–integral 1
DSA see Digital Signature Algorithm
Dyck language 1
Dyck, W. F. A., Ritter von 1
E
ECC 1
edge
–arc 1
–bridge 1
–directed 1
–source 1
–target 1
egg box diagram 1
Eilenberg, S. 1
Eisenstein, F. G.M. 1
Eisenstein’s criterion 1
element
–comparable 1
–conjugate 1
–generating 1
–incomparable 1
–invertible 1
–left inverse 1
–left neutral 1
–period 1
–regular 1
–right inverse 1
–right neutral 1
–threshold 1
–transposed 1
–zero 1
elementary arithmetic operation 1
–on elliptic curves 1
ElGamal signature 1
ElGamal, T. 1
Elgot, C. C. 1
elimination
–of ε-transitions 1
–of states 1
elimination of ε-transitions 1
Elkies, N. 1
–group operation 1
elliptic curve integer factorization 1
elliptic function 1
encoding function 1
encryption function 1
endomorphism 1
–Frobenius 1
–separable 1
ε-NFA 1
equivalent automata 1
ε-transition 1
Euclidean algorith
–extended 1
Euclidean algorithm 1
–binary 1
Eulerian pseudoprime 1
Euler’s criterion 1
Euler’s number 1
Euler’s theorem 1
Euler’s totient function 1
even permutation 1
exponentiation
–fast 1
–fast modular 1
expression
–rational 1
–regular see rational expression
–star-free 1
extended Euclidean algorithm 1
F
φ function see totient function
factor 1
factor critical pair 1
factor group see quotient group
factor ring see quotient ring
fast exponentiation 1
–modular 1
fast Fourier transform 1
fast powering see fast exponentiation
Fermat number 1
Fermat primality test 1
Fermat’s Last Theorem 1
Fermat’s little theorem 1
Fermat’s theorem on sums of two squares 1
Ferrari, L. 1
FFT see fast Fourier transform
Fibonacci number 1
–algebraically closed 1
–finite 1
–function 1
–Galois 1
–prime 1
–skew 1
–splitting 1
–sub- 1
–used in AES 1
field extension 1
final transition 1
Fine, N. J. 1
finite automaton 1
finite field
–used in AES 1
finitely generated 1
finitely presented group 1
finitely presented monoid 1
first-order logic 1
first-order variable 1
formal language 1
formal power series 1
–derivative 1
Fourier, J. B. J. 1
free group 1
–basis 1
free partially commutative group 1
free partially commutative monoid 1
free product 1
free variable 1
frequency analysis 1
Frobenius automorphism 1
Frobenius endomorphism 1
Frobenius homomorphism 1
Frobenius morphism 1
function
–collision resistant 1
–compression 1
–decoding 1
–decryption 1
–Dehn 1
–elliptic 1
–encoding 1
–encryption 1
–hash 1
–one-way 1
–rational 1
–totient 1
–tower 1
–transition 1
function field 1
Fürer, M. 1
G
Galois field 1
Gauss, J. C. F. 1
gcd see greatest common divisor; Euclidean algorithm
generalized Baumslag–Solitar group 1
generate 1
generated ideal 1
generator 1
Germain, S. 1
Gersten, S. M. 1
global solution 1
Gödel’s incompleteness theorem 1, 2
Goldwasser–Kilian primality certificates 1
good sequence 1
graph
–Schreier 1
–Stallings 1
graph group 1
–deterministic 1
greatest common divisor 1, 2, 3
Green, J. A. VI, 1
Green’s lemma 1
Green’s relations 1
–D 1
–H 1
–J 1
–L 1
–R 1
Gromov, M. L. 1
Grothendieck, A. VII, 1
–alternating 1
–automorphism 1
–Baumslag 1
–Baumslag–Gersten 1
–Baumslag–Solitar 1
–Coxeter 1
–cyclic 1
–dihedral 1
–finitely presented 1
–free 1
–free partially commutative 1
–generalized Baumslag–Solitar 1
–graph 1
–Hopfian 1
–hyperbolic 1
–Klein four- 1
–modular 1
–multiplicative 1
–Picard 1
–quotient 1
–residually finite 1
–right-angled Artin 1
–right-angled Coxeter 1
–simple 1
–small cancellation 1
–symmetric 1
–symmetry 1
–Waack 1
group divisor 1
group homomorphism 1
group of units 1
group operation on elliptic curve 1
group-based cryptography 1
group-free monoid see aperiodic monoid
Gustafson, W. H. 1
H
H-class 1
halting problem 1
Hartshorne, R. 1
hash function 1
Hasse bound 1
Hasse’s theorem 1
Hellman, M. E. V, 1, 2, 3, 4, 5
Hermite, Ch. 1
Higman’s lemma 1
Hilbert’s basis theorem 1
Hilbert’s tenth problem 1
HNN extension 1
homomorphism 1
–evaluation 1
–Frobenius 1
–group 1
–partial 1
–projection 1
–ring 1
–syntactic 1
homomorphism theorem
–groups 1
–rings 1
Hopf, H. 1
Hopfian group 1
hyperbolic group 1
I
–finitely generated 1
–generated 1
–left 1
–maximal 1
–right 1
–two-sided 1
identity 1
incomparable elements 1
independence 1
independence relation 1
index
–stabilization 1
index calculus 1
index of a subgroup 1
infinite word 1
infix see factor
inner automorphism 1
integer factorization 1
–elliptic curves 1
–Pollard’s ρ algorithm 1
–quadratic sieve 1
integer multiplication
–Karatsuba 1
–Schönhage–Strassen 1
integral domain 1
interpolation 1
introspective number 1
inversion 1
invertible element 1
irreducible normal form 1
irreducible polynomial 1
isomorphism 1
–of rings 1
isomorphism problem 1
J
J-class 1
Jacobi, C. G. J. 1
Jacobi symbol 1
K
Karatsuba’s algorithm 1
Kayal, N. VI, 1
Keller, R. M. 1
Kerckhoffs, A. 1
Kerckhoffs’ principle 1
kernel of the Schreier graph 1
key 1
–private 1
–public 1
–secret 1
Kleene star 1
Kleene’s theorem 1
Klein, F. Chr. 1
Klein four-group 1
knapsack problem 1
Knödel number 1
Knödel, W. 1
Koblitz, N. 1
Krohn–Rhodes decomposition 1, 2
Krohn–Rhodes theorem 1
Kronecker delta 1
Kronecker, L. 1
Kruskal’s tree theorem 1
L
L-class 1
label of a transition 1
Lagrange interpolation 1
Lagrange, J.-J. de 1
Lagrange polynomial 1
Lagrange’s theorem 1
Lallement, G. 1
Landau, E. G.H. 1
–accepted 1
–at a state 1
–deterministic 1
–Dyck 1
–formal 1
–mirror 1
–ω- 1
–ω-rational 1
–regular 1
–reverse 1
–star-free 1
Laocoön 1
law of quadratic reciprocity 1
lcm see least common multiple
leading coefficient 1
left-conjugate see conjugate
left coset 1
left ideal 1
left inverse 1
left neutral 1
Legendre, A.-M. 1
Legendre symbol 1
Lehmer, D.H. 1
lemma
–Bézout 1
–Dickson 1
–Fine–Wilf 1
–Green 1
–Higman 1
–Levi 1
–periodicity 1
–Zolotarev 1
length-lexicographic 1
Levi, F. W. D. 1
Levi’s lemma 1
Lindemann, C. L. F. von 1
line 1
linear Diophantine equation 1
linear Diophantine system 1
linear set 1
Liouville, J. 1
local solution 1
local submonoid 1
locally confluent 1
logic
–first-order 1
Lucas primality test 1
Lucas–Lehmer primality test 1
Lyndon factorization 1
Lyndon word 1
Lyndon–Schützenberger theorem 1
M
MacLane, S. 1
man-in-the-middle attack 1
marking algorithm 1
master theorem 1
master theorem II 1
Matiyasevich, Yu. 1
M-automaton see automaton
maximal ideal 1
Mazurkiewicz, A. 1
McKay, J.H. 1
McKnight, D. J., Jr. 1
McKnight’s theorem 1
median 1
Merkle–Damgård construction 1
Merkle–Hellman cryptosystem 1, 2
Mersenne, M. 1
Mersenne number 1
Mezei, J. 1
Mezei’s theorem 1
Miller, G. L. 1
Miller–Rabin primality test 1
minimal automaton 1
minimal polynomial 1
mirror language 1
modular arithmetic 1
modular group 1
monadic second-order logic 1, 2
monadic semi-Thue system 1
monoalphabetic cipher 1
monoalphabetic substitution 1
Monod, J. 1
monoid 1
–aperiodic 1
–augmented 1
–Brandt 1
–cancellative 1
–defining relations 1
–divisor 1
–finitely presented 1
–flip–flop 1
–free partially commutative 1
–group-free see aperiodic
–presentation 1
–residually finite 1
–syntactic 1
–trace 1
–transition 1
Moore, E. F. 1
Moore’s minimization algorithm 1
morphism
–Frobenius 1
–rational 1
MSO see monadic second-order logic
multiple 1
multiple exponent attack 1
multiple root 1
multiplication table 1
multiplicative group 1
multi-prime RSA 1
Myhill, J. R. 1
Myhill–Nerode theorem 1
N
Nair, M. 1
Nash-Williams, C. St. J. A. 1, 2
natural numbers 1
Nerode, A. 1
Neukirch, J. VII
Neumann, B.H. 1
Neumann, H. 1
Newton, I., Sir 1
Newton method 1
NFA 1
–ε- 1
Nielsen–Schreier theorem 1