2、计算数论：概念、问题与复杂度

计算数论：概念、问题与复杂度

1. 计算数论概述

计算数论是数论与计算理论相结合的学科，即 Computational Number Theory = Number Theory ⊕ Computation Theory 。基本上，任何在数论中以计算为核心的主题都可视为计算数论的范畴。其目标在于利用计算技术解决数论问题，或者利用数论技术解决计算机科学问题。下面我们将介绍计算数论中的一些典型问题。

2. 典型计算数论问题

2.1 素性测试问题（Primality Testing Problem，PTP）

• 定义：输入为 (n > 1)，若 (n) 是素数，输出 “Yes”；否则输出 “No”。理论上，PTP 可在多项式时间内解决，但判断一个大数是否为素数仍具有挑战性。
• 梅森素数：形如 (M_p = 2^p - 1)（其中 (p) 是素数且 (2^p - 1) 也是素数）的数称为梅森素数。截至目前，仅发现了 47 个这样的 (p)，最早的 4 个在 2500 年前就已被发现。(2^{43112609} - 1) 是目前已知的最大梅森素数，也是世界上已知的最大素数。
• 奖金激励：电子前沿基金会（EFF）为发现满足特定条件的大素数提供了总计 550,000 美元的奖金，具体如下：
  | 奖金 | 新素数条件 |
  | ---- | ---- |
  | $50,000 | 至少 1000000 位 |
  | $100,000 | 至少 10000000 位 |