$ K $と$ m $の任意の整数を与えられます。

Question

$ k $ と $ m $ の任意の整数を指定します。 $ 2 ^ k $ + $ m $ Prime？

K = int(input('enter exponent K: '))
M = int(input('enter integer for M: '))

if AKS.Primality(2**K + M) == True:
    OUTPUT 'yes'
else:
    OUTPUT 'no'

.

私は、この質問に対する答えを知るために数論またはその他の数学の分野で十分に知識を持っていません。

質問

この決定問題のための多項式 - 時間アルゴリズムはありますか？

Answer 1

「KとMの2進表現のサイズの多項式のサイズ」という意味では、それは非常に低いが、不可能であることを証明します。

素源をチェックするための多項式の時間アルゴリズムがありますが、サイズがKのサイズがKのサイズと同じ数字をチェックするよりも大きい数値に適用されます。