Compte tenu des entiers arbitraires de $ K $ et M $ M $, peut décider de 2 ^ k $ + M $ M $ est une prime à $ P $?

Question

donné des entiers arbitraires de $ K $ et $ m $ , est 2 $ ^ K $ + $ M $ A Premier?

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'

Je ne suis pas assez compétent dans la théorie des nombres ou tout autre domaine de mathématiques pour connaître la réponse à cette question.

Question

Y a-t-il un algorithme de temps polynomial pour ce problème de décision?

Answer 1

En supposant que vous signiez "polynôme de la taille de la représentation binaire de K et M", alors il est extrêmement improbable, mais prouvant qu'il est impossible sera également très difficile.

Il existe des algorithmes de temps polynomial pour vérifier la primalité, mais ils seraient appliqués à un nombre dont la taille est K, qui est beaucoup plus grande que de vérifier un numéro dont la taille est la même que la taille de k.