鉴于$ k $和$ m $的任意整数，可以决定$ 2 ^ k $ + $ m $是$ p $的素数吗？

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的二进制表示的大小的多项式”，那么它是极不可能的，但证明是不可能的也是非常困难的。

有多项式时间算法检查原始算法，但它们将应用于大小为k的数字，这比检查大小与k大小相同的数字大得多。