의사 시간

Pseudoprime

의사소수란 실제로는 소수가 아닌 소수(모든 소수에 공통되는 속성을 공유하는 정수)를 말합니다.의사소수는 만족하는 소수의 속성에 따라 분류됩니다.

일부 소스에서는 합성수와 실제 소수를 모두 포함하여 가능한 모든 소수를 나타내기 위해 의사 소수라는 용어를 사용합니다.

의사 소수는 공개키 암호법에서 가장 중요한 요소이며, 이는 많은 수를 그 주요 요소에 포함시키는 것의 어려움을 이용합니다.Carl Pomerance는 1988년에 144자리 숫자를 인수하는 데 1,000만 달러, 200자리 숫자를 인수하는 데 1,000억 달러가 들 것으로 추산했습니다(현재 비용은 극적으로 낮지만 여전히 터무니없이 높습니다).[1][2]그러나 이 사용에 필요한 두 개의 큰 소수점을 찾는 것도 비용이 많이 들기 때문에 다양한 확률론적 소수점 검정이 사용되며, 그 중 일부는 드물게 소수점 대신 합성 숫자를 부적절하게 전달한다.한편, AKS primality 테스트등의 결정론적 primality 테스트에서는, false positive는 표시되지 않습니다.이러한 테스트에는 의사 소수점이 없습니다.

페르마 의사 소수

주요 기사:페르마 유사 프리미

페르마의 작은 정리는 만약 p가 소수이고 a가 p에 대한 공역수라면, ap−1 - 1은 p로 나누어진다는 것이다.정수 a > 1의 경우, 합성 정수 x가 a - 1을 나누면x−1 x는 밑수 a에 대한 페르마 유사프라이임이라고 불립니다.따라서 x가 기저 a에 대한 페르마의 의사 시간일 경우 x는 a에 대한 공동 시간인 것입니다.일부 송신원에서는, 홀수만을 의사 [3]소수로서 하는 등, 이 정의의 변형을 사용하고 있습니다.

의 모든 값에 대한 페르마 유사 시간인 정수 x를 카마이클 수라고 합니다.

반

레퍼런스

  1. ^ Clawson, Calvin C. (1996). Mathematical Mysteries: The Beauty and Magic of Numbers. Cambridge: Perseus. p. 195. ISBN 0-7382-0259-2.
  2. ^ Cipra, Barry Arthur (December 23, 1988). "PCs Factor a 'Most Wanted' Number". Science. 242: 1634–1635. doi:10.1126/science.242.4886.1634. PMID 17730568.
  3. ^ Weisstein, Eric W. "Fermat Pseudoprime". MathWorld.