경라빈소수 판정법에 대한 필기

소수 판정

전제 지식

필머의 소정리
p를 소수로 하면\
a^{p-1}\equiv 1\pmod p\\
증명략
그리고 하나
p를 소수로 하면\
a^2\equiv 1\pmod p\\
설립된 a는 1 및 - 1\pmod p 뿐입니다.
증명서
공식 변형 후
a^2 - 1\equiv 0\pmod p\\
(a + 1)(a - 1)\equiv 0\pmod p
(a+1)(a-1)은 p의 배수이다
만약 p가 소수의 두 수의 적을 표시한다면 1\times p의 경우에만
a=0의 경우 a+1은 1이지만 a^{2}\equiv1이 충족되지 않아 적합하지 않습니다
따라서 a+1 또는 a-1은 p의 배수이다
a+1이 p의 배수일 때 a+1\equiv0\pmod p 즉 a\equiv-1\pmod p
a-1이 p의 배수일 때 a+1\equiv0\pmod p 즉 a\equiv1\pmod p

벨벳 테스트

n이 소수인지 여부
적당히 a(n과 상호위소)를 취하고 a^{p-1}\equiv1\pmodn이 성립되었으나 조사
만약 성립되지 않는다면, 확실히 소수가 아니라고 말할 수 있다
필머의 소정리의 짝을 얻었기 때문에.
a^{p-1}\not\equiv 1\pmod p\\
그러면 p는 소수가 아니에요.
되다
그러나 성립되더라도 소수인지 아닌지는 모른다
a를 많이 얻었으니 모두 성립했으면 좋겠다
진전이 순조롭지 못한 a를 얻을 확률은 기본적으로 1/2 정도이다

필머 테스트의 문제점

아무리 섭취해도
모든 a^{p-1}\equiv1\pmon이 설립한 n무수(카마이클수라고 부른다)
5611115 등

밀라빈 테스트

p를 홀수로 하는 소수
그리고 p-1은 짝수.
p-1 = 2^{s}t
거기에 두셔도 돼요.
이때 이하 성립
p는 소수일 때\\
a^t\equiv 1\pmod p\\
또는 r(0\ler\les-1)\\
a^{2^{r}t}\equiv -1\pmod p\\
성립
증명서
필머에서 온 소정리
a^{2^{s}t}\equiv 1\pmod p
이 제곱근은 a^{s-1}t}가 1 또는 -1(modp)이다
-1의 경우 (7)의 후자의 식은 성립된다
1의 경우 제곱근을 다시 고려한다.
이렇게 고려할 때 r=0 이전에 하나도 -1이 되지 않았다고 가정하자.(전체 1)
이때
a^{2^{0}t} = a^{t}\equiv 1\pmod n
이것은 (5)의 이전 공식을 만족시킨다
밀라빈 테스트 사용(5)의 대구
a^t\not\equiv 1\pmod p\\
또한 모든 r(0\ler\les-1)\\
a^{2^{r}t}\not\equiv -1\pmod p　\\
그럼 p는 합성수.
만약 이 조건이 충족된다면 확실히 합성수라고 할 수 있다
만약 만족하지 않는다면, 확실히 소수라고 말할 수 없다
이것도 a를 많이 가져와서 만족하지 않는지 조사를 했어요.
순조롭지 못한 a를 선택할 확률은 최대 1/4이다

결정적 알고리즘

원하는 수량 n이 n\le4559123141이면
{2,7,61}만 조사하면 됩니다.
\le2^{64} 의 경우
223259375281778978050751795265022만 조사하면 됩니다.
참고 자료
http://miller-rabin.appspot.com/

이루어지다

1\len\le2^{64} 올바른 작업

fn modpow(base: i64, mut exp: i64, m: i64) -> i64 {
    let mut ret = 1;
    let mut pow = base;
    while exp != 0 {
        if exp & 1 != 0 {
            ret = ((ret as i128 * pow as i128) % m as i128) as i64;
        }
        pow = ((pow as i128 * pow as i128) % m as i128) as i64;
        exp >>= 1;
    }
    ret
}

fn rabin_miller(n: i64) -> bool {
    if n <= 2 {
        return n == 2
    }
    if n % 2 == 0 {
        return false;
    }
    let mut s = 0;
    let mut t = n-1;
    while t % 2 == 0 {
        s += 1;
        t /= 2;
    }
    let is_prime = |a| {
        let mut x = modpow(a, t, n);
        if x == 1 || x == n-1 {
            return true;
        }
        for _ in 0..s-1 {
            x = ((x as i128 * x as i128) % n as i128) as i64;
            if x == n-1 {
                return true;
            }
        }
        false
    };
    for &a in &[2, 325, 9375, 28178, 450775, 9780504, 1795265022] {
        if a >= n {
            break;
        }
        if !is_prime(a) {
            return false;
        }
    }
    true 
}