Notations

Any time you are stuck on a problem, introduce more notation.

—Chris Skinner [Plenary Lecture, Aug 1997, Topics in Number Theory, Penn State]

General
|a|	absolute value of real number a
min S	minimum of elements of set S
max S	maximum of elements of set S
exp(a)	ea, where
log x	logarithm of x with respect to some unspecified base (like 10)
ln x	loge x, where
lg x	log2 x
logk x	(log x)k (similarly, lnk x = (ln x)k and lgk x = (lg x)k)
:=	is defined as (or “is assigned the value” in code snippets)
i
	complex conjugate (x – iy) of the complex number z = x + iy
δij	Kronecker delta
(asas–1 . . . a0)b	b-ary representation of a non-negative integer
	binomial coefficient, equals n(n – 1) ··· (n – r + 1)/r!
⌊x⌋	floor of real number x
⌈x⌉	ceiling of real number x
[a, b]	closed interval, that is, the set of real numbers x in the range a ≤ x ≤ b
(a, b)	open interval, that is, the set of real numbers x in the range a < x < b
L(t, α, c)	expression of the form exp ((c + o(1))(ln t)α(ln ln t)1–α)
Lt[c]	abbreviation for L(t, 1/2, c) (denoted also as L[c] if t is understood)
Bit-wise operations (on bit strings a, b)
NAND	negation of AND
NOR	negation of OR
XOR	exclusive OR
a ⊕ b	bit-wise exclusive OR (XOR) of a and b
a AND b	bit-wise AND of a and b
a OR b	bit-wise inclusive OR of a and b
LSk(a)	left shift of a by k bits
RSk(a)	right shift of a by k bits
LRk(a)	left rotate (cyclic left shift) of a by k bits
RRk(a)	right rotate (cyclic right shift) of a by k bits
ā	bit-wise complement of a
a ‖ b	concatenation of a and b
Sets
	empty set
#A	cardinality of set A
	a is an element of set A
A ⊆ B	set A is contained in set B
A ⊈ B	set A is not contained in set B
	set A is properly contained in set B
A ∪ B	union of sets A and B
A ⊎ B	disjoint union of sets A and B
A ∩ B	intersection of sets A and B
A B	difference of sets A and B
Ā	complement of set A (in a bigger set)
A × B	(Cartesian) product of sets A and B
	set of all natural numbers, that is, {1, 2, 3, . . .}
	set of all non-negative integers, that is, {0, 1, 2, . . .}
	set of all integers, that is, {. . . , –2, –1, 0, 1, 2, . . .}
	set of all (positive) prime numbers, that is, {2, 3, 5, 7, . . .}
	set of all rational numbers, that is,
	set of all non-zero rational numbers
	set of all real numbers
	set of all non-zero real numbers
	set of all non-negative real numbers
	set of all complex numbers
	set of all non-zero complex numbers
	, can be represented by the set {0, 1, . . . , n –1}
	group of units in , can be represented as {a | 0 ≤ a < n, gcd(a, n) = 1}
	finite field of cardinality q
	multiplicative group of , that is,
	ring of integers of number field K
	group of units of
	ring of p-adic integers
	field of p-adic numbers
Up	group of units of
Functions and relations
f : A → B	f is a function from set A to set B
f : A ↪ B	f is an injective function from set A to set B
f : A ↠ B	f is a surjective function from set A to set B
a ↦ b	a is mapped to b (by a function)
f ο g	composition of functions f and g (applied from right to left)
f–1	inverse of bijective function f
Ker f	kernel of function (homomorphism) f
Im f	image of function f
~	equivalent to
[a]	equivalence class of a
Groups
aH	coset in a multiplicative group
a + H	coset in an additive group
HK	internal direct product of (sub)groups H and K
H × K	external direct product of (sub)groups H and K
[G : H]	index of subgroup H in group G
G/H	quotient group
G1 ≅ G2	groups G1 and G2 are isomorphic
ord G	order (that is, cardinality) of group G
ordG a	order of element a in group G
Exp G	exponent of group G
Z(G)	centre of group G
C(a)	centralizer of group element a
GLn(K)	general linear group over field K (of n × n matrices)
SLn(K)	special linear group over field K (of n × n matrices)
Gtors	torsion subgroup of G
Rings
char A	characteristic of ring A
A × B	direct product of rings A and B
A*	multiplicative group of units of ring A
〈S〉	for ring A, ideal generated by S ⊆ A, also written as
〈a〉	for ring A, principal ideal generated by , also written as aA and Aa
a ≡ b (mod )	a is congruent to b modulo ideal , that is,
A ≅ B	rings A and B are isomorphic
	quotient ring (modulo ideal )
