밀러-라빈 원시성 검정

밀러-라빈 소수성 시험 또는 라빈-밀러 소수성 시험은 확률론적 소수성 시험으로, 페르마 소수성 시험 및 솔로베이-스트라센 소수성 시험과 유사하게 소수들이 소수일 가능성이 있는지 여부를 결정하는 알고리즘이다.

다항식 시간 결정론적 원시성 검정을 찾는 데 있어 역사적 의의가 있다.그것의 확률론적 변형은 알려진 가장 간단하고 가장 빠른 시험들 중 하나로서 실제로 널리 사용되고 있다.

게리 L. 밀러는 1976년에 이 테스트를 발견했다; 밀러의 테스트 버전은 결정론적이지만, 그것의 정확성은 증명되지 않은 확장된 리만 가설에 의존한다.^[1]Michael O. Rabin은 1980년에 무조건적인 확률론 알고리즘을 얻기 위해 그것을 수정했다.^[2]^[a]

수학적 개념

Fermat 및 Solovay-Strassen 테스트와 유사하게, Miller-Rabin 원시성 테스트는 프라임 값을 유지하는 것으로 알려진 특정 속성이 테스트 대상 수를 유지하는지 여부를 검사한다.

강한 확률적 소수

재산은 다음과 같다.주어진 홀수 n > 2의 경우, s와 d가 양의 정수이고 d가 홀수인 경우 n을 2^s⋅d + 1로 쓰자.0 < a < n>과 같은 염기라고 하는 정수 a를 생각해 보자.그 후, n은 다음과 같은 합치 관계 중 하나가 유지될 경우 기초할 수 있는 강력한 가능성이 있는 프라임이라고 한다.

$a^{d}\equiv 1{\pmod {n}}$ $a^{d}\equiv 1{\pmod {n}}$ $a^{d}\equiv 1{\pmod {n}}$ $a^{d}\equiv 1{\pmod {n}}$ ( $a^{d}\equiv 1{\pmod {n}}$ $a^{d}\equiv 1{\pmod {n}}$ ) ${\$ 1 ${\pmod{n$
$a^{2^{r}\cdot d}\equiv -1{\pmod {n}}$ 2 $a^{2^{r}\cdot d}\equiv -1{\pmod {n}}$ ⋅ d $a^{2^{r}\cdot d}\equiv -1{\pmod {n}}$ - 1 ( $a^{2^{r}\cdot d}\equiv -1{\pmod {n}}$ n $a^{2^{r}\cdot d}\equiv -1{\pmod {n}}$ ) ${\$ a $^{2^{r}\cdot$ d $}\equiv -1{\pmod{n}}}}}$ 의 경우 $a^{2^{r}\cdot d}\equiv -1{\pmod {n}}$ , 약 0 < r <s.

이 시험의 밑바탕은 n이 홀수 프라임일 때 다음과 같은 두 가지 사실 때문에 시험에 합격한다는 것이다.

페르마의 작은 정리(mod $a^{n-1}\equiv 1{\pmod {n}}$ )에 의해, $a^{n-1}\equiv 1{\pmod {n}}$ - $a^{n-1}\equiv 1{\pmod {n}}$ $a^{n-1}\equiv 1{\pmod {n}}$ 1 $a^{n-1}\equiv 1{\pmod {n}}$ ( $a^{n-1}\equiv 1{\pmod {n}}$ n $a^{n-1}\equiv 1{\pmod {n}}$ ) ${\$ a $^{n-1}\equiv$ 1 ${\pmod{n}}}}($ 이 속성만 해도 페르마 테스트의 기반이 되는 a 기초가 될 가능성이 있는 prime의 약한 개념을 정의한다).
1모듈로 n의 유일한 제곱근은 1과 -1이다.

따라서 대조적으로 n이 a를 근거할 수 있는 강력한 개연성이 없는 경우, n은 확실히 복합성이며, a는 n의 복합성에 대한 증인(때로는 오해의 소지가 있는 강한 증인)이라고 불린다.

그러나, 이 속성은 소수들의 정확한 특성화는 아니다.n이 복합적인 경우, 그럼에도 불구하고 a를 베이스로 할 수 있는 강력한 가능성이 있는 프라임일 수 있으며, 이 경우 강력한 가성비라고 불리며, a는 강한 거짓말쟁이다.

베이스 선택

다행히도, 어떤 복합적인 숫자도 모든 베이스에 동시에 강력한 유사점이다.그러나 목격자를 찾는 간단한 방법은 알려지지 않았다.순진한 해결책은 비효율적인 결정론적 알고리즘을 산출하는 가능한 모든 기초를 시도하는 것이다.밀러 테스트는 보다 효율적인 변형이다(아래 섹션 밀러 테스트 참조).

또 다른 해결책은 무작위로 베이스를 선택하는 것이다.이것은 빠른 확률론적 테스트를 산출한다.n이 복합적인 경우, 대부분의 베이스는 증인이므로 테스트는 n을 상당히 높은 확률의 복합체로 감지한다(아래 섹션 정확도 참조).해당 비율을 달성하는 데 필요한 만큼의 독립적으로 선택한 근거의 결과를 결합함으로써 거짓 양성 확률을 임의의 작은 비율로 빠르게 줄일 수 있다.이것은 밀러-라빈 시험이다.시도할 베이스 수는 n에 의존하지 않는다.n이 어떤 베이스에 가성비라면 다른 베이스에 가성비가 될 가능성이 더 높아 보이기 때문에 많은 베이스를 시도하면 수익이 감소하는 것 같다.^[4]^{: §8}

임의로 큰 n을 시험하기 위해서는 1, 2, …, n-1의 숫자 중에서 목격자와 강한 거짓말의 분포를 모르기 때문에 무작위로 베이스를 선택하는 것이 필수적이다.^[b]

그러나, 몇 개의 작은 베이스로 사전 선택된 세트는 사전 계산된 최대치까지 모든 합성물의 식별을 보장한다.이 최대치는 일반적으로 베이스에 비해 상당히 크다.이는 충분히 작은 n에 대해 매우 빠른 결정론적 테스트를 제공한다(아래 작은 베이스 집합에 대한 섹션 테스트 참조).

