miller rabin.cpp

密码学中的Miller Rabin素性检测算法。人工编写

// Miller Rabin.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdlib.h"
#include "stdio.h"
#include "string.h"

long int  fastmod(long int x,long int e_int,long int n)
{	long int c=1,k,i;
	char e_str[80];
	itoa(e_int,e_str,2);										//调用此函数求b^d(mod n)
	k=strlen(e_str);					
	c=x;														//调用itoa函数进行二进制转换
	for(i=1;i<k;i++)					
	{
		if(e_str[i]==49)
			c=(c*c*x)%n;
		else 
			c=(c*c)%n;
	}
	return c;
}


int main(int argc, char* argv[])
{
	long int b,d,i,j,n,y;
	do															//保证输入的要判断的数是奇数
	{
		printf("please input the number needed to judge:\n");
		scanf("%ld",&n);
		if(n%2==0)
			printf("please input the odd!\n");
	
	}while(n%2==0);												//保证输入的基数是在确定范围之内
	do
	{
		printf("please input the base(1<b<%ld):\n",n);
		scanf("%ld",&b);
		if(b<2||b>=n)
			printf("please input the base between 1 and %ld\n",n);
	}while(b<2||b>=n);
	d=n-1;
	for(j=0;d%2==0;j++)											//求出i和d
		d/=2;
	y=fastmod(b,d,n);
	for(i=0;i<j;i++)
	{
		if(i==0&&y==1||y==n-1)									//判断n是否是强概素数
		{
			printf("%ld is probably prime\n",n);
			return 1;
		}
		if(i>0&&y==1)
			break;
		y=(y*y)%n;
	}
	printf("%ld is definitely not prime\n",n);
	return 0;
}