Учитывая произвольные целые числа целых чисел $ 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.