Stærðfræðimynstur í tölvunarfræði

Weekly note 9

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.

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 x_n+1 = (ax_n + 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?

RSA

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)₁₆. 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

• 104281735391995426127780900927647529412754004160490656811749030991653345899311
  eða (00 E68D 5EDF 3416 FF31 D5FC 22D5 2E24 26DC 5141 8733 85D4 18C7 AA7E 1368 3D23 332F)₁₆
• 171337256407249794293897175609924994722989505938960696638848588549637707305419
  eða (01 7ACD 7355 13A8 5617 B44C 69EA 00DD 8870 54C4 08AF 6E02 CEDA 268E D44E 7E3A 91CB)₁₆

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!

Hip

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.