CINTA作业12--编程题（子群）

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;
}