Dados enteros arbitrarios de $ K $ y $ M $, pueden decidir $ 2 ^ K $ + $ M $ es un mejor estar en $ P $?

Question

Dados enteros arbitrarios de $ k $ y $ m $ , es $ 2 ^ k $ + $ m $ un 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'

No estoy bien informado en la teoría de números o en cualquier otro campo de matemáticas para conocer la respuesta a esta pregunta.

Pregunta

¿Hay un algoritmo de tiempo polinomial para este problema de decisión?

Answer 1

Suponiendo que te refieres a "polinomio en el tamaño de la representación binaria de K y M", entonces es extremadamente improbable, pero demostrar que es imposible también será muy difícil.

Hay algoritmos de tiempo polinomios para verificar la primalidad, pero se aplicarían a un número cuyo tamaño es k, lo que es mucho más grande que verificar un número cuyo tamaño es el mismo que el tamaño de k.