a|b	a divides b (in some ring)
vp(a)	multiplicity of prime p in element a
pk‖a	k = vp(a)
	nilradical of ring A
Ared	reduction of ring A, equals
gcd(a, b)	greatest common divisor of elements a and b
lcm(a, b)	least common multiple of elements a and b
	sum of ideals and
	intersection of ideals and
	product of ideals and
	root (or radical) of ideal
Q(A)	total quotient ring of ring A (quotient field of A, if A is an integral domain)
S–1A	localization of ring A at multiplicative set S
	localization of ring A at prime ideal
	ring of integers of number field K
N()	norm of ideal (in a Dedekind domain)
CRT	Chinese remainder theorem
ED	Euclidean domain
DD	Dedekind domain
DVD (or DVR)	discrete valuation domain (or ring)
PID	principal ideal domain
UFD	unique factorization domain
Fields
char K	characteristic of field K
K*	multiplicative group of units of field K, that is, K {0}
	algebraic closure of field K
[K : F]	degree of the field extension F ⊆ K
K[a]
K(a)	{f(a)/g(a) | f(X), , g(a) ≠ 0}
Aut K	group of automorphisms of field K
AutF K	for field extension F ⊆ K, group of F-automorphisms of K (also Gal(K|F))
FixF H	for field extension F ⊆ K, fixed field of subgroup H of AutF K
	finite field of cardinality q
	multiplicative group of units of , that is,
Tr	trace function
TrK|F (a)	for field extension F ⊆ K, trace of over F
N	norm function
NK|F (a)	for field extension F ⊆ K, norm of over F
	Frobenius automorphism , a ↦ aq
	ring of integers of number field K
	group of units of
ΔK	discriminant of number field K
	ring of p-adic integers
	field of p-adic numbers
Up	group of units of
| |p	p-adic norm on
Integers
a quot b	quotient of Euclidean division of a by b ≠ 0
a rem b	remainder of Euclidean division of a by b ≠ 0
a|b	a divides b in , that is, b = ca for some
vp(a)	multiplicity of prime p in non-zero integer a
gcd(a, b)	greatest common divisor of integers a and b (not both zero)
lcm(a, b)	least common multiple of integers a and b
a ≡ b (mod n)	a is congruent to b modulo n
a–1 (mod n)	multiplicative inverse of a modulo n (given that gcd(a, n) = 1)
φ(n)	Euler’s totient function
	Legendre (or Jacobi) symbol
[a]n	coset
ordn a	multiplicative order of a modulo n (given that gcd(a, n) = 1)
μ(n)	Möbius function
π(x)	number of primes between 1 and positive real number x
Li(x)	Gauss’ Li function
ψ(x, y)	fraction of positive integers ≤ x, that are y-smooth
ζ(s)	Riemann zeta function
RH	Riemann hypothesis
ERH	extended Riemann hypothesis
Mn	2n – 1 (Mersenne number)
ℜ	232, standard radix for representation of multiple-precision integers
Polynomials
A[X1, . . . , Xn]	polynomial ring in indeterminates X1, . . . , Xn over ring A
A(X1, . . . , Xn)	ring of rational functions in indeterminates X1, . . . , Xn over ring A
deg f	degree of polynomial f
lc f	leading coefficient of polynomial f
minpolyα,K(X)	minimal polynomial of α over field K, belongs to K[X]
cont f	content of polynomial f
pp f	primitive part of polynomial f
f′(X)	formal derivative of polynomial f(X)
Δ(f)	discriminant of polynomial f
	the polynomial
