CS202 Assignment 4: Group Theory, Modular Arithmetic, and QFT Analysis

This document presents solutions to Assignment 4 for the CS202 course, focusing on theoretical computer science concepts. The assignment covers several key areas, including group theory, modular arithmetic, and quantum computing. Problem 1 explores the multiplication table of G11, identifies generators for the group and its subgroups. Problem 2 requires constructing a multiplication table for G24 and determining the inverses of each element. Problem 3 delves into the Euclidean Algorithm and Bezout's Lemma, calculating modular inverses and solving linear Diophantine equations. Finally, Problem 4 addresses RSA encryption, including computing N, φ(N), and the decryption exponent, as well as the decryption of a ciphertext. Problem 5 provides a QFT operator defined to act as a single qubit states.

STATISTICS CS202
Problem 1
a)
Assume that p=11 and Z*={1,2,3,4,5,6,7,8,9,10} which has got the order of p-1 =11-1 =10.
i 0 1 2 3 4 5 6 7 8 9
2i mod
11
1 2 4 8 5 10 9 7 3 6
5imod
11
1 5 3 4 9 1 5 3 4 9
b)
Two elements would generate the entire group of Z*11.These includes;
[2]={1,2,3,4,5,6,7,8,9,10}
[5]={1,3,4,5,9}
c)
m=φ(11)=10
From the factorization of 10 we get 21.51
a 2≠ 1(mod 11) and a 5≠ 1(mod 11)

a 1 2 3 4 5 6 7 8 9 10
a
2mod
11
1 4 9 5 3 3 5 9 4 1
a 5
mod
11
1 10 1 1 1 10 10 10 1 10
Gen (Z*11)={2,6,7,8}
|Z*11|=10 ,Z*10 ={1,3,7,9}
The Inverse:
{2i
∈G::i∈ Z*10}={21,23,27,29(mod 11)}=[2,6,7,8}
Problem 2
Consider all the elements in G24 and write down the table for the group.
G24={1,5,7,11,13,17,19,23}
1 5 7 11 13 17 19 23
1 1 5 7 11 13 17 19 23
5 5 7 11 13 17 19 23 1
7 7 11 13 17 19 23 1 5
11 11 13 17 19 23 1 5 7
13 13 17 19 23 1 5 7 11
17 17 19 23 1 5 7 11 13
19 19 23 1 5 7 11 13 17
23 23 1 5 7 11 13 17 23
For any element G(24),there is an inverse, given as ;
1-1=1,5-1=5,7-1=7,11-1=11,13-1=13,17-1=17,19-1=19,23-1=23

Problem 3
Problem 3 a
For non-zero integers of a and b,you can write;
a * x +b * y=1
a *x + b* y=+1
Apply mod b on both sides to get;
a * x mob b =1 mod b
This explains x to be a modular of a.
Hence you can calculate the inverse :
First step
Apply the Euclidean Algorithm to find gcd(23,9)
23=9*2 +5
9=5 *1 +4
5=4 *1 +1
4=1*4 +0
gcd (23,9)=gcd(5,4) =gcd(4,1)=gcd(1,0)=1
Second Step
Apply the extended Euclidean algorithm to get x and y
Write the equation on the right in terms of a=23,b=9
23=1a +0b

9=0a + 1 b
23 =9 * 2 +5
9=5*1+4
5=4*1+1
4=1*4 +0
23= 1a +ob
9=0a + 1b
5=1a -2b
4=-1a +3b
1=2a -5b
Problem 3 b
Consider the equation
23=9*2 +5
Rearrange the equation to
5=23-2*9
But from our previous equation;
23=1a + 0b
9=0a + 1b
Therefore ,
5=(1a+0b)-2*(0a +1b)
5=1a-2b

You can realize that
1=2a -5b
And this gives
1=2*23-5* 9
Hence
X=2,y=-5 as the solution to 23* x+9*y=1
Hence 2 is the modular of 23 (mod 9)
And this results to the case:
23*2 mod9=46mod 9=1
Problem 4
a)
You are to select two prisons i.e p=59 and q=101
Compute N=pq
=101*59
=5959
Compute φ(N)=(p-1)(q-1)
=(101-1)(59-1)
=5800
b)
Consider x and y as integers such that gcd(421,111)=421x+111y
Hence a=421 ,b=111

You can work backward line in the Euclidean Algorithm as illustrated.
1=4-1*3
1=4-1 x(19-4 x 4
1=-1 x 19 +5 x 4
1=-1x 19 +5 x(23-1x19)
1=5x23-6x19
1=5x 23-6x(88-3x23)
1=-6 x 88 +23 x 23
1=23 x111 -29 X(421-3X111)
1=-29x421 +110+110
Thus x=-29,and y=110
Rearrange the equation and substitute the lower factor of the Euclidean
algorithm.
Xa +yb=-29x 421 +110x111
=-12209 +12210
=1
C)
Cd=1 mod φ
41d=1mod 5800
d =3
d)

a=bd mod N
=25079 mod 5959
=3533
Problem 5
Consider a QFT operator defined to act as a single qubit states
Ѱ=α|0) +β|1)
Hence x0=α and x1 =β1
Y0= 1
√2 (αexp(2 i⫪ 0+φ
2 )+ βexp(2 I⫪ 1∗0
2 ))= 1
√ 2 (α+β)
Y1= 1
√2 (αexp(2 I⫪ 0+1
2 )+ βexp(2 I⫪ 1∗1
2 )= 1
√ 2 (α+β)
UQFT= 1
√ 2 (α+β)|1)
You can apply the Hadamand operator (H) on the qubit;
|=α|) +β|x]Ѱ
1
√ 2 (α+β)0) + 1
√ 2 (α+β)|1)=α|0)+β|1)
=1