Miller_라 빈 테스트 학습 소결

도입 - 윌 슨 정리, 페 마 소정 리
모두 가 이 윌 슨 의 정리 정 리 를 알 고 있 을 것 이 라 고 믿 습 니 다. 정리 내용 은 하나의 소수 p 에 대한 것 입 니 다. (p - 1)!▼ − 1 (modp), 이 물건 의 증명 은 내 가 앞에서 쓴 글 을 볼 수 있다.페 마 소정 리: 하나의 소수 p 에 대해 a 가 p 를 정제 하지 않 으 면 ap - 1, 1, 1 (modp) 이지 만 이 정리의 역정 리 는 성립 되 지 않 는 다.윌 슨 의 정 리 는 하나의 수가 소수 인지 아 닌 지 를 판단 하 는 충분 한 필요조건 이다.http://blog.csdn.net/ganjingxian/article/details/76268706여 기 는 더 이상 군말 하지 않 겠 습 니 다.이 물건 을 이용 하면 우 리 는 또 다른 정 리 를 내 놓 을 수 있다.
이차 탐측 정리
하나의 소수 n 에 대해 방정식 x2. 1 (modp) 모 p 의 뿌리 는 두 개 이 고 하 나 는 n - 1 이 며 다른 하 나 는 1 이다.우 리 는 이 두 뿌리 를 n 을 모델 로 하 는 평범한 제곱 근 이 라 고 부른다.결론: 하나의 수가 1 의 평범 하지 않 은 제곱 근 이 존재 한다 면 n 은 합 수 이다.
Miller_Rabin 소성 테스트 알고리즘 사고
① 여러 기 수 를 선택 하여 테스트 한다. (즉, 몇 개의 수 를 찾 아 테스트 하 는 것 이다)② 모델 n 이 1 인 평범 하지 않 은 제곱 근 을 찾 는 방법 은 다음 과 같다. 선령 n - 1 = 2u×t, 그 중에서 u ≥ 1, t 는 홀수 이 고 an - 1 = a2u×t = (at) 2u 는 먼저 at 를 계산 합 니 다. 물론 빠 른 속도 로 계산 한 다음 에 제곱 u 회 를 사용 합 니 다. 만약 제곱 과정 에서 현재 이 (at) 2k 모델 n 이 1 과 같다 는 것 을 발견 하면 n 은 소수 가 아 닙 니 다.③ 계산 을 마 친 후에 계산 한 이 값 이 1 인지 아 닌 지, 그렇지 않 으 면 이 숫자 는 소수 가 아니다.
예 를 들다
예 를 들 어 n = 341, a = 2, n - 1 = 340 = 22×85, x = 285, 32 (mod 341), 322, 1 (mod 341), 그러면 341 은 질 수가 아 닐 것 이다.
특별 성명
이 테스트 의 정확 도 는 100% 가 아니다. 연구 결과 에 따 르 면 s 차 의 오류 확률 은 최대 2 − s 로 나 타 났 으 나 일반적으로 이 알고리즘 은 정확성 이 높 고 시간 복잡 도도 높 지 않다.
코드
pacal 을 사용 하 는 동 지 는 맞 출 수 없습니다. 제 가 쓴 프로그램 이 너무 엉망 입 니 다. 테스트 23333333 33 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33,

var
        s,n:int64;
function mull(a,b,n:int64):int64;
var
        tmp:int64;
begin
        int64(tmp):=int64(double(a*b/n+1e-6))*n;
        exit(a*b-tmp);
end;
function f(a,b,n:int64):int64;
var
        t,y:int64;
begin
        t:=1;
        y:=a;
        while b<>0 do
        begin
                if(b and 1)=1 then
                t:=t*y mod n;
                y:=y*y mod n;
                b:=b shr 1;
        end;
        exit(t);
end;
function judge(n,a:int64):boolean;
var
        u,t,x,next,i:int64;
begin
        u:=0;
        t:=n-1;
        while t mod 2=0 do
        begin
                inc(u);
                t:=t div 2;
        end;
        x:=f(a,t,n);
        i:=1;
        while i<=u do
        begin
                next:=x*x mod n;
                if ((next=1)and(x<>1)and(x<>n-1)) then
                begin
                        exit(true);
                end;
                x:=next;
                inc(i);
        end;
        if x<>1 then exit(true);
        exit(false);
end;
function miller(n,s:int64):boolean;
var
        i:longint;
        a:int64;
begin
        if n=2 then
                exit(true);
        if (n=1) or (n mod 2=0) then exit(false);
        i:=1;
        while i<=s do
        begin
                a:=random(n-2)+2;
                if judge(n,a) then
                        exit(false);
                inc(i);
        end;
        exit(true);
end;
begin
        randomize;
        readln(n,s);
        if miller(n,s) then
                writeln('yes')
        else
                writeln('no');
end.

c++

#include
#include
#include
#define fo (i,a,b) for (int i=(a);i<=(b);i++)
#define fd (i,b,a) for (int i=(b);i>=(a);i--);
typedef  long long ll;
typedef  long double db;
ll n,s;
ll mult(ll a,ll b,ll n)
{
    ll temp=((ll)((db)a*b/n+1e-6)*n);
    return a*b-temp;
}
ll pow(ll a,ll b,ll n)
{
    ll t=1,y=a;
    while (b)
    {
        if (b&1)
            t=mult(t,y,n);
        y=mult(y,t,n);
        b=b>>1;
    }
    return t;
}
bool judge(ll n,ll a)
{
    ll u=0,t=n-1;
    while(t%2==0){u++;t=t/2;}
    ll x=pow(a,t,n);
    for(int i=1;i<=u;i++)
    {
        ll next=mult(x,x,n);
        if ((next==1)&&(x!=1)&&(x!=n-1))
        return true;
        x=next;
    }
    if (x!=1)return true;
    return false;
}
bool Miller_Rabin(ll n,int s)
{
    if (n==2)return true;
    if (n<2 || n % 2==0)return false;
    for(int i=1;i<=s;i++)
    {
        ll a=rand()%(n-2)+2;
        if (judge(n,a))return false;
    }
    return true;
}
int main()
{
    srand(time(0));
    scanf("%lld%d",&n,&s);
    if (Miller_Rabin(n,s))
        printf("yes");
    else
        printf("no");
    return 0;
}

c++ 는 pacal 처럼 215 가 두 렵 지 않 습 니 다.내 가 쓴 코드 가 너무 못 생 겼 나 봐.
마지막
위의 코드 중 하 나 는 블랙 테 크 놀 로 지 입 니 다. 바로 모델 일 때 이 를 전환 시 켜 mult (pacal 에서 mull) 로 바 꾸 는 것 입 니 다. 원리: a (modb) = a − [ab]×b. 이 물건 의 증명 은 매우 간단 합 니 다. 증 법 은 다음 과 같 습 니 다. a = bk + r 를 설정 합 니 다.
a(modb)=r=a−[bk+rb]×b=a−bk=r
the end
제 수준 이 제한 되 어 있 기 때문에 잘못 쓴 부분 이 있 을 수 있 습 니 다. 여러분 의 비판 과 지적, 포용, thank you for your patience.