μm	group of m-th roots of unity
Фm	m-th cyclotomic polynomial
Vector spaces, modules and matrices
dimK V	dimension of vector space V over field K
Span S	span of subset S of a vector space
HomK(V, W)	set of all K-linear transformations V → W
EndK(V)	set of all K-linear transformations V → V
M/N	quotient vector space or module
M ≅ N	vector spaces or modules M and N are isomorphic
	direct product of modules Mi,
	direct sum of modules Mi,
At	transpose of matrix (or vector) A
A–1	inverse of matrix A
Rank T	rank of matrix or linear transformation T
RankA M	rank of A-module M
Null T	nullity of matrix or linear transformation T
(M : N)	for A-module M and submodule N, the ideal of A
AnnA(M)	annihilator of A-module M, same as (M : 0)
Tors M	torsion submodule of M
A[S]	A-algebra generated by set S
〈v, w〉	inner product of two real vectors v and w
Algebraic curves
	n-dimensional affine space over field K
	n-dimensional projective space over field K
(x1, . . . , xn)	homogeneous coordinates of a point in
[x0, x1, . . . , xn]	projective coordinates of a point in
f(h)	homogenization of polynomial f
C(K)	set of K-rational points over curve C defined over field K
K[C]	ring of polynomial functions on curve C defined over K
K(C)	field of rational functions on curve C defined over K
[P]	point P on a curve in formal sums
ordP (r)	order of rational function r at point P
DivK (C)	group of divisors on curve C defined over field K
	group of divisors of degree 0 on curve C defined over field K
DivK(r)	divisor of a rational function r
PrinK(C)	group of principal divisors on curve C defined over field K
	Jacobian of curve C defined over field K
PicK(C)	Picard group of curve C (equals DivK(C)/ PrinK(C))
	, same as Jacobian
	point at infinity on an elliptic or a hyperelliptic curve
Δ(E)	discriminant of elliptic curve E
j(E)	j-invariant of elliptic curve E
E(K)	group of points on elliptic curve E defined over field K
P + Q	sum of two points P,
mP	m-th multiple (that is, m-fold sum) of point
ψm, , fm	m-th division polynomials
t	trace of Frobenius of elliptic curve
EK[m]	group of m-torsion points in E(K)
E[m]	abbreviation for
em	Weil pairing (a map E[m] × E[m] → μm)
Div(a, b)	representation of reduced divisor on hyperelliptic curve by polynomials a, b
Probability and statistics
Pr(E)	probability of event E
Pr(E1|E2)	conditional probability of event E1 given event E2
E(X)	expectation of random variable X
Var(X)	variance of random variable X
σX	standard deviation of random variable X (equals )
Cov(X, Y)	covariance of random variables X, Y
ρX,Y	correlation coefficient of random variables X, Y
Computational complexity
f = O(g)	big-Oh notation: f is of the order of g
f = Ω(g)	big-Omega notation: g is of the order of f
f = Θ(g)	big-Theta notation: f and g have the same order
f = o(g)	small-oh notation: f is of strictly smaller order than g
f = ω(g)	small-omega notation: f is of strictly larger order than g
f = O~(g)	soft-Oh notation: f = O(g logk g) for real constant k ≥ 0
	problem P1 is polynomial-time reducible to problem P2
