베일리–PSW 소수판별법

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

베일리–PSW 소수판별법은 주어진 홀수 정수가 소수인지 여부를 확률적으로 판별하는 알고리즘이다. 이 방법은 시도 나눗셈, 밑이 2인 밀러-라빈 소수 판별법, 야코비 기호를 이용한 루카스 유사소수 검사를 차례로 수행한다. 베일리-PSW 검사는 작은 소인수를 갖는 합성수를 빠르게 걸러내기 위해 시도 나눗셈을 먼저 수행하며, 밀러-라빈과 루카스 검사를 통과하면 확률적 소수로 판정한다. 이 알고리즘은 2⁶⁴ 미만의 수에 대해서는 오류가 없는 것으로 알려져 있으며, 수학 소프트웨어 및 암호화 라이브러리 등에서 소수 판별에 활용된다.

더 읽어볼만한 페이지

소수 판별법 - 에라토스테네스의 체
에라토스테네스의 체는 주어진 범위에서 소수를 효율적으로 찾는 알고리즘으로, 특정 구간 내의 모든 수를 나열한 후 가장 작은 소수의 배수들을 제거하는 과정을 반복하여 소수만을 남기는 방식으로 작동하며, 다양한 변형과 최적화 기법이 존재하고, $O(n \log \log n)$ 의 시간 복잡도를 가진다.
소수 판별법 - 밀러-라빈 소수판별법
밀러-라빈 소수판별법은 페르마 소정리를 기반으로 주어진 수가 소수인지 판별하는 확률적 알고리즘으로, 합성수를 소수로 잘못 판별할 가능성이 있지만 검사를 반복할수록 정확도가 높아지며, 일반화 리만 가설이 참일 경우 결정론적 알고리즘으로 전환될 수 있다.

베일리–PSW 소수판별법
개요
종류	소수 판별법
분류	확률적 알고리즘
고안자	로버트 베일리 칼 포머란스 존 셀프리지 새뮤얼 웨그스태프
세부 사항
기반	페르마 소수판별법 밀러-라빈 소수판별법 뤼카스 소수판별법
결정론적 변종	밀러-라빈
통과 조건	강력한 유사소수 및 뤼카스 유사소수
미해결 문제	베일리-PSW 소수판별법을 통과하는 합성수가 존재하는가?
기타
OEIS 시퀀스	A001262 (기저 2에 대한 유사소수) A217255 (베일리-PSW 소수)

2. 알고리즘

베일리–PSW 소수판별법은 다음 단계를 거쳐 작동한다.^[2]

'''입력''': 소수인지 판별할 홀수인 양의 정수 ''n''

'''출력''': ''n''이 ''확률적 소수'' 또는 ''합성수''

1. ''n''이 어떤 편리한 한계보다 작은 소수로 나누어지는지 확인하기 위해 시도 나눗셈을 수행한다. 만약 나누어 떨어진다면, ''n''은 '''합성수'''이다.

2. 밑이 2인 강력한 확률적 소수 검사(밀러-라빈 소수 판별법)를 수행한다. 만약 ''n''이 밑이 2인 강력한 확률적 소수가 아니라면, ''n''은 '''합성수'''이다.

3. 야코비 기호 (''D''/''n'')가 −1이 되는 수열 5, −7, 9, −11, 13, −15, ...에서 첫 번째 ''D''를 찾는다. ''P'' = 1 및 ''Q'' = (1 − ''D'') / 4로 설정한다.

4. 매개변수 ''D'', ''P'', ''Q''를 사용하여 ''n''에 대한 강력한 루카스 확률적 소수 검사를 수행한다. 만약 ''n''이 강력한 루카스 확률적 소수가 아니라면, ''n''은 '''합성수'''이다. 그렇지 않으면, ''n''은 거의 확실히 소수이다.

참고:

