-
Looking back at the Class 27 Activity, you will find the + and
* tables for $\mathbb{Z}_{11}$. Using those:
- Evaluate $7*(5+4*4)-6$ in $\mathbb{Z}_{11}$
- Solve: $8*x - 3*(9*x + 2) = 0$ in $\mathbb{Z}_{11}$
-
Evaluate $9*3 + 9*8$ and $9*(3 + 8)$
in $\mathbb{Z}_{11}$, and verify that they give the same
answer. That should make you think that maybe the
distributive property does indeed hold in modular number
systems.
-
Look back at your notes for the inclass activity. You will
find that $2*2 = 0$ in $\mathbb{Z}_4$. In the integers, it is
impossible for two non-zero numbers to have a product of
zero. A proof of this is given in
Problem 1 of HW08.
Look at that proof (of the No-zero-divisors Theorem).
What is it in that proof that makes it
not apply (as it clearly doesn't!) to $\mathbb{Z}_n$?
Note: Obviously the theorem statement says "over the integers".
I'm asking what is it about the proof that makes it
not work for $\mathbb{Z}_n$?
- This problem has two parts:
- follow the gcd algorithm to compute gcd(57,21). Show
your work!
- Does 21 have a multiplicative inverse mod 57? How do
you know?
-
Referring to the
Class
29 in-class activity, I have encrypted a message
using our modular multiplication based scheme and encryption
key 12. The encrypted message is:
z.tfntybtzfjnfcxbz_fzdxw
What is the decrypted message? How did you use the two programs
I gave you in the in-class activity to find it?
-
Consider the following proof (a prose-style proof but with line numbers):
Let $a$ be an integer such that $2|a*a$, then $a$ is even.
1: $a*a$ is even, since $2|a*a$
2: assume by way of contradiction that $a$ is odd
3: then $a = 2*k + 1$
4: then $a*a = (2*k+1)*(2*k+1) = 4*k^2 + 4*k + 1 = 2*(2*k + 2) + 1$
5: so $a*a$ is odd
6: but Theorem 13 says no integer is both even and odd, so
7: contradiction between line 1 and line 5!
8: So the line 1 assumption must be false, and $a$ is even.
Give a full first-order logic proof to justify the first line. I.e.
prove that if we are given that $2|a*a$, then $a*a$ is even.
Note:
(Divisibility) of Class 25 and
(Even) of Class 23 are going to be important!
-
The "rational numbers" are all the numbers that can be expressed
as fractions. Usually we require the denominator to be positive
and the fraction to be in reduced form, in which case every
rational number has a unique representation as a fraction.
Occasionally mathematical thinking is rocked by a new result that
that is so unexpected that it changes the way mathematicians think.
This happened in the ancient greek world when someone proved that
sqrt(2) is not a rational number (i.e. that there exist lengths in
basic geometry that can't be expressed as fractions). Here is the
proof:
There is no $p/q$ such that $(p/q)*(p/q) = 2$. Note that we
can express this as: there are no integers $p,q$
where $q > 0$ and $\text{gcd}(p,q) = 1$
such that $p*p = 2*q*q$.
1: assume for contradiction that $p$,$q$ are integers such that
$q > 0$ and $\text{gcd}(p,q) = 1$ and $p*p = 2*q*q$
2: then p is even
(by above)
3: so p = 2*k
4: so 2*k*2*k = 2*q*q
5: so 2*k*k = q*q
6: so q is even
(by above)
7: so q = 2*k'
8: so 2 is a common divisor of p and q
9: contradiction!
Check every step of this proof. Is it valid? If not, where
is there a flaw?
- Extra credit Challenge!
Our Class 29 in-class activity used the following mapping
between characters and numbers in $\mathbb{Z}_{29}$:
The scheme from our in-class activity looked like this:
encryption key is $k_e$,
decryption key is $k_d$, the multiplicative inverse of $k_e \bmod
29$
$e(c)$, the encryption of character $c$, is ...
a. set $x =$ number representation of character $c$
b. set $y = k_e*x \bmod 29$
c. result is $c'$, the character represented by number
$y$ |
$d(c')$, the decryption of $c'$, is ...
a. set $y =$ number representation of character $c'$
b. set $x = k_d*y \bmod 29$
c. result is $c$ , the character represented by number $x$
|
So here is a new, better encryption method:
New Better: encryption key is $(k_{e1},k_{e2})$,
decryption key is ??? [I'm not going to tell you!]
$e(c)$, the encryption of character $c$, is ...
a. set $x =$ number representation of character $c$
b. set $y = (k_{e1}*x + k_{e2}) \bmod 29$
c. result is $c'$, the character represented by number
$y$ |
$d(c')$, the decryption of $c'$, is ...
I'm not going to tell you!
|
A message was encrypted using New Better with $(k_{e1},k_{e2}) = (19,6)$, which produced:
ajbyk.aypkyt.cyaagey
Your challenge: decrypt the message!
Hint:
Once you figure out how to decrypt one character, I would take
ex0.cpp from the
Class 29 in-class activity
and modify it to decrypt the whole challence message for you.
Message is: _______________________________________________________________________
-
Extra, extra credit Challenge!
A message was encrypted using New Better (from above), but we
don't know what key was used. We intercepted the encrypted
message and it was:
hema.ca.mdbna
Also, one of our spies found a mostly, but not completely, burnt piece of paper,
and based on that we suspect that the last two letters of the
original message were es.
Your challenge: decrypt the message!
Message is: _______________________________________________________________________