교정쇄

여기에 n이 홀수 소수일 때 1모듈로n의 유일한 제곱근은 1과 -1이라는 증거가 있다.

증명

확실히 1과 -1은 모듈로 n을 제곱할 때 항상 1을 산출한다.1모듈로n의 다른 제곱근은 없다는 것을 보여줘야 한다.이것은 여기서 유한장 Z/nZ에 대한 다항식² X - 1을 적용한 특별한 경우로서, 어떤 분야에 대한 다항식은 그 정도 이상의 뿌리를 가지고 있지 않다는 보다 일반적인 사실(이 정리는 다항식을 위한 유클리드 분할의 존재에서 따온 것이다.여기 좀 더 기본적인 증거가 있다.x가 1모듈로 n의 제곱근이라고 가정하자.다음:

(x-1)(x+1)=x^{2}-1\equiv 0{\pmod {n}.

즉, n은 제품(x - 1)(x + 1)을 나눈다.유클리드 보조정리기는 n이 prime이기 때문에 x - 1 또는 x + 1 요인 중 하나를 나누는데, 이는 x가 1 또는 -1 modulo n 중 하나로 합치됨을 의미한다.

여기에 n이 기묘한 프라임이라면, a를 베이스로 할 수 있는 강력한 개연성 프라임이라는 증거가 있다.

증명

페르마의 작은 정리로는 다음과 같다.

a^{2^{s}\cdot d}\equiv 1{\pmod{n}}

$a^{2^{s}\cdot d},a^{2^{s-1}\cdot d},\dots ,a^{2d},a^{d}$ $a^{2^{s}\cdot d},a^{2^{s-1}\cdot d},\dots ,a^{2d},a^{d}$ $a^{2^{s}\cdot d},a^{2^{s-1}\cdot d},\dots ,a^{2d},a^{d}$ , $a^{2^{s}\cdot d},a^{2^{s-1}\cdot d},\dots ,a^{2d},a^{d}$ - $a^{2^{s}\cdot d},a^{2^{s-1}\cdot d},\dots ,a^{2d},a^{d}$ $a^{2^{s}\cdot d},a^{2^{s-1}\cdot d},\dots ,a^{2d},a^{d}$ d $a^{2^{s}\cdot d},a^{2^{s-1}\cdot d},\dots ,a^{2d},a^{d}$ , $a^{2^{s}\cdot d},a^{2^{s-1}\cdot d},\dots ,a^{2d},a^{d}$ … $a^{2^{s}\cdot d},a^{2^{s-1}\cdot d},\dots ,a^{2d},a^{d}$ , d ${\$ a $^{2^{s}\cdot d},a^{s-1}\cdot$ d $},\dots ,a^{2d},a^{$ d},a^{ $d}$ 의 각 항은 전항의 제곱근이다 $a^{2^{s}\cdot d},a^{2^{s-1}\cdot d},\dots ,a^{2d},a^{d}$ 제1항은 제1항과 일치하므로 제2항은 제1항의 제곱근모듈로 n이다.이전의 보조정리법에 의해, 그것은 1 또는 -1과 일치한다.만약 그것이 -1과 일치한다면, 우리는 끝장이다.그렇지 않으면, 그것은 1과 일치하고 우리는 그 추론을 반복할 수 있다.마지막에 두 용어 중 하나가 -1에 합치되거나 모두 1에 합치되며, 특히 마지막 용어인 a는^d 다음과 같다.

예

n = 221이 prime인지 확인하려고 한다고 가정합시다.n-1을 2²·55로 표기하여 s = 2와 d = 55가 되도록 한다.1 << n - 1, a = 174라고 하는 숫자 a를 임의로 선택한다.다음 사항을 계산해 보십시오.

a^2⁰·d mod n = 174⁵⁵ mod 221 = 47 ≠ 1, n − 1
a^2¹·d mod n = 174¹¹⁰ mod 221 = 220 = n - 1

220˚ -1모드 n이므로 221이 프라임이거나 174가 221의 강력한 거짓말쟁이다.이번에는 a = 137:를 선택해서 다른 임의의 a를 시도한다.

a^2⁰·d mod n = 137⁵⁵ mod 221 = 188 ≠ 1, n − 1
a^2¹·d mod n = 137¹¹⁰ mod 221 = 205 ≠ n - 1

따라서 137은 221의 구성성의 증인이며, 174는 사실 강한 거짓말쟁이였다.이것은 221 (13과 17)의 요인에 대해 우리에게 아무것도 말해주지 않는다는 점에 유의하라.그러나 이후 절에서 341을 사용한 예는 이러한 계산이 n의 인자를 어떻게 산출할 수 있는지를 보여준다.

밀러-라빈 검정

알고리즘은 다음과 같이 필적할 수 있다.매개변수 k는 시험의 정확도를 결정한다.라운드 수가 많을수록 결과의 정확도가 높아진다.

입력 #1: n > 3, 원시성에 대해 테스트할 홀수 정수 #2: k, 출력을 수행할 테스트 라운드 수:n이 복합적인 것으로 판명된 경우, "합성" 또는 "primable prime"은 d와 함께 n을 2^r/d + 1로 표기한다(n - 1에서 2의 힘을 고려함). 증인루프: 반복 k 횟수: [2, n - 2] x ← mod^d n(x = 1 또는 x = n - 1인 경우) 범위에서 무작위 정수 a를 선택한 다음 Witness를 계속하십시오.반복 r - 1회 반복: x ← x² mod n(x = n - 1인 경우) 이후 Witness를 계속루프 리턴 "복합" 리턴 "아마도 프라임"

복잡성

반복 스쿼링을 사용하면 이 알고리즘의 실행 시간은 $O (k$ $logn 3)$ 이며 여기서 n은 원시성에 대해 테스트된 숫자, k는 수행된 라운드의 수입니다. 따라서 효율적인 다항 시간 알고리즘이다.FFT 기반 곱셈(Harvey-Hoeven 알고리즘)은 실행 시간을 $O(k$ $log$ $n$ $log$ $n)$ = $õ (k$ $log$ $n$ )로 푸시할 수 있다 $.$

정확도

프라이머리티 테스트에 의해 발생하는 오차는 복합 숫자가 프라이머로 선언될 확률로 측정된다.a의 베이스를 많이 시도할수록 시험의 정확도가 높아진다.n이 복합적인 경우 기껏해야 그 다음임을 알 수 있다.베이스의 1⁄4 a는 n에 대한 강한 거짓말이다.^[2]^[6]결과적으로, n이 복합적인 경우 밀러-라빈 시험의 k 반복 실행은 최대^−k 4의 확률로 n prime을 선언할 것이다.

이는 최악의 오류 한계가 2인^−k Solovay-Strassen 테스트에 비해 개선된 것이다.더욱이 밀러-라빈 테스트는 모든 합성 n에 대해 n에 대한 강한 거짓말의 집합이 n에 대한 오일러 거짓말의 집합의 부분 집합이라는 점에서 솔로웨이-스트라센 테스트보다 엄격히 강하며, 많은 n에 대해서는 부분 집합이 적절하다는 점에서 더욱 강력하다.

또한, n의 큰 값의 경우, 합성수가 prime으로 선언될 확률은 종종 4보다^−k 유의하게 작다.예를 들어, 대부분의 숫자 n에 대해, 이 확률은 8로^−k 제한된다; 우리가 n의 더 큰 값을 고려할 때 이 상한 n을 무효로 하는 숫자 n의 비율은 사라진다.^[7]따라서 평균적인 경우는 4보다^−k 훨씬 더 높은 정확도를 가지고 있는데, 이는 발생 가능한 소수점 생성에 악용될 수 있다(아래 참조).그러나, 암호 적수는 원시성 시험을 물리치기 위해 신중하게 선택한 가성비를 보낼 수 있기 때문에, 그러한 개선된 오류 한계는 확률 분포를 제어하지 않는 가성비를 검증하는 데 의존해서는 안 된다.^[c]그러한 맥락에서, 4의^−k 최악의 오류 한계만을 신뢰할 수 있다.

위의 오차 측정은 k라운드 시험 후 합성수가 강력한 개연성으로 선언될 확률이다. 수학적 용어로, 조건부 확률 $\Pr(M\!R_{k}\mid \lnot P)$ ( $\Pr(M\!R_{k}\mid \lnot P)$ $\Pr(M\!R_{k}\mid \lnot P)$ k $\Pr(M\!R_{k}\mid \lnot P)$ P $){\displaystyle \Pr(M\!)$ 이다. $R_{k}\mid \lnot P)}$ 여기서 $\Pr(M\!R_{k}\mid \lnot P)$ P는 시험 중인 숫자가 prime인 사건이고 MR은_k k라운드로 Miller-Rabin 시험을 통과한 사건이다.우리는 종종 역 조건부 확률 $\Pr(\lnot P\mid M\!R_{k})$ ( $\Pr(\lnot P\mid M\!R_{k})$ $\Pr(\lnot P\mid M\!R_{k})$ $\Pr(\lnot P\mid M\!R_{k})$ $\Pr(\lnot P\mid M\!R_{k})$ R $){\displaystyle \Pr(\lnot P\mid M\!)$ 에 관심을 가진다. $R_{k}}$ : 강한 개연성 prime으로 선언된 숫자가 사실 복합적일 확률이다.이 두 가지 확률은 베이즈의 법칙에 의해 관련된다.

\displaystyle \Pr(\lnot P\mid M\!R_{k}={\frac {\Pr(\lnot P\land M\!R_{k}}{\Pr(\lnot P\land M\!R_{k}+\Pr(P\land M\!R_{k}}}={\frac {1}{1+{\frac {\Pr(M\!R_{k}\중간 P)}{\Pr(M\!R_{k}\mid \lnot P)}}}\cdot {\frac {\Pr(P)}{\Pr(P)}}}}}}}}}}}}}{\frac {1}{1+{\frac {1}{\!R_{k}\mid \lnot P)}}\cdot {\frac {\Pr(P)}{1-\Pr(P)}}}}}}