첫 번째 단계는 효율성을 위한 것이다. 베일리-PSW 검사는 이 단계 없이도 작동하지만, ''n''이 작은 소인수를 가지고 있다면, ''n''이 합성수임을 보여주는 가장 빠른 방법은 시도 나눗셈으로 인수를 찾는 것이다.^[2]
2단계는 사실상 밀러-라빈 소수 판별법의 단일 적용이지만, 고정된 밑 2를 사용한다.^[2]
베일리와 왜그스태프는^[2] 1413페이지에 있는 정리 9에서 시도해야 하는 ''D''의 평균 개수가 약 3.147755149라고 증명했다.
만약 ''n''이 완전 제곱수라면, 3단계는 (''D''/''n'') = −1인 ''D''를 절대 생성하지 않는다.
''n''이 주어지면, ''D'', ''P'', ''Q''를 선택하는 다른 방법이 있다.^[8]
^[2]의 6절에서는 ''Q'' ≠ ±1인 경우, 좋은 소수 판별법은 두 개의 추가 합동 조건을 확인해야 한다고 권장한다.
베일리-PSW 검사의 약한 버전이 있으며, 이것은 때때로 ''강력한'' 베일리-PSW 검사라고 불린다.
만약 루카스 검사가 피보나치 검사로 대체된다면, 베일리-PSW 검사라고 불리는 것이 아니라 셀프리지 검사라고 불려야 한다.
포머란스, 셀프리지, 왜그스태프는 베일리-PSW 검사의 약한 버전을 통과하는 합성수에 대해 1980년에 30달러를 제공했다.^[1]

2. 1. 입력 및 출력

2. 2. 단계

(1) 어떤 특정 한계값까지 자연수로 직접 나눠 본다. 만약 하나라도 나누어떨어진다면 '''합성수'''를 출력한다.^[1]

(2) 밑이 2일 때, 즉 a=2일 때 밀러-라빈 소수판별법을 실행한다. 만약 결과가 합성수로 나온다면 '''합성수'''를 출력한다.^[1]

(3) 이 과정에서는 두 가지 방법이 있다.

(A) 수열 5, -7, 9, -11, 13, -17, 19, ...에서

\left ( \frac{D}{N} \right )=-1

인 첫 번째 D를 찾고, P=1, Q=(1-D)/4로 놓는다. 만약 Q=-1이라면 P=5, Q=5로 다시 설정한다.^[1]

(B) 수열 5, 9, 13, 17, 21, ...에서

\left ( \frac{D}{N} \right )=-1

인 첫 번째 D를 찾고, P는

\sqrt{N}

보다 큰 첫 번째 홀수, Q=(P²-D)/4로 놓는다. 만약 Q=1이라면

Q\Leftarrow P+Q+1, P\Leftarrow P+2

로 다시 설정한다.^[1]

(4) 과정 (3)에서 정한 D, P, Q에 대해 강한 뤼카 소수판별법을 적용한다. 만약 이 과정에서 결과가 합성수로 나오면 '''합성수'''를 출력하고, 아니면 '''확률적 소수'''를 출력한다.^[1]

2. 2. 1. 시도 나눗셈

어떤 특정 한계값까지 자연수로 직접 나눠 본다. 만약 하나라도 나누어떨어진다면 '''합성수'''를 출력한다.^[1]

# 첫 번째 단계는 효율성을 위한 것이다. 베일리–PSW 소수판별법 검사는 이 단계 없이도 작동하지만, ''n''이 작은 소인수를 가지고 있다면, ''n''이 합성수임을 보여주는 가장 빠른 방법은 시도 나눗셈으로 인수를 찾는 것이다.^[1]

2. 2. 2. 밀러-라빈 소수판별법

(1) 특정 한계값까지 자연수로 직접 나눠 본다. 만약 하나라도 나누어떨어진다면 '''합성수'''를 출력한다.

(2) 밑이 2일 때, 즉 a=2일 때 밀러-라빈 소수판별법을 실행한다. 만약 결과가 합성수로 나온다면 '''합성수'''를 출력한다.^[1] 이 단계는 사실상 밀러-라빈 소수 판별법의 단일 적용이지만, 고정된 밑 2를 사용한다. 밑 2를 사용하는 데 특별한 점은 없다. 다른 밑에 대한 유사소수는 같은 성장률을 보이는 것으로 보이며, 다른 밑도 잘 작동할 수 있다. 그러나 밑이 2인 강력한 확률적 소수 검사와 강력한 루카스 유사소수 검사의 조합이 소수와 합성수를 잘 구별한다는 것을 확인하기 위해 많은 연구가 이루어졌다.^[1]

