Engineering / Mathematics — Integer Algorithms
Machine Models and Complexity Theory
The random access machine and Turing machine models, what counts as a primitive operation, and how the choice of model affects stated complexities.
Executive summary
A complexity claim is meaningless without a machine model, because the model fixes what a single step costs. The two standard choices — the Turing machine and the random access machine — give different answers for the same algorithm.
For multiprecision arithmetic the distinction matters concretely: whether multiplying two machine words costs one unit or a number of units proportional to their length changes stated complexities by a full factor.
Learning objectives
- Distinguish the RAM and Turing machine cost models.
- Explain the difference between uniform and logarithmic cost.
- Identify which model a stated complexity assumes.
01Two models
Turing machine
A tape and a head. Every operation is local, so accessing a distant cell costs time proportional to the distance. Realistic about data movement, awkward for describing algorithms.
Random access machine
Indexed memory with constant-time access, and a small instruction set on machine words. Matches how algorithms are actually written and how real hardware behaves.
Complexity results in this subject are almost always stated for a RAM with logarithmic cost, counting bit operations. That is the convention used throughout this collection unless a page says otherwise.
02Uniform versus logarithmic cost
Cost measures
Uniform cost: every primitive operation costs 1, regardless of operand size.
Logarithmic cost: an operation on k-bit operands costs a function of k — typically k for addition and k² for schoolbook multiplication.
The practical compromise is a word RAM: operations on fixed-width machine words cost 1, and multiprecision operations cost a number of word operations proportional to the operand length in words. This matches implementation reality and differs from the bit model only by a constant factor.
03What counts as primitive
| Operation | Bit cost, schoolbook | Notes |
|---|---|---|
| Addition, subtraction | O(ℓ) | Linear in operand length |
| Multiplication | O(ℓ²) | O(ℓ^1.585) with Karatsuba |
| Division with remainder | O(ℓ²) | Same order as multiplication |
| Comparison | O(ℓ) | Worst case scans the whole operand |
| Shift by k bits | O(ℓ) | Effectively free in a word representation |
These costs propagate. Modular exponentiation with a k-bit exponent performs O(k) multiplications of len(n)-bit numbers, giving O(k · len(n)²) overall — a bound that only makes sense once the per-multiplication cost is fixed by the model.
04Frequently asked questions
Does the model choice ever change whether a problem is tractable?
Between reasonable models, no — the polynomial-time class is robust across Turing machines, RAMs with logarithmic cost, and word RAMs. Between reasonable and unreasonable models it certainly does, which is why uniform cost is rejected.
Where does parallelism fit?
Outside the standard model. Parallel complexity is measured separately and does not change sequential bounds. Practical factoring records use massive parallelism, which affects wall-clock feasibility but not the asymptotic classification.
Are quantum models relevant here?
They change the picture entirely for this subject specifically. Shor's algorithm factors integers and computes discrete logarithms in polynomial time on a quantum computer, which is why post-quantum cryptography moves away from both assumptions. The classical analysis in this collection assumes a classical machine.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 36-39.
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.