마지막 방정식에서는 모든 소수값이 강력한 발생 가능한 소수(검정에는 잘못된 음수가 없음)로 올바르게 보고된다는 사실을 사용하여 식을 단순화했다.분모의 왼쪽 부분을 떨어뜨림으로써 우리는 다음과 같은 간단한 상한선을 도출한다.

\displaystyle \Pr(\lnot P\mid M\!R_{k}<\Pr(M\!)!R_{k}\mid \lnot P)\cdot \왼쪽({\tfrac {1}{\Pr(P)}-1\오른쪽)}

따라서 이 조건부 확률은 위에서 설명한 오차 측정치(4로^−k 제한됨)뿐만 아니라 입력 번호의 확률 분포와도 관련이 있다.일반적인 경우, 앞에서 말한 바와 같이, 이 분포는 암호 적수에 의해 제어되므로, $\Pr(\lnot P\mid M\!R_{k})$ ( $\Pr(\lnot P\mid M\!R_{k})$ $\Pr(\lnot P\mid M\!R_{k})$ $\Pr(\lnot P\mid M\!R_{k})$ $\Pr(\lnot P\mid M\!R_{k})$ $\Pr(\lnot P\mid M\!R_{k})$ $){\displaystyle \Pr (\lnot P\mid M\!)$ 에 대해서는 별로 추론할 수 없다! $R_{k$ 다만, 우리가 밀러-라빈 테스트를 사용하여 프라임을 생성하는 경우(아래 참조)에는 발전기 자체에 의해 분배가 선택되므로 이 결과를 이용할 수 있다.

결정론적 변이형

밀러 시험

밀러-라빈 알고리즘은 특정 한계 이하로 가능한 모든 것을 시도함으로써 결정론적으로 만들 수 있다.n을 한계치로 간주하면 $O(n)$ 시행을 의미하므로 실행 시간은 입력의 크기 $로그$ $n$ 과 관련하여 지수적일 것이다.그런 다음 주행 시간을 개선하기 위해 시험의 신뢰성을 유지하면서 한계를 최대한 낮추는 것이 과제다.

시험 숫자 n이 복합적인 경우, n에 대한 강한 거짓말은 그룹의 적절한 하위 그룹(Z/nZ)*에 포함되며, 이는 우리가 (Z/nZ)*를 생성하는 집합에서 모든 a를 테스트할 경우, 그들 중 하나는 해당 하위 그룹 외부에 있어야 한다는 것을 의미하며, 따라서 n의 복합성에 대한 증인이 되어야 한다는 것을 의미한다.일반화된 리만 가설(GRH)의 진리를 가정하면 밀러가 이미 지적한 $O(ln$ $n) 2$ 보다 작은 원소에 의해 집단이 생성되는 것으로 알려져 있다.^[1]빅 O 표기법에 관련된 상수는 에릭 바흐에 의해 2로 축소되었다.^[9]이는 밀러 시험이라고 알려진 다음과 같은 결정론적 원시성 시험 알고리즘으로 이어진다.

입력: n > 1, 원시성에 대해 테스트할 홀수 정수:n이 복합적인 경우, "primate"가 n을 2^r/d + 1로 쓰고 d 홀수(n - 1)를 2/d + 1로 쓴다(n - 1) 증인루프: [2, min(n-2, ⌊2(ln)⌋)]² 범위의 모든 a에 대해: x ← mod^d n(x = 1 또는 x = n - 1인 경우)를 선택한 다음 Witness를 계속하십시오.반복 r - 1회 반복: x ← x² mod n(x = n - 1인 경우) 이후 Witness를 계속루프 리턴 "복합" 리턴 "프라임"

일반화된 리만 가설의 완전한 힘은 검정의 정확성을 보장하기 위해 필요하지 않다: 짝수 지수의 부분군을 다루기 때문에 2차 디리클레 문자에 대한 GRH의 유효성을 가정하기에 충분하다.^[6]

알고리즘의 실행 시간은 소프트-O 표기법에서 $õ(log$ $n) 4$ (FFFT albased 곱셈 사용)이다.

밀러 시험은 실제로 사용되지 않는다.대부분의 경우 확률론적 Miller-Rabin 테스트 또는 Baillie-Rabin 테스트의 적절한 사용.PSW 원시성 테스트는 훨씬 더 빨리 달리면서도 충분한 자신감을 준다.또한 검증되지 않은 가정에 의존하지 않는 결과를 제공하는 APR-CL이나 ECPP와 같이 일반적으로 사용되는 입증 방법보다 실행 속도가 느리다.결정론적 다항식 시간 알고리즘이 필요한 이론적 목적을 위해 AKS 원시성 테스트로 대체되었으며, 이는 또한 검증되지 않은 가정에 의존하지 않는다.

작은 베이스 집합에 대한 테스트

시험할 n의 숫자가 작을 때는 < $2(ln$ $n) 2$ 를 모두 시도할 필요는 없다. 훨씬 더 작은 수의 잠재적 증인이 충분하다고 알려져 있기 때문이다.예를 들어 포머런스, 셀프리지, 와그스태프^[4], 재슈케^[10] 등이 검증한 바 있다.

n < 2,047인 경우, a = 2를 시험하기에 충분하다.
n < 1,373,653인 경우 a = 2와 3을 시험하기에 충분하다.
n < 9,080,191인 경우, a = 31과 73을 시험하기에 충분하다.
n < 25,326,001인 경우, a = 2, 3, 5를 시험하기에 충분하다.
n < 3,215,031,751인 경우, a = 2, 3, 5, 7을 시험하기에 충분하다.
n < 4,759,123,123,103이면 a = 2, 7, 61을 시험하기에 충분하다.
n < 1,162,004,669,633인 경우 a = 2, 13, 23 및 1662803을 시험하기에 충분하다.
n < 2,196,302,898,747인 경우 a = 2, 3, 5, 7, 11을 시험하기에 충분하다.
n < 3,474,749,1987,383인 경우 a = 2, 3, 5, 7, 11 및 13을 시험하기에 충분하다.
n < 341,550,071,728,197이면 a = 2,3,5,7,11,13,17을 시험하기에 충분하다.

2010년 Feitsma와 Galway가 모든 기준 2개의 가성비를 열거한 작업을 사용하여 이를 확장했다(OEIS: A014233 참조). 이후 장과 덩에서 다른 방법을 사용한 첫 번째 결과가 나타났다.^[11]

n < 3,825,123,056,546,413,051이면 a = 2, 3, 5, 7, 11, 13, 17, 19, 23을 시험하기에 충분하다.
n < 18,446,744,074,073,709,551,616 = 2이면⁶⁴ a = 2,3,5,7,11,13,17,19,23,29,31,37을 시험하기에 충분하다.

Sorenson과 Webster는^[12] 위의 내용을 확인하고 64비트 이상의 결과에 대해 정확한 결과를 계산한다.

n < 318,665,857,834,031,19,7,11,13,17,19,23,29,31,37을 시험하기에 충분하다.
n < 3,317,044,064,679,887,385,961,981이라면 a = 2,3,5,5,7,11,13,17,19,23,29,31,37,41을 시험해도 충분하다.

이러한 종류의 다른 기준, 종종 위에 표시된 기준보다 더 효율적(필요한 베이스)이 존재한다.^[13]^[14]^[15]^[16]그들은 가정 없이 적절한 범위의 숫자에 대해 매우 빠른 결정론적 원시성 시험을 제공한다.

가능한 모든 입력 크기(b – 비트 숫자에 대한 최대 b 값)에 대한 잠재적 증인의 목록이 있다.그러나 모든 합성수에는 유한한 염기 집합이 충분하지 않다.Alford, Granville, Pomerance는 최소 복합성 $증인$ 이 ( $ln$ n)인 합성수 n이 무한히 많이 존재한다는 것을 보여주었다 $. 1/(3ln ln ln n)$ ^[17]그들은 또한 경험적으로 n 아래의 모든 합성수가 w보다 작은 복합성 증인을 가질 수 있는 최소 숫자는 순서 $order (log$ n $log log$ $n$ )이어야 한다고 주장한다 $.$

요인을 찾기 위한 변형

위의 알고리즘에 가장 큰 공통점 계산을 삽입함으로써 n이 복합적이라는 단순한 판단 대신 n의 인자를 얻을 수 있는 경우가 있다.예를 들어, n이 개연성 있는 prime base a이지만 개연성이 강한 prime base a가 아닌 경우에 발생한다.^[18]^{: 1402}알고리즘에서 이 경우는 내부 루프에 있는 x를 -1뿐만 아니라 1과 비교함으로써 검출할 수 있다.

내부 루프의 일부 반복 1 ≤ i < r에서 알고리즘이 변수 x의^d·2ⁱ $mod$ n $값$ 이 1과 같다는 것을 발견하면, 이전 값 $x 0$ = 변수 x의 $a$ 가^{d·2^s−1} ±1과 다른 것으로 확인되었다는 것을 알고, x가₀ 1과 -1이 아닌 1의 제곱근이라고 추론할 수 있다.n이 prime일 때는 이것이 가능하지 않기 때문에 n이 복합적이라는 것을 의미한다.더욱이 다음과 같다.

$x 02$ ≡ $1 (mod$ $n)$ 이후, n은 $x 02$ - $1 =$ ( $x 0$ - $1)(x 0$ + 1)을 나눈다는 것을 알고 있다 $.$
$x 0 ≢ \pm1 (mod$ $n)$ 이후, $n$ 은₀x - $1$ $또는 0$ x + $1$ 을 나누지 않는다는 것을 알고 있다.

여기서 우리는 $A$ = $GCD(x 0$ - 1, $n)$ 와 $B$ = $GCD(x 0$ + 1, $n)$ 는 n의 비경쟁적(필수적으로 원시적인 것은 아님) 요인(사실 n은 홀수이기 때문에 이러한 요인은 coprime과 n = A·B)이라고 추론한다.따라서, 만약 인수 작업이 목표라면, 이러한 GCD 계산은 약간의 추가 계산 비용으로도 알고리즘에 삽입될 수 있다.이로 인해 추가된 코드 또는 변경된 코드가 강조 표시되는 다음과 같은 유사 코드가 발생한다.

입력#1:n>3, 이상한 정수 primality 입력#2에 시험할:k, 시험을 출력을 수행할 매수:("여러 of", m)만약non‐trivial 인자 m는 얼마인가?발견되“복합”경우는 얼마인가? 그렇지 않으면 발생한 복합,“아마도 총리” 그렇지 않으면 쓰n로 2r·d+1에 d이상한(에 의해 채권 매수를 강대국들의 2에서 n.− 1)증인루프: 반복 k 횟수: [2, n - 2] x ← mod^d n(x = 1 또는 x = n - 1인 경우) 범위에서 무작위 정수 a를 선택한 다음 Witness를 계속하십시오.반복 r - 1회 반복: y = 1이면 y ← x mod² n, 그 다음 반환("복수"), GCD(x - 1, n) x ← y x x = n - 1이면 Witness를 계속한다.루프 리턴 "복합" 리턴 "아마도 프라임"

이것은 확률론적 요인화 알고리즘이 아니다. 왜냐하면 그것은 단지 a의 기초가 되는 가성비인 n에 대한 요인(즉, 1 $mod$ $n$ 과 $같은 n -1$ 숫자 n의 경우)을 찾을 수 있기 때문이다.다른 숫자의 경우 알고리즘은 추가 정보가 없는 "복합체"만 반환한다.

예를 들어 n = 341 및 a = 2를 고려하십시오. $n$ - 1 = $85, 4$ 가 있다 $.$ $그런 85$ 다음 $2모드 341$ = $32.$ 및 $32모드 2341$ = $1.$ 이것은 n이 가성기 2이지만 강한 가성기 2는 아니라는 것을 말해준다.이 단계에서 GCD를 계산함으로써 우리는 341: $GCD(32 -$ 1, $341)$ = $31$ 의 인자를 찾는다 $.$ 실로 $341$ = $11\cdot31$ .

요인을 더 자주 찾기 위해 -1(또는 다른 수)의 제곱근에도 동일한 사상을 적용할 수 있다.이 전략은 이전 Miller-Rabin 테스트의 지식을 활용하여 구현할 수 있다.그 라운드에서 우리는 -1의 제곱근 모듈로 n을 확인했을지도 모른다.그런 다음 $x 2$ $mod$ n = $n-1일$ 때 x의 값을 R과 비교할 수 있다: x가 R도 n도 아닌 경우 $GCD(x$ - $R,$ $n)$ 와 $GCD(x$ + $R,$ $n)$ 는 n의 비종속적인 요인이다.^[13]

발생 가능한 소수점 생성

밀러-라빈 테스트는 테스트에 합격할 때까지 무작위로 정수를 그리기만 하면 강력한 발생 가능한 프리마임을 생성하는 데 사용할 수 있다.이 알고리즘은 거의 확실히 종료된다(각 반복에서 소수점을 그릴 기회가 있기 때문이다).가장 중요한 비트 설정에서 b along probable primes를 생성하기 위한 유사 코드는 다음과 같다.

입력 #1: b, 결과의 비트 수 입력 #2: k, 출력할 테스트 라운드 수: 강력한 예상 소수 n, 반면 True: 입력 n과 k를 사용한 Miller-Rabin 테스트가 "prime"을 반환하면 [2^b−1, 2-1^b] 범위에서 무작위 홀수 정수 n을 선택한 다음 n을 반환한다.

복잡성

물론 외부 루프가 절대 종료되지 않을 수 있기 때문에 최악의 경우 실행 시간은 무한하지만, 확률 0과 함께 발생한다.기하 분포에 따라 예상되는 추첨 횟수는 ${\tfrac {1}{\Pr(M\!R_{k})}}$ ${\tfrac {1}{\Pr(M\!R_{k})}}$ ${\tfrac {1}{\Pr(M\!R_{k})}}$ ${\tfrac {1}{\Pr(M\!R_{k})}}$ ) ${\$ 이다. $R_{k}}}}}($ 이전의 표기 사용).

