Dato numeri interi arbitrari di $ k $ e $ m $, può decidere $ 2 ^ k $ + $ m $ è un primo essere in $ p $?

Question

Dato numeri interi arbitrari di $ k $ e $ m $ , è $ 2 ^ k $ + $ m $ un primo?

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'

.

Non sono abbastanza consapevole nella teoria dei numeri o in qualsiasi altro campo di matematica per conoscere la risposta a questa domanda.

domanda

C'è un algoritmo polinomiale per questo problema di decisione?

Answer 1

Supponendo che tu intenda "polinomiale nelle dimensioni della rappresentazione binaria di K e M", quindi è estremamente improbabile, ma dimostrando che è impossibile anche essere molto difficile.

Ci sono algoritmi tempo polinomiali per il controllo della primalità, ma sarebbero stati applicati a un numero la cui dimensione è K, che è molto più grande del controllo di un numero la cui dimensione è la stessa della dimensione di K.