참고:

첫 번째 단계는 효율성을 위한 것이다. 베일리–PSW 소수판별법은 이 단계 없이도 작동하지만, ''n''이 작은 소인수를 가지고 있다면, ''n''이 합성수임을 보여주는 가장 빠른 방법은 시도 나눗셈으로 인수를 찾는 것이다.

2. 2. 3. 뤼카 소수판별법

(1) 어떤 특정 한계값까지 자연수로 직접 나눠 본다. 만약 하나라도 나누어떨어진다면 '''합성수'''를 출력한다.

(2) 밑이 2일 때, 즉 a=2일 때 밀러-라빈 소수판별법을 실행한다. 만약 결과가 합성수로 나온다면 '''합성수'''를 출력한다.

(3) 이 과정에서는 두 가지 방법이 있다.

(A) 수열 5, -7, 9, -11, 13, -17, 19, ...에서

\left ( \frac{D}{N} \right )=-1

인 첫 번째 D를 찾고, P=1, Q=(1-D)/4로 놓는다. 만약 Q=-1이라면 P=5, Q=5로 다시 설정한다.

(B) 수열 5, 9, 13, 17, 21, ...에서

\left ( \frac{D}{N} \right )=-1

인 첫 번째 D를 찾고, P는

\sqrt{N}

보다 큰 첫 번째 홀수, Q=(P²-D)/4로 놓는다. 만약 Q=1이라면

Q\Leftarrow P+Q+1, P\Leftarrow P+2

로 다시 설정한다.

(4) 과정 (3)에서 정한 D, P, Q에 대해 강한 뤼카 소수판별법을 적용한다. 만약 이 과정에서 결과가 합성수로 나오면 '''합성수'''를 출력하고, 아니면 '''확률적 소수'''를 출력한다.

3. 특징

3. 1. 정확도

3. 2. 효율성

3. 3. 한계

4. 유사소수

밀러-라빈 소수판별법의 유사소수(pseudopirme)와 뤼카 소수판별법의 유사소수가 거의 없다는 점을 이용한다. 밑이 2일 때 밀러-라빈 소수판별법의 첫 열 번째 유사소수들은 다음과 같다:

2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 그리고 52633 (OEIS의 수열 A001262)

또한 강한 뤼카 소수판별법의 첫 열 번째 유사소수들 (여기서 ''P'', ''Q''는 셀프리지의 방법 A로 선택된 (''P'', ''Q'') 쌍이다)은 다음과 같다:

5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309, 그리고 58519 (OEIS의 수열 A217255)

위 두 수열에서 중복되는 수는 매우 적으며, 특히 위 두 수열에 모두 포함되면서 소수라면 만족해야 할 특정 조건들을 만족하는 합성수는 훨씬 적다는 것이 알려져 있다. 베일리-PSW 소수판별법은 바로 이 점을 이용하여 효과적으로 어떤 수가 소수인지 합성수인지를 판별한다. 베일리-PSW 소수판별법은 2⁶⁴ 미만의 수에 대해서는 검사를 진행했을 때 단 한 번도 틀리지 않았지만, 합성수이지만 확률적 소수라고 출력되는 수는 극히 적긴 하지만 무한히 많이 있을 것으로 추측된다.

서로 다른 밑에 대한 의사 소수의 목록 사이에는 상당한 중복이 있다.^[10]

밑 ''a''를 선택했을때, 만약 ''n''이 밑 ''a''에 대한 의사 소수라면, ''n''은 여러 밑에 대한 의사 소수 중 하나일 가능성이 높다.^[10]

예를 들어, ''n'' = 341은 밑 2에 대한 의사 소수이다.^[2] 1392페이지의 정리 1에 따르면 341이 밑 ''a''에 대한 의사 소수인 100개의 ''a'' 값(mod 341)이 있다.

(그러한 ''a''의 처음 10개는 1, 2, 4, 8, 15, 16, 23, 27, 29, 30입니다.) 이러한 ''a''의 비율은 일반적으로 ''n''에 비해 훨씬 작다.

