Để nhân 2 số nguyên, ta thường dùng quy tắc nhân từng chữ số của một số với số còn lại theo từng hàng rồi cộng kết quả lại. Nếu 
là số bít (trong hệ nhị phân, hoặc số chữ số trong hệ thập phân) của 2 số thì thuật toán được học từ thời phổ thông này cần sử dụng 
phép tính (cộng và nhân bằng bảng cửu chương) để tính ra kết quả cuối cùng.
Ví dụ:
Karatsuba-Ofman đã áp dụng kỹ thuật chia để trị để tăng tốc thuật toán nhân 2 số nguyên này. Thuật toán của 2 ông như sau:
procedure 
Input: 2 số 
có bit.
Output: Tích 
.
Giả sử 
, nếu cần thêm các chữ số 
vào đằng trước .
- If
return (tính bằng bảng cửu chương).
- else chia thành các phần có
-bit: 
.
Như vậy: 
còn
- return
Qua các bước của thuật toán Karatsuba-Ofman, ta có thể dễ dàng thấy được tính đúng đắn của thuật toán, nghĩa là thuật toán luôn trả lại 
. Bây giờ ta tìm hiểu độ phức tạp của thuật toán trên. Gọi 
là số tính toán cần thiết để nhân 2 số -bit bằng thủ tục 
ở trên. Ta có
trong đó 
là số tính toán của các bước 3,4,5 (nhân các số có bit) còn 
là số tính toán của các bước còn lại. Để ý là bước 7 thực chất chỉ gồm phép dịch trái (shift left) các số 
và phép cộng để tính 
. Áp dụng định lý tổng quát ta tính được
Như vậy, thuật toán nhân 2 số nguyên của Karatsuba-Ofman cũng có độ phức tạp thuật toán đa thức nhưng có bậc 
nhỏ hơn 
. Với lớn (cỡ vài nghìn hoặc vài chục nghìn), thuật toán Karatsuba-Ofman giảm đáng kể thời gian nhân 2 số nguyên. Năm 1963, Toom chứng minh rằng có thể nhân 2 số nguyên với độ phức tạp 
với 
bất kì.
Nếu ta viết
trong đó 
là các chữ số, 
là hệ cơ sở (ở đây, 
). Khi đó có thể hiểu là việc tính giá trị của phép nhân 2 đa thức 
tại . Với nhận xét này, Schönhage và Strassen đã sử dụng phép biến đổi Fourier nhanh (FFT – Fast Fourier Transform) để tạo ra thuật toán nhân 2 số nguyên với độ phức tạp 
. Hai ông còn đưa ra giả thuyết là có tồn tại thuật toán nhân 2 số nguyên với độ phức tạp 
nhưng đến nay vẫn chưa có thuật toán nào như vậy được tìm ra.
