目录
17 关系: 埃拉托斯特尼筛法，卡内基梅隆大学，卢卡斯-莱默检验法，合数，广义黎曼猜想，伪代码，快速傅里叶变换，确定性算法，產業等級質數，随机化算法，试除法，質數判定法則，费马小定理，费马素性检验，迈克尔·拉宾，耶路撒冷希伯來大學，最大公因數。
- 有限域
- 素性测试
埃拉托斯特尼筛法
埃拉托斯特尼筛法（κόσκινον Ἐρατοσθένους，sieve of Eratosthenes ），簡稱--，也有人称素数筛。这是一種簡單且历史悠久的筛法，用來找出一定範圍內所有的質數。 所使用的原理是從2開始，將每個質數的各個倍數，標記成合數。一個質數的各個倍數，是一個差為此質數本身的等差數列。此為這個篩法和試除法不同的關鍵之處，後者是以質數來測試每個待測數能否被整除。 埃拉托斯特尼篩法是列出所有小質數最有效的方法之一，其名字來自於古希臘數學家埃拉托斯特尼，並且被描述在另一位古希臘數學家尼科馬庫斯所著的《算術入門》中。.
卡内基梅隆大学
#重定向 卡内基·梅隆大学.
卢卡斯-莱默检验法
数学中，卢卡斯-莱默检验法（Lucas–Lehmer primality test）是检验梅森数的素性检验，是由爱德华·卢卡斯于1878年完善，随后于1930年代将其改进。 因特网梅森素数大搜索用这个检验法找到了不少很大的素数，最近几个最大的素数就是这个项目发现的。由于梅森数比随机选择的整数更有可能是素数，因此他们认为这是一个极有用的方法。.
合数
合數（也稱為合成數）是因數除了1和其本身外具有另一因數的正整數（定義為包含1和本身的因數大於或等於3個的正整數）。依照定義，每一個大於1的整數若不是質數，就會是合數。而0與1則被認為不是質數，也不是合數。例如，整數14是一個合數，因為它可以被分解成2 × 7。 起初105个合数为：4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87 88, 90, 91, 92, 93, 94, 95, 96, 98, 99, 100, 102, 104, 105, 106, 108, 110, 111, 112, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 128, 129, 130, 132, 133, 134, 135, 136, 138, 140,141,142,143,144,145,146,147,148,150.
查看 米勒-拉宾检验和合数
广义黎曼猜想
黎曼猜想是数学中最重要的猜想之一，描述了黎曼ζ函数非平凡零点的分布规律。而其中黎曼ζ函数可以用各种整体L函数（global L-function）替代，由此得到黎曼猜想不同类型的推广。这些推广的猜想描述的是不同L函数非平凡零点分布的规律。许多数学家相信这些猜想是正确的。不过其中仅有部分函数域情形下的推广得到了证明。 整体L函数可以与椭圆曲线、数域（此时称为戴德金ζ函数）、马斯形式（Maass form）或狄利克雷特征（此时称为狄利克雷L函数）相联系。其中，描述戴德金ζ函数的黎曼猜想被称为扩展黎曼猜想（extended Riemann hypothesis，ERH），而描述狄利克雷L函数的黎曼猜想则被称为广义黎曼猜想（generalized Riemann hypothesis，GRH）。（也有许多数学家用“广义黎曼猜想”用作对各种整体L函数推广的总称，而非单指狄利克雷L函数下的情形。）.
伪代码
伪代码（pseudocode），又称为虚拟代码，是高层次描述算法的一种方法。它不是一种现实存在的编程语言（已经出现了类似伪代码的语言，参见Nuva）；它可能综合使用多种编程语言的语法、保留字，甚至会用到自然语言。 它以编程语言的书写形式指明算法的职能。相比于程序语言（例如Java、C++、C、Delphi 等等）它更类似自然语言。它是--、不标准的语言。我们可以将整个算法运行过程的结构用接近自然语言的形式（这里可以使用任何一种作者熟悉的文字，例如中文、英文，重点是将程序的意思表达出来）描述出来。使用伪代码，可以帮助我们更好的表述算法，不用拘泥于具体的实现。 人们在用不同的编程语言实现同一个算法时意识到，他们做出来的实现（而非功能）很不同。程序员要理解一个用他并不熟悉的编程语言编写的程序，可能是很困难的，因为程序语言的形式限制了程序员对程序关键部分的理解。伪代码就这样应运而生了。 当考虑算法功能（而不是其语言实现）时，伪代码常常得到应用。计算机科学在教学中通常使用伪代码，以使得所有的程序员都能理解。.
查看 米勒-拉宾检验和伪代码
快速傅里叶变换
快速傅里叶变换（Fast Fourier Transform, FFT），是快速计算序列的离散傅里叶变换（DFT）或其逆变换的方法。傅里叶分析将信号从原始域（通常是时间或空间）转换到頻域的表示或者逆过来转换。FFT会通过把DFT矩阵分解为稀疏（大多为零）因子之积来快速计算此类变换。 因此，它能够将计算DFT的复杂度从只用DFT定义计算需要的 O(n^2)，降低到 O(n \log n)，其中 n 为数据大小。 快速傅里叶变换广泛的应用于工程、科学和数学领域。这里的基本思想在1965年才得到普及，但早在1805年就已推导出来。 1994年美國數學家把FFT描述为“我们一生中最重要的数值算法”，它还被IEEE科学与工程计算期刊列入20世纪十大算法。.
确定性算法
确定性算法（deterministic algorithm）是计算机算法的一类。如果以算法的每一步骤是否确定来分类，计算机算法可以分为确定性算法和随机化算法。 Category:演算法 Category:算法分析.
產業等級質數
業等級質數（Industrial-grade primes）是由取名的數，表示一整數尚未以嚴謹的方式證實是質數，但已通過了測試，像是米勒-拉宾检验（有正的，不可忽略的失效率），或是，目前還沒有任一個合數通過此測試。 產業等級質數有時會用來代替一些演算法中需要的認證質數，像RSA加密演算法就需要用戶產生大的質數。若數字位數超過100位，證明它們是產業等級質數會比素性测试簡單很多。前者可以立即產生，而其不是質數的失效率很低，因此在實務上幾乎不可能失效。換句話說，對於於這些數字是質數可以抱持非常高的信心，不過不是一定成立。.
随机化算法
随机化算法（randomized algorithm），是这样一种算法，在算法中使用了随机函数，且随机函数的返回值直接或者间接的影响了算法的执行流程或执行结果。就是将算法的某一步或某几步置于运气的控制之下，即该算法在运行的过程中的某一步或某几步涉及一个随机决策，或者说其中的一个决策依赖于某种随机事件。 Category:算法分析.
试除法
试除法是整数分解算法中最简单和最容易理解的算法。首次出現於義大利數學家斐波那契出版於1202年的著作。 给定一个合数n（这里，n是待分解的正整数），试除法看成是用小于等于\sqrt的每个素数去试除待分解的整数。如果找到一个数能够整除除尽，这个数就是待分解整数的因子。试除法一定能够找到n的因子。因为它检查n的所有可能的因子，所以如果这个算法“失败”，也就证明了n是个素数。试除法可以从几条途径来完善。例如，n的末位数不是0或者5，那么算法中就可以跳过末位数是5的因子。如果末位数是2，检查偶数因子就可以了。 某种意义上说，试除法是个效率非常低的算法，如果从2开始，一直算到\sqrt需要 \pi(\sqrt)次试除，这里pi(x)是小于x的素数的个数。这是不包括素性测试的。如果稍做变通——还是不包括素性测试——用小于\sqrt的奇数去简单的试除，则需要次。这意味着，如果n有大小接近的素因子（例如公钥密码学中用到的），试除法是不太可能实行的。但是，当n有至少一个小因子，试除法可以很快找到这个小因子。值得注意的是，对于随机的n，2是其因子的概率是50％，3是33％，等等，88％的正整数有小于100的因子，91％的有小于1000。.
查看 米勒-拉宾检验和试除法
質數判定法則
#重定向 素性测试.
费马小定理
费马小定理是数论中的一个定理：假如a是一个整数，p是一个質数，那么a^p - a 是p的倍数，可以表示为 如果a不是p的倍数，这个定理也可以写成 这个书写方式更加常用。（符号的应用请参见同餘。）.
费马素性检验
费马素性检验是一种質數判定法則，利用随机化算法判断一个数是合数还是可能是素数。.
迈克尔·拉宾
迈克尔·O·拉宾（Michael Oser Rabinמִיכָאֵל אֹשֶׁר רַבִּין， ）是一名以色列计算机科学家，1976年图灵奖得主。.
耶路撒冷希伯來大學
耶路撒冷希伯来大學（希伯来语： האוניברסיטה העברית בירושלים, HaUniversita HaIvrit BeYerushalaim；阿拉伯语： الجامعة العبرية في القدس, Al-Jāmi`ah al-`Ibriyyah fil-Quds; abbreviated HUJI）是在以色列繼以色列理工學院之後建立的第二所大学。.
最大公因數
数学中，兩個或多個整數的最大公因數（greatest common factor，hcf）指能够整除这些整数的最大正整数（这些整数不能都为零）。例如8和12的最大公因数为4。最大公因数也称最大公约数（greatest common divisor，gcd）。 整数序列a的最大公因数可以記為(a_1, a_2, \dots, a_n)或\gcd(a_1, a_2, \dots, a_n)。 求兩個整數最大公因數主要的方法：.
另见
有限域
素性测试
亦称为 Miller-Rabin 質數測試，米勒-拉賓素性检验。