Index

A

Abel, N. H. 1, 2, 3

Abelian 1

accepted language 1

accepted set 1, 2

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

–binary gcd 1, 2, 3

–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 p −1 2

–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

alphabet 1, 2, 3

alternating group 1

amalgamated product 1

antichain 1

aperiodic monoid 1

arc 1

Arnold, A. 1, 2

Artin, E. 1

associativity 1

–elliptic curves 1, 2

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

–complete 1, 2

–deterministic 1, 2

–deterministic Büchi 1

–equivalent 1

–finite 1, 2

–minimal 1

–minimization 1

–nondeterministic 1

–product 1

–run 1, 2, 3

–spelling 1, 2

–subset 1

–trim 1

–with rational labels 1

automorphism 1

–Frobenius 1, 2

–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, M. 1, 2

Benois’ theorem 1

Bézout, É. 1

Bézout’s lemma 1

big- see -notation

binary gcd 1, 2, 3

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-smooth number 1, 2

Büchi automaton 1

–deterministic 1

–run 1

Büchi, J. R. VII, 1, 2, 3, 4, 5

Büchi’s theorem 1, 2

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

center of a group 1, 2

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 automaton 1, 2

complete rewriting system 1

complex product 1

compression see data compression

compression function 1

computational security 1

concatenation 1, 2

concurrency 1

confluent 1

–locally 1

–strongly 1

congruence 1, 2

–syntactic 1, 2

congruent 1, 2

conjugacy problem 1

conjugate element 1

constant polynomial 1

construction

–subset 1

–Thompson 1

content see alphabet

convergent rewriting system 1

convolution product 1

coprime 1, 2, 3

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

–Diffie–Hellman 1, 2

–ElGamal 1, 2

–elliptic Diffie–Hellman 1

–elliptic ElGamal 1

–key exchange 1

–Merkle–Hellman 1, 2

–monoalphabetic cipher 1

–multi-prime RSA 1

–polyalphabetic cipher 1

–public-key 1

–Rabin 1, 2

–RSA 1, 2, 3

–shift cipher 1

–symmetric 1

–Vernam one-time pad 1

–Vigenére cipher 1

curve 1

–elliptic 1, 2, 3

–pseudo- 1

cyclic group 1

cyclic semigroup 1

cyclically reduced word 1

D

?-class 1

Damgård, I. B. 1

data compression 1, 2

Davis, M. 1

De Morgan, A. 1

decoding function 1

decomposition

–Krohn–Rhodes 1, 2

decreasing sequence 1

decryption function 1

defining relation 1

degree

–divisor 1

–endomorphism 1

–polynomial 1, 2

degree formula 1

Dehn function 1

Dehn, M. 1

Dehn’s algorithm 1

del Ferro, S. 1

dependence alphabet 1

derivative 1, 2

Descartes, R. 1

Descartes’ rule of signs 1

deterministic automaton 1, 2

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, B.W. V, 1, 2, 3

Diffie–Hellman key exchange 1, 2

–on elliptic curves 1

Diffie–Hellman problem 1, 2

digital commitment 1

digital signature 1

Digital Signature Algorithm 1

dihedral group 1

direct product 1

directed edge 1

discrete Fourier transform 1, 2

discrete logarithm 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

divisor 1, 2

–greatest common 1

–group 1

–local 1, 2

–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

–idempotent 1, 2

–incomparable 1

–inverse 1, 2

–invertible 1

–left inverse 1

–left neutral 1

–neutral 1, 2

–period 1

–regular 1

–right inverse 1

–right neutral 1

–square 1, 2

–threshold 1

–transposed 1

–unit 1, 2

–zero 1

elementary arithmetic operation 1

ElGamal cryptosystem 1, 2

–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

elliptic curve 1, 2, 3, 4

–group operation 1

elliptic curve integer factorization 1

elliptic function 1

empty word 1, 2

encoding function 1

encryption function 1

endomorphism 1

–Frobenius 1

–separable 1

ε-NFA 1

equivalent automata 1

ε-transition 1

Euclid of Alexandria 1, 2

Euclidean algorith

–extended 1

Euclidean algorithm 1

–binary 1

–binary extended 1, 2

Euler, L. 1, 2, 3, 4

Eulerian pseudoprime 1

Euler’s criterion 1