따라서, 만약 ''n''이 밑 ''a''에 대한 의사 소수라면, ''n''은 평균보다 다른 어떤 밑에 대한 의사 소수일 가능성이 더 높다. 예를 들어, 25·10⁹까지 밑 2에 대한 의사 소수는 21853개이다. 이것은 이 범위에서 백만 개의 홀수 정수 중 약 2개에 불과하다.

그러나:

이 21853개의 숫자 중 4709개(21% 이상)는 밑 3에 대한 의사 소수이기도 하다.
''이'' 4709개의 숫자 중 2522개(53% 이상)는 밑 2, 3, 5에 대한 의사 소수이다.
''이'' 2522개의 숫자 중 1770개(70% 이상)는 밑 2, 3, 5, 7에 대한 의사 소수이다.

숫자 29341은 밑 2부터 12까지의 가장 작은 의사 소수이다.

이 모든 것은 서로 다른 밑에 대한 소수 확률 검정이 서로 독립적이지 않음을 시사하며, 따라서 더 많은 밑에 대한 페르마 소수 확률 검정을 수행하는 것은 효과가 감소할 것이다.

반면에, 페르마와 루카스 소수 확률 검정이 ''독립적''임을 시사하므로, 이러한 유형의 검정을 ''결합''하면 강력한 소수성 검정이 될 것이며, 특히 검사의 ''강력한'' 형태가 사용될 경우 더욱 그렇다.

모든 소수 밑 2, ..., ''p''에 대한 의사 소수인 숫자는 p-smooth인 모든 밑에 대한 의사 소수이기도 하다.

서로 다른 밑에 대한 ''강력한'' 의사 소수 사이에도 중복이 있다. 예를 들어, 1373653은 밑 2부터 4까지의 가장 작은 강력한 의사 소수이고, 3215031751은 밑 2부터 10까지의 가장 작은 강력한 의사 소수이다. Arnault^[11]는 307보다 작은 모든 ''소수'' 밑에 대한 ''강력한'' 의사 소수인 397자리 카마이클 수 ''N''을 제공한다. 이 ''N''이 카마이클 수이기 때문에, ''N''은 또한 ''p''보다 작은 모든 밑에 대한 (반드시 강력하지는 않은) 의사 소수이며, 여기서 ''p''는 ''N''의 131자리 가장 작은 소인수이다. 빠른 계산을 통해 위에서 설명한 방법으로 ''D'', ''P'', ''Q''를 선택하면 ''N''이 루카스 소수 확률 검정을 통과하지 못하므로, 이 숫자는 베일리-PSW 검사에서 합성수로 올바르게 판별될 것이다.

4. 1. 밀러-라빈 유사소수

밑이 2인 밀러-라빈 유사소수는 25 · 10⁹까지 21853개가 존재한다.^[10] 이는 백만 개의 홀수 정수 중 약 2개에 불과한 수치이다.^[10]

서로 다른 밑에 대한 의사 소수 목록 사이에는 상당한 중복이 존재한다.^[10] 예를 들어, 1373653은 밑 2부터 4까지의 가장 작은 강력한 의사 소수이고, 3215031751은 밑 2부터 10까지의 가장 작은 강력한 의사 소수이다. Arnault^[11]는 307보다 작은 모든 소수 밑에 대한 강력한 의사 소수인 397자리 카마이클 수 ''N''을 제시했는데, 이 수는 베일리-PSW 검사에서 합성수로 판별된다.^[11]

4. 2. 뤼카 유사소수

서로 다른 밑에 대한 의사 소수 목록 사이에는 상당한 중복이 있다.^[10] 예를 들어, 341은 밑 2에 대한 의사 소수이다.^[2] 25·10⁹까지 밑 2에 대한 의사 소수는 21853개이며, 이 중 4709개(21% 이상)는 밑 3에 대한 의사 소수이기도 하다.

서로 다른 밑에 대한 ''강력한'' 의사 소수 사이에도 중복이 있다. 예를 들어, 1373653은 밑 2부터 4까지의 가장 작은 강력한 의사 소수이고, 3215031751은 밑 2부터 10까지의 가장 작은 강력한 의사 소수이다. 아놀트(Arnault)^[11]는 307보다 작은 모든 ''소수'' 밑에 대한 ''강력한'' 의사 소수인 397자리 카마이클 수 ''N''을 제시했다.