소수점 만이 검정을 통과할 때 소수점일 확률은 검정을 통과할 확률에 큰 하한을 부여한다.[2^b−1, 2-1^b] 범위에서 홀수 정수를 균일하게 그리면 다음과 같은 결과를 얻을 수 있다.

\디스플레이 스타일 \Pr(M\!)R_{k}}]\Pr(P)={\frac {\pi \좌측(2^{b}\우측)-\pi \좌측(2^{b-1}\우측)}{2^{b-2}}

여기서 π은 원시 기능이다.π의 점증적 팽창(원수 정리의 확장)을 이용하여 b가 무한을 향해 성장할 때 이 확률을 대략적으로 추정할 수 있다.다음 사항을 확인하십시오.

\Pr(P)={\tfrac {2}{\ln2}}b^{-1}+{\mathcal {O}\왼쪽(b^{-3}\오른쪽)

{\tfrac {1}{\Pr(P)}}={\tfrac {\ln2}{2}}b+{\mathcal{O}\왼쪽(b^{-1}\오른쪽)}

따라서 우리는 발전기가 b에 비례하는 숫자보다 더 이상 밀러-라빈 테스트를 실행하지 않을 것으로 예상할 수 있다.각 Miller-Rabin 시험의 최악의 복잡성을 고려하여(이전 참조), 입력 b와 k를 가진 발전기의 예상 가동 시간은 FFT 기반 곱셈을 사용한 $O(k$ $b 4)$ 또는 $õ(k$ $b 3)$ 로 제한된다.

정확도

이 발전기의 오차 측정은 복합수를 출력할 확률이다.

조건부 확률(이전 섹션에 표시됨)과 $\Pr(P)$ ) ${\displaystyle \Pr(P)}($ 바로 전에 표시됨)의 점증거동 사이의 관계를 사용하여 다음과 같은 큰 상한을 지정할 수 있다.

displaystyle \Pr(\lnot P\mid M\!)!R_{k}<Pr(M\!)!R_{k}\mid \lnot P)\cdot \cdot \cdmac({\tfrac {1}{\Pr(P)}-1\b-k}\cdot \left({\tfrac {\\\\\ln2}}:b-1+{O}\math{-1}\{-1}:{-1}}}}}}}}}:{-1}:{-1}:{-1}:{-1}:{-1}:{-1}:{-1}:{-1}:{-1}:{-1}:{-1}:{-1}:{-1}:{-1}:{

따라서 b가 충분히 큰 경우 이 오차 측정치는 ${\tfrac {\ln 2}{2}}\cdot b\cdot 4^{-k}$ n ${\tfrac {\ln 2}{2}}\cdot b\cdot 4^{-k}$ ${\tfrac {\ln 2}{2}}\cdot b\cdot 4^{-k}$ b ${\tfrac {\ln 2}{2}}\cdot b\cdot 4^{-k}$ 4 ${\tfrac {\ln 2}{2}}\cdot b\cdot 4^{-k}$ - ${\tfrac {\ln 2}{2}}\cdot b\cdot 4^{-k}$ ${\$ }{2 $}}\cdot b\cdot 4^{-k}$ 보다 작지만 훨씬 더 나은 한계가 존재한다 ${\tfrac {\ln 2}{2}}\cdot b\cdot 4^{-k}$