P1 ≅ P2	problems P1 and P2 are polynomial-time equivalent
Intractable problems
CVP	closest vector problem
DHP	(finite field) Diffie–Hellman problem
DLP	(finite field) discrete logarithm problem
ECDHP	elliptic curve Diffie–Hellman problem
ECDLP	elliptic curve discrete logarithm problem
HECDHP	hyperelliptic curve Diffie–Hellman problem
HECDLP	hyperelliptic curve discrete logarithm problem
GIFP	general integer factorization problem
IFP	integer factorization problem
QRP	quadratic residuosity problem
RSAIFP	RSA integer factorization problem
RSAKIP	RSA key inversion problem
RSAP	RSA problem
SQRTP	modular square root problem
SSP	subset sum problem
SVP	shortest vector problem
Algorithms
ADH	Adleman, DeMarrais and Huang’s algorithm
AES	advanced encryption standard
AKS	Agarwal, Kayal and Saxena’s deterministic primality test
BSGS	Shanks’ baby-step–giant-step method
CBC	cipher-block chaining mode
CFB	cipher feedback mode
CSM	cubic sieve method
CSPRBG	cryptographically strong pseudorandom bit generator
CvA	Chaum and Van Antwerpen’s undeniable signature scheme
DDF	distinct-degree factorization
DES	data encryption standard
DH	Diffie–Hellman key exchange
DPA	differential power analysis
DSA	digital signature algorithm
DSS	digital signature standard
ECB	electronic codebook mode
ECDSA	elliptic curve digital signature algorithm
ECM	elliptic curve method
E-D-E	encryption–decryption–encryption scheme of triple encryption
EDF	equal-degree factorization
EG	Eschenauer and Gligor’s scheme
FEAL	fast data encipherment algorithm
FFS	Feige, Fiat and Shamir’s zero-knowledge protocol
GKR	Gennaro, Krawczyk and Rabin’s RSA-based undeniable signature scheme
GNFSM	general number field sieve method
GQ	Guillou and Quisquater’s zero-knowledge protocol
HFE	cryptosystem based on hidden field equations
ICM	index calculus method
IDEA	international data encryption algorithm
KLCHKP	braid group cryptosystem
L3	Lenstra–Lenstra–Lovasz algorithm
LFSR	linear feedback shift register
LSM	linear sieve method
LUC	cryptosystem based on Lucas sequences
MOV	Menezes, Okamoto and Vanstone’s reduction
MPQSM	multiple polynomial quadratic sieve method
MQV	Menezes–Qu–Vanstone key exchange
NFSM	number field sieve method
NR	Nyberg–Rueppel signature algorithm
NTRU	Hoffstein, Pipher and Silverman’s encryption algorithm
NTRUSign	NTRU signature algorithm
OAEP	optimal asymmetric encryption procedure
OFB	output feedback mode
PAP	pretty awful privacy
PGP	pretty good privacy
PH	Pohlig–Hellman method
PRBG	pseudorandom bit generator
PSS	probabilistic signature scheme
QSM	quadratic sieve method
RSA	Rivest, Shamir and Adleman’s algorithm
SAFER	secure and fast encryption routine
Satoh–FGH	Point counting algorithm on elliptic curves over fields of characteristic 2
SDSA	shortened digital signature algorithm
SEA	Schoof, Elkies and Atkins’ algorithm for point counting on elliptic curves
SETUP	secretly embedded trapdoor with universal protection
SFF	square-free factorization
SHA	secure hash algorithm
SmartASS	algorithm for computing discrete logs in anomalous elliptic curves
SNFSM	special number field sieve method
SPA	simple power analysis
TWINKLE	the Weizmann Institute key location engine
TWIRL	the Weizmann Institute relation locator
XCM	xedni calculus method
XSL	extended sparse linearization attack
XTR	efficient and compact subgroup trace representation
ZK	zero-knowledge
Quantum computation
|ψ〉	ket notation for vector ψ
	inner product of vectors |ψ〉 and
‖ψ‖	norm of vector |ψ〉 (equals )
	n-dimensional Hilbert space (over )
|0〉, |1〉, . . . , |n – 1〉	orthonormal basis of
cbit	classical bit
qubit	quantum bit
⊗	tensor product of Hilbert spaces
F	Fourier transform
H	Hadamard transform
I	Identity transform
X	Exchange transform
Z	Z transform
Computational primitives
ulong	32-bit unsigned integer data type (unsigned long)
ullong	64-bit unsigned integer data type (unsigned long long)
a := b	assignment operator (returns the value assigned)
+, –, ×, /, %	arithmetic operators
++, – –	increment and decrement operators
a ◊ = b	a := a ◊ b for
=, ≠, >, <, ≥, ≤	comparison operators
1	True as a condition
if	conditional statement: if (condition)···
if-else	conditional statement: if (condition)··· , else···
while	while loop: while (condition)···
do	do loop: do···while (condition)
for	for loop: for (range of values)···
{···}	block of statements
, or. or new-line	statement terminator
/*··· */	comment
return	return from this routine
Miscellaneous
	end of (visible or invisible) proof
	end of item (like example, definition, assumption)
[H]	hint available in Appendix D