$ k $ & $ m $의 임의의 정수를 감안할 때 $ 2 ^ k $ + $ m $를 결정할 수있는 것은 $ P $입니다.

cs.stackexchange https://cs.stackexchange.com/questions/128309

  •  29-09-2020
  •  | 
  •  

문제

$ k $ 및 $ m $ , $ 2 ^ k $ + $ m $ 프라임? 

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'
.

나는이 질문에 대한 답을 알기 위해 숫자 이론이나 다른 수학 분야에서 충분히 잘 알고 있지 않다.

질문

이 결정 문제에 대한 다항식 시간 알고리즘이 있습니까?

도움이 되었습니까?

해결책

K와 M의 바이너리 표현의 크기에서 "다항식"을 의미한다고 가정하면 매우 가능성이 없지만 불가능하다는 것을 증명하는 것은 매우 어려울 것입니다.

원시를 확인하기위한 다항식 시간 알고리즘이 있지만 크기가 k가 동일한 숫자를 확인하는 것보다 훨씬 크고 크기가 k가되는 숫자에 적용됩니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 cs.stackexchange
scroll top