Miller-Rabin 시험 자체에서 종종^−k 4(이전 참조)보다 훨씬 작은 오차가 발생한다는 사실을 이용하여, Damgård, Landrock 및 Pomerance는 다양한 등급의 매개변수 b와 k로 발전기에 대한 몇 가지 오차 한계를 도출했다.^[7]이러한 오류 한계로 인해 구현자는 원하는 정확도에 대해 합리적인 k를 선택할 수 있다.

이러한 오류 범위 중 하나는 4로^−k, 모든 b 2 2를 유지한다(저자들은 b ≥ 51에 대해서만 그것을 보여주었고, 로널드 버스트 주니어는 나머지 값 2 2 b ≤ 50으로^[19] 증거를 완성했다).다시 말해서 이 단순한 바운드는 b의 큰 값에 대해 개선될 수 있다.예를 들어, 동일한 저자가 도출한 또 다른 경계는 다음과 같다.

\leftt\tfrac {1}{7}b^{15/4}2^{-b/2}\오른쪽)\cdot 4^{-k}}

모든 b ≥ 21과 k ≥ b 4를 지탱한다.이 바운드는 b ≥ 32가 되자마자 4보다^−k 작다.

메모들

^ 밀러-라빈 테스트는 종종 M. M. Artjuhov에 의해 1967년 즉시 발견되었다고 잘못 알려져 있다; Artjuhov의 논문^[3](특히 그의 정리 E)을 읽으면 그가 실제로 Solovay-Strassen 테스트를 발견했다는 것을 보여준다.
^ 예를 들어, 1995년에 아르놀트는 397자리 숫자의 합성 숫자를 주는데, 이 숫자는 307호 이하의 모든 베이스가 강한 거짓말쟁이들이며, 이 숫자는 메이플에 의해 프라임이라고 보고되었다. isprime()기능, 특정 베이스 2, 3, 5, 7, 11을 사용하여 Miller-Rabin 시험을 구현했기 때문이다.^[5]
^ 예를 들어, 2018년에 Albrecht 등은 OpenSSL, GNU GMP와 같은 많은 암호 라이브러리에 대해 이러한 라이브러리가 prime이라고 선언하는 복합 번호를 구축할 수 있었고, 따라서 대립적인 문맥을 염두에 두고 구현되지 않았음을 증명했다.^[8]

