Dato numeri interi arbitrari di $ k $ e $ m $, può decidere $ 2 ^ k $ + $ m $ è un primo essere in $ p $?
-
29-09-2020 - |
Domanda
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?
Soluzione
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.