フェルマーテストを実装しているが、カーマイケル数が素数と判定されずこまっている。

実現したいこと

カーマイケル数でも、素数と判定されるようにしたい。

発生している問題・分からないこと

フェルマーテストを実装しているのですが、素数ではないが、フェルマーテストだと素数だと判定されるカーマイケル数を指定すると、素数でないと出力されてしまう。

該当のソースコード

Python
1import math
2import random
3
4
5def is_prime(n):
6    if n == 1: return False
7    if n == 2: return True
8
9    for i in range(100): #100は試行回数
10        a = random.randint(2,n-1)
11
12        if math.gcd(n,a) != 1:
13            return False
14        
15        if pow(a,n-1,n) != 1:
16            return False
17        
18    return True

試したこと・調べたこと

teratailやGoogle等で検索した
ソースコードを自分なりに変更した
知人に聞いた
その他

上記の詳細・結果

同様の質問が見つからない。

補足

特になし

行動規範の内容に同意します

回答3件

ベストアンサー

カーマイケル数を指定した場合、15行目の判定で素数ではないと判定されることはありませんが、12行目の判定で素数ではないと判定される可能性は残ります。
例えば、最初のカーマイケル数である 561 = 3 * 11 * 17 を渡した場合、乱数で3の倍数が出ただけで、素数ではないと判定されます。

投稿2025/08/30 16:16

編集2025/08/30 16:17

actorbug

総合スコア2546

カーマイケル数でも、素数と判定されるようにしたい。

フェルマーテストのみで素数判定をするように書き直せば，カーマイケル数を素数と（誤）判定するようになります。具体的には最初の if 文で return False を continue に変更します。

なお，a は２回同じ値に設定する必要はないので random.randint() の代わりに
random.sample() を用いました。

Python
1import random
2import math
3
4def is_prime_fermat(n):
5    if n == 1: return False
6    if n == 2: return True
7
8    for a in random.sample(range(2, n), min(100, n - 2)):
9
10        if math.gcd(a, n) != 1:
11            continue
12
13        if pow(a, n - 1, n) != 1:
14            return False
15
16    return True
17
18
19carmichael = [561, 1105, 1729, 2465, 2821, 6601, 8911]
20for i in list(range(501, 511)) + carmichael:
21    print(f'{i:4d}: {is_prime_fermat(i)}')
22#  501: False
23#  502: False
24#  503: True
25#  504: False
26#  505: False
27#  506: False
28#  507: False
29#  508: False
30#  509: True
31#  510: False
32#  561: True
33# 1105: True
34# 1729: True
35# 2465: True
36# 2821: True
37# 6601: True
38# 8911: True

投稿2025/08/31 07:29

little_street

総合スコア507

こういう事かい?

Python
1#!/usr/bin/env python3
2
3from random import randint
4
5def expmod(base, exp, m):
6    acc = 1
7    while True:
8        if exp == 0:
9            return acc
10        elif exp % 2 == 0:
11            base, exp = base ** 2 % m, exp / 2
12        else:
13            exp, acc = exp - 1, base * acc % m
14
15def fermat_test(n):
16    def try_it(a):
17        return expmod(a, n, n) == a
18    return try_it(randint(1, n - 1))
19
20def is_prime(n, times = 100):
21    while True:
22        if times == 0:
23            return True
24        elif fermat_test(n):
25            times -= 1
26        else:
27            return False
28
29if __name__ == '__main__':
30    [print(f'{i}: {is_prime(i)}') for i in \
31     # カーマイケル数
32     # https://oeis.org/A002997
33     [561, 1105, 1729, 2465, 2821, 6601, 8911,
34      10585, 15841, 29341, 41041, 46657, 52633,
35      62745, 63973, 75361, 101101, 115921, 126217,
36      162401, 172081, 188461, 252601, 278545, 294409,
37      314821, 334153, 340561, 399001, 410041, 449065,
38      488881, 512461, 530881, 552721]]
39