Stable Marriages

The stable marriage problem is another classic appreciation of discrete mathematics to social networks. 

Suppose that you have been hired to be a matchmaker with n men and n woman who wish to be paired up with their perfect matches. Each man provides the matchmaker with a list of the woman ranking from first choice to last choice, as same for the woman. 

The matchmakers job is to provide a way to pair up the n men and n women in such a way so no man or woman is left behind. 

The stable marriage theorem states that your job can always be accomplished, no matter how the men and women have ranked one another. This theorem provides an algorithm that accomplishes your task. 

In round 1: every man proposes to his first choice. those woman who receives the offers tentatively accept the best offer and tell the other men not to come back. The rejected men then propose to their next choice, and the women then tentatively accept the best offer they have so far received and tell the other proposers to go away. This process continues until every man and woman are paired up. 

Example One: Suppose the matchmaker receives the following list: 

man 1 (3,1,4,2,5)

man 2 (1,3,5,2,4) 

man 3 (5,4,3,2,1)

man 4 (1,5,4,2,3)

man 5 (3.4.5.1.2)

woman 1 (3,5,1,4,2) 

woman 2 (3,1,2,4,5)

woman 3 (1,2,3,4,5)

woman 4 (5,3,1,2,4)

woman 5 (5,4,3,2,1)

 Use the stable marriage algorithm to find a stable parring. 

Answer: Men 1,2,3,4 and 5 will propose to women 3,1,5, 1, and 3 respectively. Woman 1 rejects man 2, woman 3 rejects man 5. So then men 2 and 5 propose to women 3 and 4 respectively, but man 2 is rejected again because woman 3 is already taken. Man 2 now continues to move down his list to woman number 5, who accepts him and rejects man number 3. Now man 3 proposes to woman 3, who rejects him. Then man 3 proposes to woman 2 who accepts his offer. WIth no man or woman unattached, the algorithm terminates with stable pairings: 

man 1 with woman 3, man 2 with woman 5, man 3 with woman 2, man 4 with woman 1, and man 5 with woman 4. 

Examine Question: Suppose the matchmaker receives the following list: 

man 1 (c, a, d, b, e)

man 2 (a, c, e, b, d) 

man 3 (e, d, c, b, a) 

man 4 (a, e, d, c, b)

man 5 (c, d, e, b, a)

woman a (3,1,2,4,5)

woman b (3, 5, 1, 4, 2)

woman c (5,3,1,2,4)

woman d (1,2,3,4,5)

woman e (5,4,3,2,1)

A. Use the stable marriage algorithm to find a solution pairing. (men proposes to women)

B. Find another stable marriage obtained by having the women propose to the men. 

RSA Method of Cryptography

RSA: is a crypt o-system, which is known as one of the first practicable public-key crypt o-systems and is widely used for secured data transmission. This method was named after three mathematically trained computer sciences, Ronald Riverst, Aid Shamer, and Lenorad Adleman, who discovered this method in 1977.

In the crypt o-system the encryption key is public and differs from the decryption key which is kept a secret. 

How it works: The bank publishes two numbers on its website, n and e (as in encipher), n and e are about 2000 digits long. 

1, Write your plain text should be under 1000 characters

for example: quiz today   

2. Convert your plain text to a number m (under 2000 digits) by replacing each letter with its 2-digit position in the alphabet

for example: 172109262015040125

3. Computer cipher text C=M raised to the e power mod n. Your the one emailing the C to the bank. 

4. When the bank receives your C, it uses a magic secret number d ( as its decipher) and computes C raised to the d mod n, which equals M. Then it converts M back to your plain text. 

The Encryption: An example of this is: if Brittany transmits her public key (n,e) to Billy and keeps the private key secret. Billy then wishes to send message M to Brittany. He first turns M into an integer m, such that 0 ≤ m < n by using an agreed protocol of the system. he then computes the cipher text c 

corresponding to , then Billy transmits c to Alice. 

The Decryption: Brittany can recover m from c by using her private key exponent d from the formula 

. Given m, she can recover the original message M.

Example One: Compute the following RSA method where p=5 and q=29. Find e and f, and also d to figure out what the value of M will be? 

To find the value of n we multiply p by q. 

so since p=5 and q=29 so (p)(q)=145. 

Now we need to find (n)

(145) = 4 x 28 = 112

We pick d=3 and then find e and f so that 

ed + (n) f =1

3 e + 112 f  =1

3(-37) + 112(1) =1

so e = -37

Now we send the message to M=2. 

The sent message is 

.

Exam Question: Compute the following RSA method where p=3 and q =7. Find e, f. and d to figure out what value M with encryption and decryption? 

Citations: Wikipedia and Our Math notes