數論主題列表和米勒-拉宾检验

快捷方式: 差异，相似，杰卡德相似系数，参考。

數論主題列表和米勒-拉宾检验之间的区别

數論主題列表 vs. 米勒-拉宾检验

這是數論的主題列表。參照. 米勒-拉賓質數判定法是一种質數判定法則，利用随机化算法判断一个数是合数还是可能是素数。卡内基梅隆大学的计算机系教授Gary Lee Miller首先提出了基于广义黎曼猜想的确定性算法，由于广义黎曼猜想并没有被证明，其后由以色列耶路撒冷希伯來大學的Michael O. Rabin教授作出修改，提出了不依赖于该假设的随机化算法。.

埃拉托斯特尼筛法

埃拉托斯特尼筛法（κόσκινον Ἐρατοσθένους，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函数下的情形。）.

广义黎曼猜想和數論主題列表 · 广义黎曼猜想和米勒-拉宾检验 · 查看更多 »

随机化算法

随机化算法（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的倍数，这个定理也可以写成 这个书写方式更加常用。（符号的应用请参见同餘。）.

數論主題列表和费马小定理 · 米勒-拉宾检验和费马小定理 · 查看更多 »

费马素性检验

费马素性检验是一种質數判定法則，利用随机化算法判断一个数是合数还是可能是素数。.

數論主題列表和费马素性检验 · 米勒-拉宾检验和费马素性检验 · 查看更多 »

最大公因數

数学中，兩個或多個整數的最大公因數（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)。 求兩個整數最大公因數主要的方法：.

數論主題列表和最大公因數 · 最大公因數和米勒-拉宾检验 · 查看更多 »