#23318: 米勒-拉賓(MillerRabbin)演算法(C++)


DE45A (一葉之秋)

School : 新北市立板橋高級中學
ID : 68688
IP address : [118.166.66.52]
Last Login :
2021-01-24 12:54:21
f394. 心愛數質數 | From: [1.172.150.32] | Post Date : 2020-11-07 17:49

 

這題可以用米勒-拉賓(MillerRabbin)演算法

附上關鍵程式碼(注意益位問題)

bool M_R(long long a,long long n){

long long d=n-1,r=0;

while(d%2==0)d/=2,++r;

long long k=pow(a,d)%n;

if(k==1)return true;

for(int i=0;i<=r;++i,k=k*k%n){

if(k==n-1)return true;

}

return false;

}

 
#23350: Re:米勒-拉賓(MillerRabbin)演算法(C++)


HaKkaz (luckyanthonyan)

School : 新北市立板橋高級中學
ID : 83096
IP address : [27.247.225.213]
Last Login :
2021-01-26 23:19:55
f394. 心愛數質數 | From: [203.64.161.234] | Post Date : 2020-11-09 16:18

 

這題可以用米勒-拉賓(MillerRabbin)演算法

附上關鍵程式碼(注意益位問題)

bool M_R(long long a,long long n){

long long d=n-1,r=0;

while(d%2==0)d/=2,++r;

long long k=pow(a,d)%n;

if(k==1)return true;

for(int i=0;i<=r;++i,k=k*k%n){

if(k==n-1)return true;

}

return false;

}


電~~~~~~

 
#23351: Re:米勒-拉賓(MillerRabbin)演算法(C++)


valder (valder)

School : 新北市立板橋高級中學
ID : 83342
IP address : [203.64.161.114]
Last Login :
2021-01-27 14:51:22
f394. 心愛數質數 | From: [203.64.161.163] | Post Date : 2020-11-09 16:19

 

這題可以用米勒-拉賓(MillerRabbin)演算法

附上關鍵程式碼(注意益位問題)

bool M_R(long long a,long long n){

long long d=n-1,r=0;

while(d%2==0)d/=2,++r;

long long k=pow(a,d)%n;

if(k==1)return true;

for(int i=0;i<=r;++i,k=k*k%n){

if(k==n-1)return true;

}

return false;

}


電~~~~~~


\電神教我写程式~~~/

 
#23484: Re:米勒-拉賓(MillerRabbin)演算法(C++)


nick930212@gmail.com (arod571431)

School : 臺北市立麗山高級中學
ID : 119219
IP address : [119.77.194.9]
Last Login :
2021-01-27 22:01:14
f394. 心愛數質數 | From: [114.136.123.116] | Post Date : 2020-11-21 19:28

 

這題可以用米勒-拉賓(MillerRabbin)演算法

附上關鍵程式碼(注意益位問題)

bool M_R(long long a,long long n){

long long d=n-1,r=0;

while(d%2==0)d/=2,++r;

long long k=pow(a,d)%n;

if(k==1)return true;

for(int i=0;i<=r;++i,k=k*k%n){

if(k==n-1)return true;

}

return false;

}


電~~~~~



 
ZeroJudge Forum