Python を使用して素数を検出する方法の例

この記事では主に Python の素数検出の方法を紹介します。必要な方は参考にしてください:

因子検出:

検出係数、時間計算量 O(n^(1/2))

def is_prime(n):
  if n < 2:
    return False
  for i in xrange(2, int(n**0.5+1)):
    if n%i == 0:
      return False
  return True

フェルマーの小定理:

n が素数で、a が n より小さい任意の正の整数の場合、a の n 乗は法 n と合同です

実装方法:

基数 (たとえば、2) を選択します。大きな整数 p の場合、2^(p-1) と 1 が p を法として合同でない場合、p は一致しません。素数; それ以外の場合、p は素数になる可能性があります

2**(n-1)%n は計算す​​るのが簡単な数ではありません

モジュラー演算ルール:

(a^b) % p = ((a % p)^b) % p
(a * b) % p = (a % p * b % p) % p

X^N(% P) を計算します

はい

N が偶数の場合、X^N = (X *X)^[N/2];
N が奇数の場合、X^N = X*X^(N-1) = X *(X*X)^[N/2];

def xn_mod_p(x, n, p):
  if n == 0:
    return 1
  res = xn_mod_p((x*x)%p, n>>1, p)
  if n&1 != 0:
    res = (res*x)%p
  return res

また、以下のアルゴリズムのようにまとめると、二つの関数は同じです

def xn_mod_p2(x, n, p):
  res = 1
  n_bin = bin(n)[2:]
  for i in range(0, len(n_bin)):
    res = res**2 % p
    if n_bin[i] == '1':
      res = res * x % p
  return res

べき乗剰余演算の高速処理により、フェルマーテストが実現できます

フェルマー検定は、否定的な結論が得られた場合には正確ですが、肯定的な結論は間違っている可能性があります。大きな整数に対しては非常に効率的で、整数が増加するにつれて偽陽性率は減少します

def fermat_test_prime(n):
  if n == 1:
    return False
  if n == 2:
    return True
  res = xn_mod_p(2, n-1, n)
  return res == 1

MILLER-RABIN検出

Miller -Rabin 検出は、現在広く使用されている二次検出です

定理: p が素数で、0フェルマーの小定理: a^(p-1) ≡ 1(mod p)

これはミラーラビンの素数性検定の方法です。インデックス n-1 の因数 2 を続けて抽出し、n-1 を d*2^r (d は奇数) と表します。次に、計算する必要があるのは、a を n で割って d*2^r 乗した余りになります。したがって、a^(d * 2^(r-1)) は 1 に等しいか、n-1 に等しいかのいずれかになります。 a^(d * 2^(r-1)) が 1 に等しい場合、定理は引き続き a^(d * 2^(r-2)) に適用され、平方根はこの方法で a になるまで継続されます。 ^ は、特定の i (d * 2^i) mod n = n-1 に対して満たされるか、最後の指数の 2 が使用されて a^d mod n=1 または n-1 が得られます。このようにして、フェルマーの小定理は次の形式に強化されます:

因数 2 を可能な限り抽出し、n-1 を d*2^r で表します。n が素数の場合、a^d mod n のいずれかになります。 =1、または i が a^(d*2^i) mod n=n-1 (0<=i

定理: n が素数で、a が n より小さい正の整数の場合、n に対する a に基づくミラー テストは真になります。

ミラー テストは k 回実行されます。 、合成数を素数として扱うことの誤り確率は、最大値は 4^(-k) を超えません

def miller_rabin_witness(a, p):
  if p == 1:
    return False
  if p == 2:
    return True
  #p-1 = u*2^t 求解 u, t
  n = p - 1
  t = int(math.floor(math.log(n, 2)))
  u = 1
  while t > 0:
    u = n / 2**t
    if n % 2**t == 0 and u % 2 == 1:
      break
    t = t - 1
  b1 = b2 = xn_mod_p2(a, u, p)
  for i in range(1, t + 1):
    b2 = b1**2 % p
    if b2 == 1 and b1 != 1 and b1 != (p - 1):
      return False
    b1 = b2
  if b1 != 1:
    return False
  return True
def prime_test_miller_rabin(p, k):
  while k > 0:
    a = randint(1, p - 1)
    if not miller_rabin_witness(a, p):
      return False
    k = k - 1
  return True

以上がPython を使用して素数を検出する方法の例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。