计算代数与计算数论.doc

大素数的生成
#include <stdio.h>
#include <stdlib.h>
//大素数的生成
int euild(int a,int b);
main()
{
int n,i,t,b;
printf("请输入一个奇数和安全系数(用逗号隔开)：");
scanf("%d,%d",&n,&t);i=1;
b=rand()%(n-3)+2;
if(euild(b,n)==1)
{
for(;i<=t;i++)
{
b=rand()%(n-3)+2;
if(euild(b^(n-1),n)!=1)
break; }}
if(i>t)
printf("该奇数很可能是一个素数！\n");
else
{printf("该奇数是不一个素数！\n它对%d不成立",b);}}
int euild(int a,int b)
{
int r[3],s[3],t[3],z,q;
if(a<b){z=a;a=b;b=z;}
r[0]=a;r[1]=b;s[0]=1;s[1]=0;t[0]=0;t[1]=1;
do{
q=r[0]/r[1];s[2]=s[0]-q*s[1];t[2]=t[0]-q*t[1];r[2]=r[0]-q*r[1];
s[0]=s[1];s[1]=s[2];t[0]=t[1];t[1]=t[2];r[0]=r[1];
r[1]=r[2];
}
while(r[1]!=0);
return abs(r[0]);
}

模重复平方计算法

N=input('请输入指数n的值：');
b=input('请输入b的值：');
m=input('请输入m的值');
i=0;
while N>0
i=i+1;
n(i)=mod(N,2);
N=fix(N/2);
end
if n(1)==0
a(1)=1;
else a(1)=mod(b,m);
end
b(2)=mod(b*b,m);
for j=2:1:i
if n(j)==0
a(j)=a(j-1);
else a(j)=mod(a(j-1)*b(j),m);
end
b(j+1)=mod(b(j)*b(j),m);
end
answer=a(j)

求两个数的最大公因数
#include <stdio.h>
main()
{
int r[3],s[3],t[3],a,b,z,q;
printf("请输入两个整数：");
scanf("%d,%d",&a,&b);
if(a<b){z=a;a=b;b=z;}
r[0]=a;r[1]=b;s[0]=1;s[1]=0;t[0]=0;t[1]=1;
do{
q=r[0]/r[1];s[2]=s[0]-q*s[1];t[2]=t[0]-q*t[1];r[2]=r[0]-q*r[1];s[0]=s[1];s[1]=s[2];
t[0]=t[1];t[1]=t[2];r[0]=r[1];r[1]=r[2];
}
while(r[1]!=0);
printf("%d*%d+%d*%d=%d\n",s[0],a,t[0],b,r[0]);}

求一个奇素数的全部原根

p=input('请输入一个奇素数：');
%找出指数
w=factor(p-1);
q=(p-1)./w;
i=1;
while i~=length(q)
if q(i)==q(i+1)
q(i+1)=[];i=i-1;
end
i=i+1;
end
%找出一个元根
i=2;
while i<p
for k=1:length(q)
if mochong(i,q(k),p)==1
break
end
end
if (k==length(q))&&(mochong(i,q(length(q)),p)~=1)
break
end
i=i+1;
end
%找出p-1的简化剩余系
k=1;
for j=1:1:p-1
if gcd(j,p-1)==1
qq(k)=j;
k=k+1;
end
end
disp('该素数的一个原根为：')
disp(i)
disp('它的指数为：')
disp(qq)

function y=mochong(b,N,m)
%clear
%clc
%N=input('请输入指数n的值：');
%b=input('请输入b的值：');
%m=input('请输入m的值');
if N==1
y=b;
else
i=0;
while N>0
i=i+1;
n(i)=mod(N,2);
N=fix(N/2);
end
if n(1)==0
a(1)=1;
else a(1)=mod(b,m);
end
b(2)=mod(b*b,m);
for j=2:1:i
if n(j)==0
a(j)=a(j-1);
else a(j)=mod(a(j-1)*b(j),m);
end
b(j+1)=mod(b(j)*b(j),m);
end
y=a(j);
end