StŠr­frŠ­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.

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:
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)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


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.
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.

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.