@chawuciren
2019-10-21T15:26:46.000000Z
字数 1789
阅读 583
CINTA
1、构造Zp*的子群。随机取一个Zp*中的元素g,不断做g的平方、g的立方,g的4次方,......,把所得放到一个集合S中,直到S不再增加。并计算S的阶。
/*
* Input: 素数p
* Output: Zp*的子集S的阶
*/
int subgroup_1(int p){
int* arr=(int *)malloc(sizeof(int)*p);//用一个空数组检查元素是否在子集中,存在将数组对应下标的元素置为1
for(int i=0;i<p;i++) arr[i]=0;//初始化
srand((unsigned)time(NULL));
int a = rand() % (p-1)+1;//在1到p-1中随机取一个数
int b=a;
int count=0;
while(1){
b=b*a%p;//不断做g^2 g^3......
if(arr[b]) break;//直到跑回原来的位置停止
else arr[b]=1;//如果元素不存在则将元素放入子集中
}
for(int i=0;i<p;i++){
if(arr[b]==1) count++;//计算子集中的元素个数
}
return count;
}
2、构造Zp*的子群。对Zp*中的所有元素g做平方,所得放集合S中。计算S的阶。
/*
* Input: 素数p
* Output: Zp*的子集S的阶
*/
int subgroup_2(int p){
int* arr=(int *)malloc(sizeof(int)*p);
for(int i=0;i<p;i++) arr[i]=0;
int b=0;
int count=0;
for(int i=1;i<p;i++){
b=i*i%p;//对Zp*中的所有元素做平方
arr[b]=1;//将所得放入S中
}
for(int i=0;i<p;i++){
if(arr[b]==1) count++;
}
return count;
}
3、构造Zn*的子群。取Zn*中的两个元素,放到集合S中,不断重复对S中的任意两个元素进行乘法,所得如果在S中则忽略,否则加入S,直到S不再增加。计算S的阶。
/*
* Input: 合数n
* Output: Zn*的子集S的阶
*/
int Subgroup(int n){
int num=Euler_phi(n);//计算Zn*中有多少个元素
int j=0;
int*S=(int*)malloc(sizeof(int)*num);
for(int i=1;i<n;i++){//算出所有Zn*的元素放入S中
if(gcd(i,n)==1){
S[j]=i;
j++;
}
}
int order=Calculation(S,num,n);//计算子群的阶
return order;
}
int Calculation(int* S,int num,int n){
int count=2;
int p1=0;
int p2=0;
int stop=0;
srand((unsigned)time(NULL));
p1 = rand() % (num);
do{
p2=rand() % (num);
}while(p2==p1);//随机取Zn*中的两个不同元素
int* sub=(int*)malloc(sizeof(int)*num);//用于存放子群的元素
int* inspect=(int*)malloc(sizeof(int)*n);//用于检查子群元素是否存在
for(int i=0;i<num;i++){//初始化
sub[i]=0;
}
for(int i=0;i<n;i++){//初始化
inspect[i]=0;
}
sub[0]=S[p1];//选取的两个元素放入子集中
sub[1]=S[p2];
inspect[sub[0]]=1;//如果该元素已存在,将inspect数组对应下标的元素置1
inspect[sub[1]]=1;
for(int i=1;i<num;i++){
for(int j=0;j<num;j++){
if(i==j) {//如果没有新元素,循环停止
stop=1;
break;
}
if(inspect[sub[j]*sub[i]%n]==0){//如果是新元素,将新元素放入子集
sub[count]=sub[j]*sub[i]%n;
inspect[sub[j]*sub[i]%n]=1;
count++;//计算阶
}
}
if(stop==1) break;
}
return count;
}