Arbitrária com inteiros de us $K$ e $M$, pode decidir $2^K$ + $M$ é um excelente ser em $P$?

Question

Arbitrária de números inteiros $K$ e $M$, é $2^K$ + $M$ um 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'

Eu não sou experiente o suficiente em teoria ou em qualquer outro campo da matemática para saber a resposta a esta pergunta.

Pergunta

Existe um algoritmo em tempo polinomial para este problema de decisão?

Answer 1

Supondo que você quer dizer "polinomial no tamanho da representação binária de K e M" e, em seguida, é extremamente improvável, mas provando que é impossível também vai ser muito difícil.

Existem algoritmos de tempo polinomial para verificar a primalidade, mas eles seriam aplicadas a um número, cujo tamanho é de K, que é muito maior do que a verificação de um número cujo tamanho é o mesmo que o tamanho de K.