소수성 테스트는 입력된 숫자가 소수인지 여부를 결정하는 알고리즘입니다. 일부 소수 테스트는 결정적입니다. 그들은 숫자가 소수인지 합성인지 항상 정확하게 결정합니다.
가장 빠르게 알려진 결정론적 소수성 테스트는 2004년에 발명되었습니다. Agrawal, Kayal 및 Saxena와 같은 3명의 컴퓨터 과학자가 O~(log(n) 6 에서 작동하는 AKS 소수성 테스트를 발명했습니다. ) 시간, 여기서 O~(f(n))는 O(f(n).log(f(n)) k 로 표시됩니다. ) 일부 정수 k [1]에 대해. 상당한 혁신이기는 하지만 이 속도는 정보 보안 요구 사항에 비해 다소 느립니다.
소수의 장점은 암호화에 활용된다는 것입니다. 표준 암호 시스템 -RSA 알고리즘 중 하나는 더 높은 보안을 제공하기 위해 일반적으로 1024비트 이상인 소수를 키로 필요로 합니다.
이러한 많은 수를 처리할 때 다음 방법은 확실히 좋지 않습니다. 특히 수행된 작업이 소수 테스트 시 / 및 %인 경우 이러한 많은 수로 작업하는 것이 아닙니다.
따라서 생성된 최고의 소수 테스트 알고리즘은 제공된 숫자가 "가능한 소수"인지 또는 합성인지 여부만 결정할 수 있습니다.
다음과 같은 원시성 테스팅의 유형이 있습니다 -
-
결정적 알고리즘 − 결정적 소수 테스트 알고리즘은 정수를 받아들이고 계속해서 소수 또는 합성을 출력합니다. 이 알고리즘은 항상 적절한 답을 제공합니다.
-
나누기 알고리즘 − 가장 간단한 소수 테스트는 다음과 같습니다. −
입력 수 n이 주어지면 2에서 n -1 사이의 정수가 n을 나누는지 확인합니다. n이 m으로 나눌 수 있으면 n은 합성수이고 그렇지 않으면 소수입니다. 그러나 모든 m을 n – 1까지 테스트하는 대신 m을 √n까지 테스트하는 것만 중요합니다. n이 합성인 경우 두 값으로 인수분해될 수 있으며, 그 중 적어도 하나는 √n보다 작거나 같아야 합니다.
-
확률적 알고리즘 − 확률적 알고리즘은 대부분의 경우 정확한 답을 제공하지만 항상 그런 것은 아닙니다. 이 테스트는 n이 모든 소수가 충족해야 하는 하나 이상의 조건을 충족하는지 여부를 결정했습니다. 확률 알고리즘은 소수 또는 합성을 복원하는 다음 규칙에 따라 달라집니다. -
-
테스트할 정수가 실제로 소수이면 알고리즘은 확실히 소수를 반환합니다.
-
테스트할 정수가 실제로 합성이면 확률이 1 − ε인 합성을 반환하지만 확률이 ε인 소수를 반환할 수 있습니다. 알고리즘을 'm'번 실행하고 오류 확률을 Σ m 으로 줄일 수 있다면 실수 확률을 높일 수 있습니다. .
-
페르마 소수성 테스트 − 페르마 소수성 테스트는 n이 소수이면 a
n−1
이라는 페르마의 작은 정리에서 유래합니다. ≡ 1(mod n). 입력 n과 a