@chawuciren
2019-11-19T10:41:27.000000Z
字数 2091
阅读 569
CINTA
5.1
a=8,b=3,p=11,q=19,n=pq=209
using EGCD algothm
y=41
5.2
M=5*7*9*11=3465
5.3
/*
* Input: a,b,q,p(x=a (mod q) x=b(mod p))
* Output: x
*/
int CRT(int a,int p,int b,int q){//x=a (mod q) x=b(mod p)
int n=p*q;
int p_1=egcd(p,q);
if(p_1<0) p_1=q+p_1; //overflow
int q_1=egcd(q,p);
if(q_1<0) q_1=p+q_1;
int y=(a*q*q_1)%n+(b*p*p_1)%n;
return y; //return solution
}
int egcd(int a, int b){
int r0=1,s1 = 1;
int r1=0,s0=0,q = 0,temp=0;
while (b){
q = a / b; //Seeking quotient
a = a%b;
swap(&a,&b);//Gcd algorithm on the right side of the equation
r0 = r0-(q*r1);//Gcd algorithm on the left side of the equation
swap(&r0,&r1);
s0 = s0 - (q*s1);
swap(&s0,&s1);
}
return r0;
}
void swap(int*a,int *b){//Exchange the values of a and b
int temp=*a;
*a=*b;
*b=temp;
}
5.4
proof:
Define f
1.Show f is injective
Suppose:
2.Show f is surjective
3.Check that f(x) preserves the group operation.
it is an isomorphism from .
5.5