計算數論是數論的一個分支，它關注於尋找和實現高效的計算機演算法，以解決數論中的各種問題。近年來，在這個領域取得了很大的進展，無論是在計算機速度的提高方面，還是在尋找更高效的演算法方面。計算數論的兩個重要應用是大整數的素性測試和素因數分解。
素性測試被認為是容易的，因為非常大的通用數字（目前最多約 4000 位）可以被可靠地測試其素性。事實上，在 2002 年 8 月 6 日，Agrawal、Saxena 和 Kayal 找到了一個多項式時間演算法，用於測試和證明通用數字的素性。雖然這個演算法仍然不實用，但它是一個里程碑式的發現，因為多項式時間演算法被認為是容易的。另一方面，因式分解被認為是困難的，因為目前還沒有已知的多項式時間演算法用於分解整數。被分解的最大通用整數是 RSA-576，一個 174 位數字，它是兩個 87 位素數的乘積。素性測試容易但因式分解困難這一事實為安全加密提供了可能，例如RSA 加密。
