鉴于$ k $和$ m $的任意整数,可以决定$ 2 ^ k $ + $ m $是$ p $的素数吗?
-
29-09-2020 - |
题
给定 $ 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'
.
我在数字理论或任何其他数学领域不够了解,以了解这个问题的答案。
问题
是该决策问题的多项式时间算法吗?
解决方案
假设你的意思是“k和m的二进制表示的大小的多项式”,那么它是极不可能的,但证明是不可能的也是非常困难的。
有多项式时间算法检查原始算法,但它们将应用于大小为k的数字,这比检查大小与k大小相同的数字大得多。
不隶属于 cs.stackexchange