计算数论

计算数论是数论的一个分支，它关注于寻找和实现高效的计算机算法，以解决数论中的各种问题。近年来，在这个领域取得了很大的进展，无论是在计算机速度的提高方面，还是在寻找更高效的算法方面。计算数论的两个重要应用是大整数的素性测试和素因数分解。

素性测试被认为是容易的，因为非常大的通用数字（目前最多约 4000 位）可以被可靠地测试其素性。事实上，在 2002 年 8 月 6 日，Agrawal、Saxena 和 Kayal 找到了一个多项式时间算法，用于测试和证明通用数字的素性。虽然这个算法仍然不实用，但它是一个里程碑式的发现，因为多项式时间算法被认为是容易的。另一方面，因式分解被认为是困难的，因为目前还没有已知的多项式时间算法用于分解整数。被分解的最大通用整数是 RSA-576，一个 174 位数字，它是两个 87 位素数的乘积。素性测试容易但因式分解困难这一事实为安全加密提供了可能，例如RSA 加密。

计算数论中的其他问题包括计算大数的最大公约数，以及计算与数域相关的各种量，即类数和类群。