getprime.cpp

素数Robin—Millor测试法的C语言源码

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<string.h>

#define MAX 32
char *binary=(char *)malloc(MAX*sizeof(char));        //用来存放十进制数转化的二进制数

unsigned int b_m_n(unsigned int ,unsigned int ,unsigned int );               //求b^m%n
int DecimalToBinary(unsigned int ,char *);                  //十进制转化为二进制（倒序）
bool test(unsigned int );            //Miller-Rabin测试
unsigned int random();       //产生一个32位奇随机数

int main(int argc,char *argv[])
{
	unsigned int n;

	while(argc!=3)      //若输入不符合要求，提示错误
	{
		printf("ERROR!\n");
		printf("Please input the form: getPrime getPrime 32bit\n");
		exit(0);
	}

	n=random();         //产生一个32位奇随机数

	while(!test(n))    //测试其是否是素数
		n=n+2;

	printf("\nThe Prime is (32-bit):\n%u\n",n);
	
	return 0;
}

unsigned int random()
{
	unsigned int n;

	srand((unsigned)time(NULL));    //随机数的种子 

	n=1;                   //产生一个32位奇随机数
	n=n<<1;
	for(int i=0;i<30;i++)
	{
		n+=rand()%2;
		n=n<<1;
	}
	n=n|1;

	return n;
}

bool test(unsigned int n)            //Miller-Rabin测试
{
	unsigned int a=0;
	int number=0;

	for(int i=0;i<5;i++)         //测试五次
	{
		a=b_m_n(rand(),n-1,n);
		if(a==1)
			number++;	
	}
	if(number==5)
		return true;
	else
		return false;	
}

unsigned int b_m_n(unsigned int b,unsigned int m,unsigned int n)             //求b^m%n
{	
	unsigned int a=1;
    unsigned __int64 bb=(unsigned __int64)b;
	int length;

	length=DecimalToBinary(m,binary);   //十进制转化为二进制（倒序）

	//b^n%m   
	for(int i=0;i<length;i++)
	{
		if(binary[i]==1)
			a=(a*bb)%n;

		bb=(bb*bb)%n;
	}

    return a;
}

int DecimalToBinary(unsigned int m,char *binary)       //十进制转化为二进制（倒序）
{
	unsigned int mm=m;
	int i;
	for(i=0;mm!=0;i++)
	{	
		binary[i]=mm & 1;	
		mm=mm>>1;
	}

	return i;
}