茶年 · 中文维基百科

可能質數

Wikipedia · 2025-03-27 维基百科 👁 1 阅读

在數論上，可能質數（probable prime，縮寫為PRP）指的是一個滿足所有質數都會滿足、但多數合成數都不會滿足的特定條件的數。不同的可能質數會有不同的條件。雖說一些可能質數會是合成數（也就所謂的偽質數），但一般會透過條件的選取讓這種狀況變得少見。

像例如一個基於費馬小定理的費馬合成數測試，其原理如次：在給定一個的狀況下，選取一個不是的倍數的數（一般會在1 的範圍中選取），然後計算a^{n-1}\pmod{n}。若結果不是1，則是合成數；若結果是1，那就有可能是質數，這種情況下，可稱是以為底的可能質數。一個以為底的弱可能質數指的是一個以為底的可能質數，但這個可能質數不是以為底的強可能質數。

對於固定的底，一個以之為底的合成數不太可能會是可能質數（也就所謂的偽質數），像例如說在不大於25 \times 10^9的數字中，有11,408,012,595個奇合成數，但只有21,853個以2為底的偽質數；相比之下在同樣的區間中有1,091,987,404個奇質數。

性質
質數可能性是高效質數判定演算法的基礎，而這類演算法被應用於密碼學中。這些演算法通常在本質上是隨機化的。這主意背後的想法是盡管對於任意固定的底而言，都有實際上是合成數的以為底的可能質數，因此會期望說對於任意的合成數，存在一個P ，使得在隨機選取時，是以為底的偽質數的機率不會超過。在這種狀況下，假如重複類似的操作次，每次都選取新的，那麼是以為底的偽質數的機率就不會大於P^k。有鑑於P^k指數性遞減之故，因此只需要選取適量的，就能把機率壓低到可忽略地小（相對電腦硬體出現錯誤的機率等而言）的程度。

然而壞消息是，由於卡邁克爾數之故，上述的理論是對於弱可能質數而言是不成立的；不過對於諸如強可能質數（像例如由米勒-拉賓質數判定法給出的那些，其中P=\frac{1}{4}）或歐拉可能質數（由給出，其中P=\frac{1}{2}）等對質數可能性測試更精進的想法而言，上述的理論是成立的。

即使在需要使用確定性質數判定證明的狀況下，一個有用的步驟是先使用隨機化質數判定法，這可迅速（且確定）地去掉絕大多數的合成數。

有時質數判定測試會與小的偽質數表一起使用，好快速確定小於特定門檻的數字的質數性。

變體
一個以為底的歐拉可能質數是一個較強的理論指出的可能是質數的正整數，其中對於任意的質數，a^\frac{(p-1)}{2}\equiv(\tfrac{a}{p})\pmod{p}，其中(\tfrac{a}{p})是雅可比符號。

一個是合成數歐拉可能質又稱以為底的歐拉-雅可比偽質數。最小的以2為底的歐拉-雅可比偽質數是561。在小於25 \times 10^9的數字中，有11347個以2為底的歐拉-雅可比偽質數。

這測試可利用1的平方根除以p必然等於1或-1這件事實來改進。而這可藉由n=2^s\cdot d+1這點（其中是奇數）達成。若滿足以下條件，則稱是以為底的強可能質數：

: a^d\equiv 1\pmod n,\;
或
: a^{d\cdot 2^r}\equiv -1\pmod n\text{ for some }0\leq r\leq s-1. \,

一個實際上是合成數的以為底的強可能質數又稱為以為底的強偽質數。所有以為底的強偽質數也都是在相同底下的歐拉可能質數，但反過來不盡然成立。

最小的以2為底的2強偽質數是2047。在小於25 \times 10^9的數字中，有4842個以2為底的2強偽質數。

此外也有基於盧卡斯數列的。盧卡斯可能質數可單獨使用。另外是混合盧卡斯測試和強可能質數測試的質數判定法。

測試是否為強可能質數的範例
以下為測試97是否是以2為底的強可能質數的步驟：

  • 第一步：找到使得96=d\cdot 2^s的d和s，其中d是奇數。

** 先從s=0開始，此時d會是96。
** 慢慢增加s，之後會發現說d=3且s=5，而這是因為96=3\cdot 2^5之故。

  • 第二步：在1 的範圍內選取a，此處選取a = 2。
  • 第三步：計算a^d \bmod n，也就是計算2^3 \bmod 97。由於這不同餘於1之故，因此測試下一個條件。
  • 第四步：在0 \leq r 的範圍內計算2^{3\cdot 2^r} \bmod 97。假若其中一個的結果與96同餘，那97是可能質數；不然97就篤定是合成數。以下是對各個r運算的結果：

** r=0: 2^3 \equiv 8 \pmod{97}
** r=1: 2^6 \equiv 64 \pmod{97}
** r=2: 2^{12} \equiv 22 \pmod{97}
** r=3: 2^{24} \equiv 96 \pmod{97}

  • 因此，97是以2為底的強可能質數，也因此是以2為底的可能質數。

參見
*
*

  • 歐拉-雅可比偽質數

*

  • 米勒-拉賓質數判定法
  • 佩蘭質數判定法
  • 卡邁克爾數

外部連結

參考資料

#偽素數

评论 (0)

  • 还没有评论，来抢沙发吧。