伪素数
伪素数是有和質數相同的性質（像是通過隨機性的素性测试判定），但本身是合数的数，根据所满足的性质的不同可以划分不同种类的伪素数。其中最有名的伪素数是满足费马小定理的合数，即费马伪素数。 伪素数的重要性 公开密钥加密的基礎是建立在大的合數，很難進行因數分解的基礎上，因此質數在公开密钥加密裡非常重要，而伪素数可能被誤當成質數，影響公开密钥加密。 卡爾·帕梅朗斯在1988年估計要將144位數的數字進行因數分解，其成本約為一千萬美元，若要分解20…
标签：#伪素数
共 7 篇文章
费马伪素数
费马伪素数（）是指满足费马小定理的伪素数，也是最重要的一类伪素数。 其定义是：对自然数x和一个与其互素的自然数a，如果x整除 ax-1 - 1，则称x是一个以a为底的费马伪素数或者关于a的费马伪素数。最小的费马伪素数是341（=11×31，关于2）。如果x关于任何与其互素的数都是费马伪素数，则称x是绝对伪素数（或卡邁克爾數，来自找到第一个绝对伪素数的数学家羅伯特·丹尼·卡邁克爾）。最小的绝对伪素数是561。 有人已经证明了费马伪素数的个…
欧拉伪素数
欧拉伪素数（）是伪素数的一种。对于奇合数n以及与其互素的自然数a，如果 : a^{(n-1)/2} \equiv \pm 1\pmod{n} 成立，则称n为关于a的欧拉伪素数。欧拉伪素数是费马伪素数的推广，所有欧拉伪素数同时也是费马伪素数。 与费马伪素数类似，欧拉伪素数的定义也是源于费马小定理。该定理表明，对于素数p以及整数a，有 ap−1 = 1 (mod p)。对大于2的素数p，p可以表示为2q + 1 ，其中q为整数。于是a(2q…
欧拉-雅可比伪素数
欧拉－雅可比伪素数（）是伪素数的一种。对于奇合数n以及与其互素的自然数a，如果 : a^{(n-1)/2} \equiv \left(\frac{a}{n}\right)\pmod{n} 成立（其中\left(\frac{a}{n}\right)为雅可比符号），则称n为以a為底的欧拉－雅可比伪素数，或简称为欧拉伪素数。 欧拉－雅可比伪素数是欧拉伪素数的推广，所有欧拉－雅可比伪素数同时也是费马伪素数与欧拉伪素数。由于上式对所有素数都成立，…
卡邁克爾數
在數論上，卡邁克爾數（）是正合成數n，且使得對於所有跟n互質的整數b，b^{n-1} \equiv 1 \pmod{n}。 概觀 費馬小定理說明所有質數都有這個性質。在這方面，卡邁克爾數和質數十分相似，所以它們稱為偽質數。 因為這些數的存在，使得费马素性检验變得不可靠。不過，它仍可用於證明一個數是合數。另一方面，隨着數越來越大，卡邁克爾數變得越來越少，1至10^{17}有585 355個卡邁克爾數。 卡邁克爾數的一個等價的定義在Kors…
中国猜想
在数论中，中国猜想是一个被证伪的猜想，即一个整数n是素数，当且仅当2^n-2能被n整除——换句话说，整数n是素数当且仅当2^n \equiv 2\pmod{n} 。如果n是素数，那么2^n \equiv 2\pmod{n}成立 （这是费马小定理的一个特例），然而费马小定理的逆命题是错误的，因此整个猜想也是错误的。最小的反例是n=341=11×31。使2^n-2能被n整除的合数n称为Poulet数。它们是一类特殊的费马伪素数。 历史 尽管…
強偽質數
強偽質數是指一種能通过米勒-拉宾检验的合数。所有质数都能通过这个检验，但有一小部分合数也能通过這個檢驗。根據费马小定理的推论，強偽質數也是伪質數。 参考文献