CINTA作业14-CRT题

CINTA

---

5.1
a=8,b=3,p=11,q=19,n=pq=209
$p_1 \equiv p^{-1}(mod\ q)\ \ \ q_1 \equiv q^{-1}(mod\ p)$ using EGCD algothm
$p_1=7\ \ q_1=7$
$y\equiv aqq_1+bpp_1(mod\ n)$ y=41

5.2
M=5*7*9*11=3465
$b_1=693$
$b_2=495$
$b_3=385$
$b_4=315$
$b_{1}^{'}=2$
$b_{2}^{'}=3$
$b_{3}^{'}=4$
$b_{4}^{'}=8$
$y=1*693*2+2*495*3+3*385*4+4*315*8=1731$

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
$f(x) \triangleq\ ([x\ mod\ p],[x\ mod\ q])$
1.Show f is injective
Suppose:

$$\forall a,b \in Z_n^*,a\neq b,f(a)=f(b)\\ f(a)=([a\ mod\ p],[a\ mod\ q])\\ f(b)=([b\ mod\ p],[b\ mod\ q])\\ ([a\ mod\ p],[a\ mod\ q]) \neq ([b\ mod\ p],[b\ mod\ q])$$
So it doesn't exist $a \neq b, f(a)=f(b)$

2.Show f is surjective

$$\forall n_1 \in Z_p^* \times Z_q^*,p_1 \in Z_p^*,q_1 \in Z_q^* \\ n_1=(p_1,q_1)=([x\ mod\ p],[x\ mod\ q]),x\in Z^*_n$$
So f is surjective

3.Check that f(x) preserves the group operation.
$f(a)*f(b)=([a\ mod\ p],[a\ mod\ q])*([b\ mod\ p],[b\ mod\ q])=([ab\ mod\ p],[ab\ mod\ q])=f(ab)$

it is an isomorphism from $Z^∗_n\ to\ Z^∗_p×Z^∗_q$.

5.5

$$Z^*_{35}=\{1,2,3,4,6,8,9,11,12,13,16,17,18,19,22,23,24,26,27,29,31,32,33,34 \}\\ Z^*_5=\{1,2,3,4\}\\ Z^*_7=\{1,2,3,4,5,6\}\\ 1\leftrightarrow(1,1)\ \ 2\leftrightarrow(2,2)\ \ 3\leftrightarrow(3,3)\\ 4\leftrightarrow(4,4)\ \ 6\leftrightarrow(1,6)\ \ 8\leftrightarrow(3,1)\\ 9\leftrightarrow(4,2)\ \ 11\leftrightarrow(1,4)\ \ 12\leftrightarrow(2,5)\\ 13\leftrightarrow(3,6)\ \ 16\leftrightarrow(1,2)\ \ 17\leftrightarrow(2,3)\\ 18\leftrightarrow(3,4)\ \ 19\leftrightarrow(4,1)\ \ 22\leftrightarrow(2,1)\\ 23\leftrightarrow(3,2)\ \ 24\leftrightarrow(4,3)\ \ 26\leftrightarrow(6,5)\\ 27\leftrightarrow(2,6)\ \ 29\leftrightarrow(4,1)\ \ 31\leftrightarrow(1,3)\\ 32\leftrightarrow(2,4)\ \ 33\leftrightarrow(3,5)\ \ 34\leftrightarrow(4,6)\ $$