참조

^ ^a ^b Miller, Gary L. (1976), "Riemann's Hypothesis and Tests for Primality", Journal of Computer and System Sciences, 13 (3): 300–317, doi:10.1145/800116.803773, S2CID 10690396
^ ^a ^b Rabin, Michael O. (1980), "Probabilistic algorithm for testing primality", Journal of Number Theory, 12 (1): 128–138, doi:10.1016/0022-314X(80)90084-0
^ Artjuhov, M. M. (1966–1967), "Certain criteria for primality of numbers connected with the little Fermat theorem", Acta Arithmetica, 12: 355–364, MR 0213289
^ ^a ^b Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. (July 1980). "The pseudoprimes to 25·10⁹" (PDF). Mathematics of Computation. 35 (151): 1003–1026. doi:10.1090/S0025-5718-1980-0572872-7.
^ F. Arnault (August 1995). "Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases". Journal of Symbolic Computation. 20 (2): 151–161. doi:10.1006/jsco.1995.1042.
^ ^a ^b Schoof, René (2004), "Four primality testing algorithms" (PDF), Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography, Cambridge University Press, ISBN 978-0-521-80854-5
^ ^a ^b Damgård, I.; Landrock, P. & Pomerance, C. (1993), "Average case error estimates for the strong probable prime test" (PDF), Mathematics of Computation, 61 (203): 177–194, Bibcode:1993MaCom..61..177D, doi:10.2307/2152945, JSTOR 2152945
^ Martin R. Albrecht; Jake Massimo; Kenneth G. Paterson; Juraj Somorovsky (15 October 2018). Prime and Prejudice: Primality Testing Under Adversarial Conditions (PDF). ACM SIGSAC Conference on Computer and Communications Security 2018. Toronto: Association for Computing Machinery. pp. 281–298. doi:10.1145/3243734.3243787.
^ Bach, Eric (1990), "Explicit bounds for primality testing and related problems", Mathematics of Computation, 55 (191): 355–380, Bibcode:1990MaCom..55..355B, doi:10.2307/2008811, JSTOR 2008811
^ Jaeschke, Gerhard (1993), "On strong pseudoprimes to several bases", Mathematics of Computation, 61 (204): 915–926, doi:10.2307/2153262, JSTOR 2153262
^ Jiang, Yupeng; Deng, Yingpu (2014). "Strong pseudoprimes to the first eight prime bases". Mathematics of Computation. 83 (290): 2915–2924. doi:10.1090/S0025-5718-2014-02830-5.
^ Sorenson, Jonathan; Webster, Jonathan (2015). "Strong Pseudoprimes to Twelve Prime Bases". Mathematics of Computation. 86 (304): 985–1003. arXiv:1509.00864. Bibcode:2015arXiv150900864S. doi:10.1090/mcom/3134. S2CID 6955806.
^ ^a ^b Caldwell, Chris. "Finding primes & proving primality — 2.3: Strong probable-primality and a practical test". The Prime Pages. Retrieved February 24, 2019.
^ Zhang, Zhenxiang & Tang, Min (2003), "Finding strong pseudoprimes to several bases. II", Mathematics of Computation, 72 (44): 2085–2097, Bibcode:2003MaCom..72.2085Z, doi:10.1090/S0025-5718-03-01545-X
^ Sloane, N. J. A. (ed.). "Sequence A014233 (Smallest odd number for which Miller–Rabin primality test on bases <= n-th prime does not reveal compositeness)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
^ Izykowski, Wojciech. "Deterministic variants of the Miller–Rabin primality test". Retrieved February 24, 2019.
^ Alford, W. R.; Granville, A.; Pomerance, C. (1994), "On the difficulty of finding reliable witnesses" (PDF), Lecture Notes in Computer Science, Springer-Verlag, 877: 1–16, doi:10.1007/3-540-58691-1_36, ISBN 978-3-540-58691-3
^ Robert Baillie; Samuel S. Wagstaff, Jr. (October 1980). "Lucas Pseudoprimes" (PDF). Mathematics of Computation. 35 (152): 1391–1417. doi:10.1090/S0025-5718-1980-0583518-6. MR 0583518.
^ Burthe Jr., Ronald J. (1996), "Further investigations with the strong probable prime test" (PDF), Mathematics of Computation, 65 (213): 373–381, Bibcode:1996MaCom..65..373B, doi:10.1090/S0025-5718-96-00695-3