Euler’s number 1

Euler’s theorem 1

Euler’s totient function 1

evaluation homomorphism 1, 2

even permutation 1

exponentiation

–fast 1

–fast modular 1

expression

–rational 1

–regular see rational expression

–star-free 1

extended Euclidean algorithm 1

–binary 1, 2

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, P. de 1, 2, 3, 4

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

field 1, 2, 3

–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 state 1, 2

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

flip–flop 1, 2

formal language 1

formal power series 1

–derivative 1

Fourier, J. B. J. 1

Frederick the Great 1, 2

free group 1

–basis 1

–rank 1, 2

free monoid 1, 2

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, F. G. 1, 2, 3

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

Galois, É. 1, 2, 3

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, K. P. 1, 2, 3

Gödel’s incompleteness theorem 1, 2

Goldwasser, S. 1, 2, 3

Goldwasser–Kilian primality certificates 1

good sequence 1

graph

–rose 1, 2

–Schreier 1

–Stallings 1

graph group 1

graphical realization 1, 2

–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

group 1, 2

–alternating 1

–automorphism 1

–Baumslag 1

–Baumslag–Gersten 1

–Baumslag–Solitar 1

–center 1, 2

–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

–Schützenberger 1, 2

–simple 1

–small cancellation 1

–special linear 1, 2

–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, H. 1, 2, 3

Hasse’s theorem 1

Hellman, M. E. V, 1, 2, 3, 4, 5

Hermite, Ch. 1

Higman, G. VI, 1, 2

Higman’s lemma 1

Hilbert, D. 1, 2, 3

Hilbert’s basis theorem 1

Hilbert’s tenth problem 1

HNN extension 1

homomorphism 1

–evaluation 1

–Frobenius 1

–graphical realization 1, 2

–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

ideal 1, 2

–finitely generated 1

–generated 1

–left 1

–maximal 1

–principal 1, 2

–right 1

–two-sided 1

idempotent element 1, 2

identity 1

image 1, 2

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

initial state 1, 2

inner automorphism 1

integer factorization 1

–elliptic curves 1

–Pollard’s p − 1 algorithm 2

–Pollard’s ρ algorithm 1

–quadratic sieve 1

integer multiplication

–Karatsuba 1

–Schönhage–Strassen 1

integral domain 1

interpolation 1

introspective number 1

inverse element 1, 2

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, A. A. 1, 2

Karatsuba’s algorithm 1

Kayal, N. VI, 1

Keller, R. M. 1

Kerckhoffs, A. 1

Kerckhoffs’ principle 1

kernel 1, 2

kernel of the Schreier graph 1

key 1

–private 1

–public 1

–secret 1

key exchange 1, 2

Kilian, J. J. 1, 2, 3

Kleene, S. C. 1, 2, 3

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, K. B. VI, 1, 2, 3

Krohn–Rhodes decomposition 1, 2

Krohn–Rhodes theorem 1

Kronecker delta 1

Kronecker, L. 1

Kruskal, J. B. 1, 2

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

language 1, 2, 3

–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

least common multiple 1, 2

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 of a word 1, 2

length-lexicographic 1

Lenstra, H., Jr. 1, 2

letter 1, 2

Levi, F. W. D. 1

Levi’s lemma 1

lexicographic order 1, 2

Lindemann, C. L. F. von 1

line 1

linear Diophantine equation 1

linear Diophantine system 1

linear set 1

Liouville, J. 1

local divisor 1, 2

local solution 1

local submonoid 1

locally confluent 1

logic

–first-order 1

–monadic second-order 1, 2

Lucas, É 1, 2

Lucas primality test 1

Lucas–Lehmer primality test 1

Lyndon factorization 1

Lyndon, R. C. VII, 1, 2, 3

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, R. C. 1, 2

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

modulo 1, 2, 3

modulus 1, 2

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 1, 2

–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

–least common 1, 2

multiple exponent attack 1

multiple root 1

multiplication table 1

multiplicative group 1

multiplicity of a root 1, 2

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

neutral element 1, 2

Newton, I., Sir 1

Newton method 1

NFA 1

–ε- 1

Nielsen, J. 1, 2, 3

Nielsen transformation 1, 2

Nielsen–Schreier theorem 1

Noether, A. E. 1, 2