# CSci 1901: Lab 2, January 25

### Lab 2: Writing Procedures

#### Step 1 (Drill)

Write a procedure that takes in 4 arguments and returns the smallest argument. You may NOT use the builtin `min` procedure, though you may feel free to use it in all future labs.

```STk> (min-of-4 1 3 5 6)
1
STk> (min-of-4 9 0 21 -2)
-2
STk> (min-of-4 2 2 2 5)
2
```

2 points

#### Step 2 (Drill)

Write a procedure, `sum-func`, that takes in three numeric arguments and returns the sum of the largest two arguments divided by the third argument.

```STk> (sum-func 8 6 2)
7
STk> (sum-func 3 5 4)
3
STk> (sum-func 9 9 9)
2
```

3 points

#### Step 3 (Drill)

Complete Exercise 1.8 from the textbook. The code for using Newton's method to iteratively compute square roots is given in the textbook in Section 1.1.7. You may modify the existing code for square roots or do this exercise from scratch, this is your choice.

```STk> (cube-root 8)
2.0000049116755
STk> (cube-root 27)
3.00000054106418
STk> (cube-root 3.375)
1.50000111249087
STk> (cube-root 0.015625)
0.251206551211726
```

2 points

The following two questions will have you write two predicates that we will be using next week to preform RSA encryption and decryption.

#### Step 4 (Application - RSA Encryption)

Write a predicate (a procedure that returns `#t` or `#f`) `relatively-prime?` that takes in two numbers and determines if they are relatively prime. Two numbers are relatively prime if the greatest common divisor of those two numbers is one.

```STk> (relatively-prime? 2 3)
#t
STk> (relatively-prime? 24 26)
#f
STk> (relatively-prime? 8 9)
#t
STk> (relatively-prime? 11 22)
#f
```

You may make use of the following procedure, `gcd`, from the book which determines the greatest common divisor of two numbers using Euclid's algorithm.

```(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
```

1 point

#### Step 5 (Application - RSA Encryption)

Write a predicate which takes in three numbers and determines if the first two numbers are the inverse of each other modulo the third number. Two numbers, say `a` and `b` are the inverse of each other modulo some number `c` if ```a*b mod c = 1```. For this problem you may make use the builtin in procedure `(remainder p m)` which computes ```p mod m```.

```STk> (modulo-inverse? 3 4 11)
#t
STk> (modulo-inverse? 3 4 13)
#f
STk> (modulo-inverse? 342 453 30985)
#t
STk> (modulo-inverse? 342 454 30985)
#f
```

2 points

#### Bonus Question (RSA Encryption)

Next week you will write some procedures for preforming RSA encryption, a very common encryption and decryption method. It will not be necessary to understand that mathematics behind RSA encryption, but understanding the math will make the lab more interesting. For this bonus question read through the following description of RSA encryption and answer the following questions:
• RSA encryption involves 4 numbers, namely P,Q,D, and E. P and Q must be prime. E must be odd and must satisfy two additional conditions, what are these conditions?
• What is the one condition that the number D must satisfy?
• Use this dictionary, that associates words with a numeric value, to find the encoding for the word "abstract". This is the number T described in the above link.
• Use the value for T that you just found to find the encrypted cipher text (called C) for "abstract". Use the following RSA values - P = 61, Q = 53, E = 17, and D= 2753. You will need to make use of the function `(expmod a b c)` from the book which efficiently computes the value `a^b mod c`
```(define (square x) (* x x))

(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (square (expmod base (/ exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
```
• Use `expmod` to verify that the cipher text you found above decrypts properly back to the numeric encoding for abstract.

Congratulations on completing Lab 2!
Lab 2 point total: 10 pts

#### This is what you will learn in this lab

• get familiar with writing simple scheme programs;
• understand how to write nested procedures;
• understand the difference between procedures and predicates;
• understand the beginning of RSA encryption (more next week).