외부 링크

Weisstein, Eric W. "Rabin-Miller Strong Pseudoprime Test". MathWorld.
결정론적 변형의 온라인 대화형 구현(알고리즘 단계별 단계별 단계별 단계별 단계별 단계별 단계별 단계별 단계별)
애플릿(독일어)
C#의 밀러-라빈 원시성 검정
임의 정밀 산술법을 사용한 자바스크립트의 밀러-라빈 소수성 검정

[4] 밀러-라빈 테스트는 종종 M. M. Artjuhov에 의해 1967년 즉시 발견되었다고 잘못 알려져 있다; Artjuhov의 논문^[3](특히 그의 정리 E)을 읽으면 그가 실제로 Solovay-Strassen 테스트를 발견했다는 것을 보여준다.

[7] 예를 들어, 1995년에 아르놀트는 397자리 숫자의 합성 숫자를 주는데, 이 숫자는 307호 이하의 모든 베이스가 강한 거짓말쟁이들이며, 이 숫자는 메이플에 의해 프라임이라고 보고되었다. isprime()기능, 특정 베이스 2, 3, 5, 7, 11을 사용하여 Miller-Rabin 시험을 구현했기 때문이다.^[5]

[11] 예를 들어, 2018년에 Albrecht 등은 OpenSSL, GNU GMP와 같은 많은 암호 라이브러리에 대해 이러한 라이브러리가 prime이라고 선언하는 복합 번호를 구축할 수 있었고, 따라서 대립적인 문맥을 염두에 두고 구현되지 않았음을 증명했다.^[8]

[miller-1] Miller, Gary L. (1976), "Riemann's Hypothesis and Tests for Primality", Journal of Computer and System Sciences, 13 (3): 300–317, doi:10.1145/800116.803773, S2CID 10690396