5. 활용

메이플의 `isprime` 함수,^[12] Mathematica의 `PrimeQ` 함수 (2020년 버전의 베일리–PSW를 이미 사용),^[13] PARI/GP의 `isprime` 및 ispseudoprime` 함수,^[14] 및 SageMath의 `is_pseudoprime` 함수^[15] 모두 페르마 강력 추정 소수 테스트와 루카스 테스트를 결합하여 사용한다. Maxima의 `primep` 함수는 341550071728321보다 큰 숫자에 대해 이러한 테스트를 사용한다.^[16] FLINT 라이브러리에는 결합된 테스트를 사용하는 함수 `n_is_probabprime` 및 `n_is_probabprime_BPSW`와 페르마 및 루카스 테스트를 개별적으로 수행하는 다른 함수가 있다.^[17] 자바 표준 버전과 OpenJDK와 같은 오픈 소스 구현의 `BigInteger` 클래스에는 `isProbablePrime`이라는 메서드가 있다. 이 메서드는 무작위 기수로 하나 이상의 밀러-라빈 테스트를 수행한다. 테스트할 숫자 ''n''이 100비트 이상인 경우, 이 메서드는 또한 ''비강력'' 루카스 테스트를 수행하여 ''U_n+1''이 0 (mod ''n'')인지 확인한다.^[18]^[19] 밀러-라빈 테스트에서 무작위 기수를 사용하는 것은 베일리–PSW 테스트에 지정된 단일 기수 2 테스트를 수행하는 것과 비교하여 장점과 단점이 있다. 장점은 무작위 기수를 사용하면 ''n''이 합성수일 확률에 대한 경계를 얻을 수 있다는 것이다. 단점은 베일리–PSW 테스트와 달리 ''n''이 2⁶⁴와 같은 고정된 경계보다 작으면 ''n''이 소수라고 확신할 수 없다는 것이다. Perl에서 `Math::Primality`^[20] 및 `Math::Prime::Util`^[21]^[22] 모듈에는 강력한 베일리–PSW 테스트를 수행하는 함수와 강력한 유사 소수 및 강력한 루카스 테스트를 위한 별도의 함수가 있다. 파이썬에서 `NZMATH`^[23] 라이브러리에는 강력한 유사 소수 및 루카스 테스트가 있지만 결합된 함수는 없다. SymPy^[24] 라이브러리는 이를 구현한다. 6.2.0 버전부터 GNU 다중 정밀도 산술 라이브러리(GNU Multiple Precision Arithmetic Library)의 `mpz_probab_prime_p` 함수는 강력한 루카스 테스트와 밀러-라빈 테스트를 사용한다. 이전 버전은 베일리–PSW를 사용하지 않았다.^[25] Magma(Magma)의 IsProbablePrime 및 IsProbablyPrime 함수는 34·10¹³보다 큰 숫자에 대해 20개의 밀러-라빈 테스트를 사용하지만 이를 루카스 추정 소수 테스트와 결합하지 않는다.^[26] 암호화 라이브러리에는 종종 소수 테스트 함수가 있다. Albrecht et al.은 이러한 라이브러리에서 사용되는 테스트에 대해 논의한다. 일부는 페르마와 루카스 테스트를 결합하여 사용하고, 많은 수는 그렇지 않다.^[27]

`5. 1. 컴퓨터 대수 시스템`


메이플의 `isprime` 함수,^[12] Mathematica의 `PrimeQ` 함수 (2020년 버전의 베일리–PSW를 이미 사용),^[13] PARI/GP의 `isprime` 및 `ispseudoprime` 함수,^[14] 및 SageMath의 `is_pseudoprime` 함수^[15] 모두 페르마 강력 추정 소수 테스트와 루카스 테스트를 결합하여 사용한다. Maxima의 `primep` 함수는 341550071728321보다 큰 숫자에 대해 이러한 테스트를 사용한다.^[16]

FLINT 라이브러리에는 결합된 테스트를 사용하는 함수 `n_is_probabprime` 및 `n_is_probabprime_BPSW`와 페르마 및 루카스 테스트를 개별적으로 수행하는 다른 함수가 있다.^[17]

자바(Java) 표준 버전과 OpenJDK와 같은 오픈 소스 구현의 `BigInteger` 클래스에는 `isProbablePrime`이라는 메서드가 있다. 이 메서드는 무작위 기수로 하나 이상의 밀러-라빈 테스트를 수행한다. 테스트할 숫자 ''n''이 100비트 이상인 경우, 이 메서드는 또한 ''비강력'' 루카스 테스트를 수행하여 ''U_n+1''이 0 (mod ''n'')인지 확인한다.^[18]^[19]

Perl에서 `Math::Primality`^[20] 및 `Math::Prime::Util`^[21]^[22] 모듈에는 강력한 베일리–PSW 테스트를 수행하는 함수와 강력한 유사 소수 및 강력한 루카스 테스트를 위한 별도의 함수가 있다. 파이썬(Python)에서 `NZMATH`^[23] 라이브러리에는 강력한 유사 소수 및 루카스 테스트가 있지만 결합된 함수는 없다. SymPy^[24] 라이브러리는 이를 구현한다.

6.2.0 버전부터 GNU 다중 정밀도 산술 라이브러리(GNU Multiple Precision Arithmetic Library)의 `mpz_probab_prime_p` 함수는 강력한 루카스 테스트와 밀러-라빈 테스트를 사용한다. 이전 버전은 베일리–PSW를 사용하지 않았다.^[25]

Magma(Magma)의 IsProbablePrime 및 IsProbablyPrime 함수는 34·10¹³보다 큰 숫자에 대해 20개의 밀러-라빈 테스트를 사용하지만 이를 루카스 추정 소수 테스트와 결합하지 않는다.^[26]

암호화 라이브러리에는 종종 소수 테스트 함수가 있다. Albrecht et al.은 이러한 라이브러리에서 사용되는 테스트에 대해 논의한다. 일부는 페르마와 루카스 테스트를 결합하여 사용하고, 많은 수는 그렇지 않다.^[27]

5. 2. 암호학 라이브러리
메이플의 `isprime` 함수^[12], Mathematica의 `PrimeQ` 함수 (2020년 버전부터 베일리–PSW 사용)^[13], PARI/GP의 `isprime` 및 `ispseudoprime` 함수^[14], SageMath의 `is_pseudoprime` 함수^[15]는 모두 페르마 강력 추정 소수 테스트와 루카스 테스트를 결합하여 사용한다. Maxima의 `primep` 함수는 341550071728321보다 큰 숫자에 대해 이러한 테스트를 사용한다.^[16]

FLINT 라이브러리에는 결합된 테스트를 사용하는 함수 `n_is_probabprime` 및 `n_is_probabprime_BPSW`와 페르마 및 루카스 테스트를 개별적으로 수행하는 다른 함수가 있다.^[17]

자바 표준 버전과 OpenJDK와 같은 오픈 소스 구현의 `BigInteger` 클래스에는 `isProbablePrime`이라는 메서드가 있다. 이 메서드는 무작위 기수로 하나 이상의 밀러-라빈 테스트를 수행하며, 100비트 이상인 경우 ''비강력'' 루카스 테스트도 수행한다.^[18]^[19] 밀러-라빈 테스트에서 무작위 기수를 사용하는 것은 베일리–PSW 테스트에 지정된 단일 기수 2 테스트와 비교하여 장단점이 있다.

Perl에서 `Math::Primality`^[20] 및 `Math::Prime::Util`^[21]^[22] 모듈에는 강력한 베일리–PSW 테스트를 수행하는 함수와 강력한 유사 소수 및 강력한 루카스 테스트를 위한 별도의 함수가 있다. 파이썬에서 `NZMATH`^[23] 라이브러리에는 강력한 유사 소수 및 루카스 테스트가 있지만 결합된 함수는 없다. SymPy^[24] 라이브러리는 이를 구현한다.

6.2.0 버전부터 GNU 다중 정밀도 산술 라이브러리의 `mpz_probab_prime_p` 함수는 강력한 루카스 테스트와 밀러-라빈 테스트를 사용한다. 이전 버전은 베일리–PSW를 사용하지 않았다.^[25]

Magma의 `IsProbablePrime` 및 `IsProbablyPrime` 함수는 34·10¹³보다 큰 숫자에 대해 20개의 밀러-라빈 테스트를 사용하지만 이를 루카스 추정 소수 테스트와 결합하지 않는다.^[26]

암호화 라이브러리에는 종종 소수 테스트 함수가 있다. Albrecht et al.은 이러한 라이브러리에서 사용되는 테스트에 대해 논의하며, 일부는 페르마와 루카스 테스트를 결합하여 사용하고, 많은 수는 그렇지 않다고 한다.^[27]



6. 역사

6. 1. 존 셀프리지
6. 2. 포머란스, 셀프리지, 왜그스태프



참조

_[1] 
논문
 
The pseudoprimes to 25·10⁹
 
"//math.dartmouth.ed[...] 
1980-07
 


_[2] 
논문
 
Lucas Pseudoprimes
 
http://mpqs.free.fr/[...] 
1980-10
 


_[3] 
웹사이트
 
The Baillie–PSW Primality Test
 
http://www.trnicely.[...] 
2012-01-13
 


_[4] 
서적
 
Unsolved Problems in Number Theory
 
Springer-Verlag
 
1994
 


_[5] 
웹사이트
 
Are There Counterexamples to the Baillie–PSW Primality Test?
 
http://www.pseudopri[...] 


_[6] 
웹사이트
 
Baillie–PSW
 
https://www.d.umn.ed[...] 
University of Minnesota Duluth
 
null
 


_[7] 
논문
 
Some Comments on Baillie–PSW Pseudoprimes
 
http://www.fq.math.c[...] 
2003-08
 


_[8] 
서적
 
A Course in Computational Number Theory
 
https://archive.org/[...] 
Key College Publishing in cooperation with Springer
 


_[9] 
논문
 
Strengthening the Baillie-PSW Primality Test
 
2021-07
 


_[10] 
논문
 
Pseudoprimes and a generalization of Artin's conjecture
 
1982
 


_[11] 
논문
 
Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases
 
1995-08
 


_[12] 
문서
 
isprime - Maple Help
 
http://www.maplesoft[...] 
maplesoft.com
 


_[13] 
문서
 
Wolfram Language & System Documentation Center - Some Notes on Internal Implementation
 
http://reference.wol[...] 
wolfram.com
 


_[14] 
문서
 
User's Guide to PARI/GP (version 2.11.1)
 
https://pari.math.u-[...] 
PARI/GP
 


_[15] 
문서
 
SageMath Documentation
 
http://doc.sagemath.[...] 
SageMath
 


_[16] 
문서
 
Maxima Manual
 
https://maxima.sourc[...] 
Maxima
 


_[17] 
문서
 
FLINT: Fast Library for Number Theory
 
http://flintlib.org/ 
FLINT
 


_[18] 
문서
 
BigInteger.java
 
http://www.docjar.or[...] 
DocJar
 


_[19] 
문서
 
BigInteger.java
 
http://hg.openjdk.ja[...] 
OpenJDK
 


_[20] 
문서
 
Math::Primality
 
http://metacpan.org/[...] 
Perl module
 


_[21] 
문서
 
Math::Prime::Util
 
http://metacpan.org/[...] 
Perl module
 


_[22] 
문서
 
Math::Prime::Util::GMP
 
http://metacpan.org/[...] 
Perl module
 


_[23] 
웹사이트
 
NZMATH
 
http://tnt.math.se.t[...] 
number theory calculation system in Python
 
2013-01-17
 


_[24] 
웹사이트
 
SymPy
 
https://www.sympy.or[...] 


_[25] 
문서
 
GNU MP 6.2.0 Prime Testing Algorithm
 
https://gmplib.org/m[...] 
GMPLIB
 


_[26] 
문서
 
Magma Computational Algebra System - Primes and Primality Testing
 
http://magma.maths.u[...] 
Magma
 


_[27] 
간행물
 
Prime and Prejudice: Primality Testing Under Adversarial Conditions
 
https://eprint.iacr.[...] 
Association for Computing Machinery
 
2018-10-15
 


 

                
                    
                    
                        

                        본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다. 

                        모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.

                        하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다. 

                        따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

                        

                        문의하기 : help@durumis.com