1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
|
\newfam\bbold
\def\bb#1{{\fam\bbold #1}}
\font\bbten=msbm10
\font\bbsev=msbm7
\font\bbfiv=msbm5
\textfont\bbold=\bbten
\scriptfont\bbold=\bbsev
\scriptscriptfont\bbold=\bbfiv
\newcount\indentlevel
\newcount\itno
\def\reset{\itno=1}\reset
\def\afterstartlist{\advance\leftskip by .5in\par\advance\leftskip by -.5in}
\def\startlist{\par\advance\indentlevel by 1\advance\leftskip by .5in\reset
\aftergroup\afterstartlist}
\def\alph#1{\ifcase #1\or a\or b\or c\or d\or e\or f\or g\or h\or
i\or j\or k\or l\or m\or n\or o\or p\or q\or r\or
s\or t\or u\or v\or w\or x\or y\or z\fi}
\def\li#1\par{\medskip\penalty-100\item{\ifcase\indentlevel \number\itno.\or
\alph\itno)\else
(\number\itno)\fi
}%
#1\smallskip\advance\itno by 1\relax}
\def\ul{\bgroup\def\li##1\par{\item{$\bullet$} ##1\par}}
\let\endul\egroup
\def\hline{\noalign{\hrule}}
\let\impl\rightarrow
\newskip\tableskip
\tableskip=10pt plus 10pt
\def\endproof{\leavevmode\quad\vrule height 6pt width 6pt
depth 0pt\hskip\parfillskip\hbox{}{\parfillskip0pt\medskip}}
\def\lcm{\mathop{\rm lcm}}
\li Find the prime factorization of each of these integers.
{\startlist
\li 9072
$9072 = 2^4\cdot 3^4\cdot 7.$
\li 324
$324 = 2^2\cdot 3^4.$
\li 6!
$6! = 2^4\cdot 3^2\cdot 5.$
}
\li Approximate the number of prime numbers not exceeding 50000. Show
your work.
The approximate number of primes less than $N$ is $N/\ln(N)$
$${50000\over\ln(50000)} \approx {50000\over 10.82} \approx 4621.$$
\li Determine whether the integers 2, 51, 101, and 119 are pairwise
relatively prime. Show your work for full credit.
These are the prime factorizations of the above numbers:
$2 = 2.$
$51 = 3\cdot 17.$
$101 = 101.$
$119 = 7\cdot 17.$
$51$ and $119$ are not coprime because they share the factor 17.
Every other pair is relatively prime.
\li What is the greatest common divisors of these pairs of integers?
{\startlist
\li $2^4*3^3*5^6$ and $2^5*3^3*5^2*7^2.$
$2^4*3^3*5^2.$
\li 19 and $19^1 8.$
19.
}
\li What is the least common multiple of these pairs of integers?
{\startlist
\li $2^4*3^3*5^6$ and $2^5*3^3*5^2*7^2.$
$2^5*3^3*5^6*7^2.$
\li $2^4*7$ and $5^5*13.$
$2^4*5^5*7*13.$
}
\li Find the least integer with $n$ distinct positive factors where $n$
is below. For example, if $n=4,$ then the solution is $6$ because
$1,2,3,6$ are distinct positive factors of $6$ and there are $n=4$ of
them.
{\startlist
\li 3
$4$ has factors $1,2,4.$
\li 5
$16$ has factors $1,2,4,8,16.$
\li 6
$12$ has factors $1,2,3,4,6,12.$
}
\li Use the Euclidean algorithm to find the following values. You must
clearly show all steps of your work using the Euclidean algorithm taught
in class.
{\startlist
\li $\gcd(100,101)$
$(100,101)\to (100, 1)\to (1, 0),$ giving $\gcd(100,101) = 1.$
\li $\gcd(64, 12)$
$(64, 12)\to (12, 4)\to (4, 0),$ giving $\gcd(64,12) = 4.$
}
\li Show your work by using the Chinese Remainder Theorem, find all
values $x$ such that
$x \equiv 1 \pmod{5}.$
$x \equiv 2 \pmod{6}.$
$x \equiv 3 \pmod{7}.$
\smallskip
5, 6, and 7 are pairwise coprime, so these congruences specify a unique
integer $n$ such that $x\equiv n \pmod{210}.$
$y_1 = 42,$ and $a_1 = 1,$ so $z_1 = 3.$
$y_2 = 35,$ and $a_2 = 2,$ so $z_2 = 5.$
$y_3 = 30,$ and $a_3 = 3,$ so $z_3 = 4.$
$a_1y_1z_1 + a_2y_2z_2 + a_3y_3z_3 \equiv 206 \bmod{210}.$
\li Decrypt the following ciphertext message: $HJUXDW,$ which was
encrypted first using a shift cipher, then using a transposition cipher.
The key of the shift cipher was $k=3,$ and the transposition cipher was
based on the permutation $\sigma$ of the set 1, 2, 3 with $\sigma(1) =
2$ and $\sigma(2) = 3$ and $\sigma(3) = 1.$
We start by computing a transposition $\sigma^{-1}(3) = 2$ and
$\sigma^{-1}(2) = 1$ and $\sigma^{-1}(1) = 3.$
The ciphertext becomes $JUHDWX.$
We then convert the ciphertext to numbers
$(9, 20, 7, 3, 22, 23)$ and subtract three to get
$(6, 17, 4, 0, 19, 20),$ and finally convert numbers to letters,
obtaining $GREATU.$
\li Suppose you intercept the message ``57 04 00 59 50 57 04 14 52 50 57
42 00 54'' that has been encrypted using the RSA algorithm. You know
that the public key used for encryption is $(65,7).$ Decrypt the message
to determine what was said. Use the process shown in lecture to complete
this problem. You must show all work. (If your calculator is unable to
calculate $a^d\bmod{n}$ where a is one of the numbers in the message above and
$d$ is the decryption key, then you can just show $a^d\bmod{n}$ for each value of
a. Note that this is the final step in decryption so you won't show what
the message actually was. You must still show the work for calculating
the decryption key $d$).
$n = 13\cdot 5 = p\cdot q.$
$\lcm(p-1,q-1) = 12.$
$7\cdot 7 \equiv 1 \pmod{12},$
so $d = 7$ (the multiplicative inverse of 7 mod 12)
We then compute $a^d\bmod{n}$ for each number in the message, obtaining
$(8,4,0,19,15,8,4,14,13,15,8,3,0,24)$ or $IEATPIEONPIDAY.$
\bye
|