[rabin-2] Rabin, Michael O. (1980), "Probabilistic algorithm for testing primality", Journal of Number Theory, 12 (1): 128–138, doi:10.1016/0022-314X(80)90084-0

[3] Artjuhov, M. M. (1966–1967), "Certain criteria for primality of numbers connected with the little Fermat theorem", Acta Arithmetica, 12: 355–364, MR 0213289

[PSW-5] Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. (July 1980). "The pseudoprimes to 25·10⁹" (PDF). Mathematics of Computation. 35 (151): 1003–1026. doi:10.1090/S0025-5718-1980-0572872-7.

[Arnault397Digit-6] F. Arnault (August 1995). "Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases". Journal of Symbolic Computation. 20 (2): 151–161. doi:10.1006/jsco.1995.1042.

[schoof-8] Schoof, René (2004), "Four primality testing algorithms" (PDF), Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography, Cambridge University Press, ISBN 978-0-521-80854-5

[damgård-landrock-pomerance-9] Damgård, I.; Landrock, P. & Pomerance, C. (1993), "Average case error estimates for the strong probable prime test" (PDF), Mathematics of Computation, 61 (203): 177–194, Bibcode:1993MaCom..61..177D, doi:10.2307/2152945, JSTOR 2152945

[10] Martin R. Albrecht; Jake Massimo; Kenneth G. Paterson; Juraj Somorovsky (15 October 2018). Prime and Prejudice: Primality Testing Under Adversarial Conditions (PDF). ACM SIGSAC Conference on Computer and Communications Security 2018. Toronto: Association for Computing Machinery. pp. 281–298. doi:10.1145/3243734.3243787.

[12] Bach, Eric (1990), "Explicit bounds for primality testing and related problems", Mathematics of Computation, 55 (191): 355–380, Bibcode:1990MaCom..55..355B, doi:10.2307/2008811, JSTOR 2008811

[13] Jaeschke, Gerhard (1993), "On strong pseudoprimes to several bases", Mathematics of Computation, 61 (204): 915–926, doi:10.2307/2153262, JSTOR 2153262

[14] Jiang, Yupeng; Deng, Yingpu (2014). "Strong pseudoprimes to the first eight prime bases". Mathematics of Computation. 83 (290): 2915–2924. doi:10.1090/S0025-5718-2014-02830-5.

[15] Sorenson, Jonathan; Webster, Jonathan (2015). "Strong Pseudoprimes to Twelve Prime Bases". Mathematics of Computation. 86 (304): 985–1003. arXiv:1509.00864. Bibcode:2015arXiv150900864S. doi:10.1090/mcom/3134. S2CID 6955806.

[prime-pages-16] Caldwell, Chris. "Finding primes & proving primality — 2.3: Strong probable-primality and a practical test". The Prime Pages. Retrieved February 24, 2019.

[17] Zhang, Zhenxiang & Tang, Min (2003), "Finding strong pseudoprimes to several bases. II", Mathematics of Computation, 72 (44): 2085–2097, Bibcode:2003MaCom..72.2085Z, doi:10.1090/S0025-5718-03-01545-X

[18] Sloane, N. J. A. (ed.). "Sequence A014233 (Smallest odd number for which Miller–Rabin primality test on bases <= n-th prime does not reveal compositeness)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

[19] Izykowski, Wojciech. "Deterministic variants of the Miller–Rabin primality test". Retrieved February 24, 2019.

[20] Alford, W. R.; Granville, A.; Pomerance, C. (1994), "On the difficulty of finding reliable witnesses" (PDF), Lecture Notes in Computer Science, Springer-Verlag, 877: 1–16, doi:10.1007/3-540-58691-1_36, ISBN 978-3-540-58691-3

[baillie-21] Robert Baillie; Samuel S. Wagstaff, Jr. (October 1980). "Lucas Pseudoprimes" (PDF). Mathematics of Computation. 35 (152): 1391–1417. doi:10.1090/S0025-5718-1980-0583518-6. MR 0583518.

[burthe-22] Burthe Jr., Ronald J. (1996), "Further investigations with the strong probable prime test" (PDF), Mathematics of Computation, 65 (213): 373–381, Bibcode:1996MaCom..65..373B, doi:10.1090/S0025-5718-96-00695-3

[1]

[2]

[a]

[4]

[b]

[6]

[7]

[c]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[3]

[5]

[8]

v t 수이론적 알고리즘
원시성 검정	AKS APR 바일리-PSW 타원곡선 포클링턴 페르마 루카스 루카스-레머 루카스-레머-리젤 프로트의 정리 페핀스 이차적 프로베니우스 솔로베이-스트라센 밀러-라빈
프라임 생성	앳킨의 체 에라토스테네스의 체 순다람의 체 휠 인자화
정수 인자화	지속분수(CFRAC) 딕슨스 Lenstra 타원 곡선(ECM) 오일러즈 폴라드 호 p − 1 p + 1 2차 체(QS) 일반수 필드 체(GNFS) 특수수 필드 체(SNFS) 이성 체 페르마츠 샨크스의 사각형 재판분할 쇼르스
곱하기	고대 이집트인 긴 카라츠바 툼-쿡 sch나게-스트라센 총통의
유클리드 주 나누기	이진수 청킹 푸리에 골드슈미트 뉴턴-래프슨 긴 짧다 SRT
이산 로그	베이비 스텝 거인 스텝 폴라드 로 폴라드 캥거루 포흘리그-헬먼 지수 미적분학 기능장 체
최대공통점	이진수 유클리드 주 확장유클리드 르메르스
모듈형 제곱근	시폴라 포클링턴스 토넬리-상크스 베를레캄프 쿠네르스
기타 알고리즘	차크라발라 코르나키아 제곱에 의한 지수화 정수 제곱근 정수 관계(LL; KZ) 모듈형 지수 몽고메리 환원 슈프
이탤릭체는 알고리즘이 특수형태의 숫자에 대한 것임을 나타낸다.

Search