|
June 23, 2004
A: FROM MENTOR DENISE HARBERT
IN IL
Hi Sanna! Here's an example that might make sense to the younger
GEM-SET
students. Breaking codes and computing digits in non-repeating
infinite
numbers like pi, e, and others are basically the same thing
as solving a math
problem. There are two main approaches to solving math problems:
1) the
step-by-step logical way ("proof") that most students
are taught in math
classes, or 2) the "brute force" way that student
member Sarah U-M described,
which means trying every possible answer until you find the
right one. For
example:
Problem: What is x in this equation: 2x + 5 = 18
Solution using approach 1:
a) subtract 5 from both sides of the = sign to get: 2x + 5
- 5 = 18 - 5, which
simplifies to 2x = 13
b) divide both sides by 2 to get: 2x/2 = 13/2, which simplifies
to x = 6.5
Solution using approach 2:
a) assume x = 0 and see if the equation works: 2(0) + 5 =
0 + 5 = 5, which is
less than 18, so try again
b) assume x = 1 and see if the equation works: 2(1) + 5 =
2 + 5 = 7, which is
less than 18, so try again
c) assume x = 2 and see if the equation works: 2(2) + 5 =
4 + 5 = 9, which is
less than 18, so try again
d) assume x = 3 and see if the equation works: 2(3) + 5 =
6 + 5 = 11, which is
less than 18, so try again
e) assume x = 4 and see if the equation works: 2(4) + 5 =
8 + 5 = 13, which is
less than 18, so try again
f) assume x = 5 and see if the equation works: 2(5) + 5 =
10 + 5 = 15, which
is less than 18, so try again
g) assume x = 6 and see if the equation works: 2(6) + 5 =
12 + 5 = 17, which
is less than 18, so try again
h) assume x = 7 and see if the equation works: 2(7) + 5 =
14 + 5 = 19, which
is greater than 18, so try again
i) Because x = 6 is too low and x = 7 is too high, the answer
must be
somewhere in between 6 and 7. Therefore, pick a number between
6 and 7 and
see if that works.
j) assume x = 6.4 and see if the equation works: 2(6.4) +
5 = 12.8 + 5 = 17.8,
which is less than 18, so try again
k) Because x = 6.4 is too low and x = 7 is too high, the answer
must be
somewhere in between 6.4 and 7. Therefore, pick a number between
6.4 and 7
and see if that works.
l) assume x = 6.5 and see if the equation works: 2(6.5) +
5 = 13 + 5 = 18,
which is equal to 18, so x = 6.5 is the answer!
Both of these approaches solved the problem. Which approach
was faster? For
a human, approach 1 is a lot faster. That is the way math
problems were
solved before computers. Which approach is faster for a computer?
Computers
don't "think" the way humans do. In order for a
computer to do approach 1,
you would have to program it to know when it should add, when
it should
subtract, when it should multiply, and when it should divide.
This is pretty
complex decision-making that is easy for a human but hard
for a computer.
However, approach 2 is easy for a computer because it is the
same type of
computation repeated in each step. The only difference between
steps is the
decision made after the computation. However, this one decision
is much
easier to program than the complex decisions that would be
needed in approach
1.
Computers can now do the "brute force" approach
2 very quickly and easily.
Computers today can be left on continuously and they can be
linked together in
networks. Any person connected to the internet can install
software to help
with the computations in various projects. Thus, computers
can be used while
the people who own them are not using them. Computer computations
may be
mathematically less complicated (or less creative) than the
computations a
human could make, but computers can make so many computations
so fast that
they can solve some problems with the "brute force"
method faster than humans
could solve the same problem using the "mathematical
logic" method. This is
especially true for problems with huge numbers of digits -
like computing pi
or finding prime numbers.
Student member Sarah U-M mentioned prime numbers. Computers
are now using the
"brute force" method to find huge prime numbers
that humans could never
compute by hand. The most famous project is the "Great
Internet Mersenne
Prime Search" (GIMPS). A prime number is a positive integer
greater than 1
that is divisible only by itself and 1. A Mersenne prime is
a prime number
that can be expressed as some power of 2 minus 1 (i.e., 2^p
– 1, where p is
a positive integer). The first three Mersenne prime numbers
are 3, 7, and 31.
The values of p that create these Mersenne primes are 2, 3,
5. That's
because:
2 to the 2nd power minus 1 = 2^2-1 = 2x2 - 1 = 4 - 1 = 3,
which is a prime
number
2 to the 3rd power minus 1 = 2^3-1 = 2x2x2 - 1 = 8 - 1 = 7,
which is a prime
number
2 to the 5th power minus 1 = 2^5-1 = 2x2x2x2x2 - 1 = 32 -
1 = 31, which is a
prime number
Right now, there are only 41 known Mersenne primes. The last
three Mersenne
primes were discovered by the GIMPS project:
39th known Mersenne prime discovered in November 2001:
2 to the 13,466,917th power minus 1, contains 4,053,946 digits
http://news.bbc.co.uk/1/hi/sci/tech/1693364.stm
40th known Mersenne prime discovered on November 17, 2003:
2 to the 20,996,011th power minus 1, contains 6,320,430 digits
http://www.newscientist.com/news/news.jsp?id=ns99994438
41st known Mersenne Prime discovered on May 15, 2004:
2 to the 24,036,583th power minus 1, contains 7,235,733 digits
http://www.mersenne.org/
Notice how 2 years separated the 39th and 40th prime "finds",
but only 6
months separate the 40th and 41st prime "finds".
This could be because of
increased participation in the GIMPS project, advancing technology
and
computer speeds, and/or the fact that the 40th and 41st primes
are closer
together than the 39th and 40th primes are!
********************
June 14, 2004
A: FROM STUDENT MEMBER SARAH U-M IN CA
All encryption algorithms require one or more "keys"--
user-inputted strings of data. Key length is usually
measured in bits (a bit is a single 1 or 0). The
larger the key length, the greater the number of
possible values for the key, called the "keyspace".
Every bit added doubles the keyspace.
The goal in creating an algorithm is to somehow make
it so no information can be deduced from the
ciphertext alone. (Kerckhoff's principle: "the
security of a cryptosystem should depend only on the
secrecy of the key.") Thus, the best way an enemy has
to decipher an intercepted message is to try every
key, one by one. This is known as a "brute-force
attack". The larger the keyspace in an ideal
cryptosystem, the longer a message will take to
decipher.
From a simplistic point of view, computers have simply
sped up the key-checking process. I'm more interested
in the mathematics than the history of
cryptography/cryptanalysis, but I believe the first
machines designed for breaking ciphers were the
"bombes" used by Turing and Welchman at Bletchley
Park
in WW II. I'll second Ms. Kane-- Alan Turing rocks....
I don't know too much about computing pi. I believe
the same result occurs: basically, computers make
calculating a lot faster. Google should have all you
need to know.
I could babble on about finding primes and the
difference between public and private keys for longer
than even the mentors would want to listen, so I'll
stop here. It's awesome that you're interested in
this: there are so few female crypto enthusiasts I
know of and none are my age. I'd love to chat sometime
with anyone who's interested. Check out sci.crypt for
a good time.
********************
June 11, 2004
A: FROM MENTOR LORI KANE IN
MA
Computers have brought us from ancient times, where ciphers
were as simple
as substituting one letter for another, to technology such
as the Enigma,
which was an electro-magnetic machine used by the Germans
in the second
World War, to the electronic forms we have today. Today we
mostly use two
kinds of encryption: public and private key cryptography (and
the key
systems that you've probably heard of: DES, RSA, etc.). This
technology
encrypts information using an algorithm that is computationally
difficult
to solve (within a practical amount of time) without having
the key.
One of the most important code breakers in history is Britain's
Alan
Turing. He is considered one of the founders of code breaking
and computer
science. Turing is most famous for cracking the Enigma cipher
machine
which greatly helped the Allies win the battle of the Atlantic
and
eventually the war. You can read about his fascinating life
and tragic end
on the following sites:
http://www.turing.org.uk/turing/
http://www.alanturing.net/turing_archive/
Here are other good sites for information on cryptography:
http://www.busan.edu/~nic/networking/puis/ch06_01.htm
http://www.vectorsite.net/ttcode.html
The Code Book by Simon Singh is also a great source on the
history of
cryptography (and can be found at most book stores).
...I'll have to let one of the other mentors talk about pattern
finding.
|
