StŠrfrŠimynstur Ý t÷lvunarfrŠi
Weekly note 9
This week we will finish discussing the Pascal's triangle from section 4.4. We will then
briefly look at probability from section 5.1. After that we will start with relations
in Chapter 7. We will skip all of Chapter 6.
Next week we will continue with relations in Chapter 7.
This week you do not have to hand in any homework, but you work on some interesting
projects. You do not have to hand in these projects, but we will evaluate the
projects that are turned in and select the 3-4 best ones. The students
whose projects get selected will get as a prize the grade 10 for all older
homework (i.e. homework 1 thru 8).
Below are the projects. Pick one of them to do and present your solution in such a
way the we can put your solution on the Web page of the course in case it is selected.
You can for instance hand it in as a Word document or as a interactive Web page.
The deadline for turing in the projects in to noon on monday October 31st and you are
to turn them in to me. You can choose whether to send
them in email or put them in my box in VR-II.
- Linear Congruential Method
- As you may recall the linear congruential method (LCM) is one of the ways we can generate
pseudo random numbers. The method uses the formula xn+1 = (axn + c) mod m.
Not all values of a, c, and m give a method with a full period (i.e. all values from
0 to m-1 appear as random numbers). Look at this choice of the parameters a, cand m,
and pay particular attention to the following points:
- If we wanted to have a random number generator that produces 8 bit numbers, is it possible to find values for a
and c that will giva a full period if we fix m as 256? How about 16 bit numbers (i.e. m = 65536)?
- Look at the random number generator in Java (i.e. the class Random) and convince yourselves that it has full period.
- What about the randomness of the generator? Are there different values of a, c, and m that produce
different amounts of randomness?
- The RSA public key cryptography method is based on the difficulty of factoring integers. Here
you get a public key (n, e) with some message that has been coded with it. You are to find
the original message by first finding the private key (n, d) from the public one and use it
to decode the message.
The key that you get is (221873272483254945141922353186910788703120217007463592538956281140602541064561, 65537). Here n is
the 257-bit number and e is 65537. Here you have n in hexadecimal format:
(01 EA87 D26D AE2B B5E4 DC33 6EE0 D994 DB82 FE49 F895 5D80 0E36 6B76 722C 1016 4171)16.
Since n is 257 bits (i.e. just over 32 bytes) then we can code 32 characters in one number that is lower than n
if we concatenate the ASCII codes of the characters. The message that you are to try to find is coded with two 257-bit numbers.
Thus, it is between 33 and 64 characters in length. The numbers are
(00 E68D 5EDF 3416 FF31 D5FC 22D5 2E24 26DC 5141 8733 85D4 18C7 AA7E 1368 3D23 332F)16
(01 7ACD 7355 13A8 5617 B44C 69EA 00DD 8870 54C4 08AF 6E02 CEDA 268E D44E 7E3A 91CB)16
So that you will know if you are on the right track the message starts with: "N˙ ...". Thus the first
three letters are 'N' (78), '˙' (250) and ' ' (32). Hand in a description of the method that you used
to crack the method, with the solution.
Note that currently people use 1024-bit keys (i.e. the size of n) in RSA, and those that want more
security use 2048-bit keys. You should therefore have no problem in breaking a 257-bit key!
- The game Hip is played on a NxN board where
N is an odd number. Initially the board is empty, and the players take turns placing their stones. One player
has white stones, the other black ones. The goal of the game is to avoid having 4 stones of the same color
forming a square on the board. The square does not thave to be parallel to the sides of the board. I could
have any angle (see some pictures of squares).
You are to analyse the game and write a report on what you find out.
- Calculate the number of possible squares on a NxN board.
- Look at the cases N=5 and N=7. Is there an optimal way to play for either player
that guarantees him/her victory?
- How many possible moves are there (e.g. for N=5 and N=7)?
- What does the game tree (see also pages 651-656 in the
textbook) look like (at least the first few levels)?
In the sections next week (Nov. 1.-2.) you are to try to solve selected problems from
material covered so far in the course. The teachers will go between students and help out,
but will not teach in the normal way. You do not have to show up for these sections,
but it is important for those who have missed out on some material or want to see where
they stand to take this opportunity
The problems to be solved in next weeks sections will be give out later.
hh (hja) hi.is, 24. oktˇber, 2005.