Engineering / Mathematics — Orientation
Mathematical Notation and Standing Conventions
The notational conventions, symbol set and standing assumptions used throughout the KEVOS computational number theory collection.
Executive summary
Notation in this field is largely settled but not entirely uniform, and small disagreements between texts cause real confusion — whether zero is a natural number, whether rings are assumed to have unity, whether the gcd of zero and zero is defined.
This page fixes the conventions used across the collection so that no page has to restate them.
Learning objectives
- Read the symbol set used throughout the collection without ambiguity.
- Know which conventions are choices rather than universal facts.
01Sets and number systems
| Symbol | Meaning |
|---|---|
Z | The integers, including negatives and zero |
Z≥0 | The non-negative integers |
Q, R, C | Rationals, reals, complex numbers |
Z_n | The integers modulo n, as a ring of residue classes |
Z_n* | The group of units modulo n |
F_q | The finite field with q elements |
R[X] | The ring of polynomials in X with coefficients in R |
02Conventions that are choices
The following are settled here by decision, not by mathematical necessity. Other texts differ.
- Rings are commutative with a multiplicative identity unless explicitly stated otherwise. This is a genuine restriction and it simplifies the theory considerably.
- The greatest common divisor is taken to be non-negative, so
gcd(a, 0) = |a|andgcd(0, 0) = 0. - Division with remainder produces a remainder in the range
0 ≤ r < |b|, not a symmetric range. - A prime is an integer greater than 1 with no positive divisors other than 1 and itself; 1 is not prime and negative primes are not used.
logwithout a base means the natural logarithm; binary logarithms are writtenlog2.
03Asymptotic and complexity notation
Cost is measured in bit operations unless stated otherwise. Counting arithmetic operations instead is sometimes convenient but conceals the growth of operand size, which for multiprecision arithmetic is precisely the quantity of interest.
O(f), Ω(f), Θ(f), o(f) — upper, lower, tight and strictly smaller growthThe length of an integer n in bits is written len(n) and is roughly log2 n. Complexity is always expressed in terms of input length, so an algorithm polynomial in n itself is exponential in the input size and does not count as efficient.
04Frequently asked questions
Why insist on bit operations rather than arithmetic operations?
Because the operands grow. An algorithm performing a fixed number of multiplications on numbers that double in length each round is not constant-time in any meaningful sense. Counting bit operations keeps the cost model honest about multiprecision arithmetic.
Is gcd(0, 0) = 0 standard?
It is the common convention and it makes the gcd a well-defined operation on all pairs, which matters when writing algorithms that must not special-case their inputs. Some texts leave it undefined.
Does the commutative restriction limit what can be covered?
It excludes non-abelian group theory and non-commutative ring theory, neither of which is needed for the algorithms here. Elliptic curve groups are abelian, and the multiplicative groups used in cryptography are abelian, so the restriction costs nothing in this domain.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages xiv.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.