Cryptography math questions

Here are two (simplified) versions of Roulette. Compute the probabilities of losing in each.
(a) Las Vegas roulette. There are 38 (uniformly random) outcomes: two green numbers 0 and 00, and 36 red and black numbers 1 to36 (half red, half black). You bet on a red or black color (say red). You then win if you get a red number, and lose if you get a non-red number. What’s the probability that you lose?
(b) Monte-Carlo roulette. There are 37 (again, uniformly random) outcomes: 0 is green, and 36 red and black numbers 1 to 36(again half red, half black). You bet on a red or black color (say red). You then win if you get a red number, and lose if you get a black number. If you get the green 0, you get a special reroll, where if you get a red then you get your money back (so you don’t win but don’t lose either), but you lose if you get a green or black on the reroll. What is your probability of losing?
Then, comment on the values themselves.
Suppose you have 15 people coming together to form a committee of5 people. 6 out of 15 of the people are spies. What’s the probability that at least half of the committee are spies?
True or false? (Warning: as in all my problems, you need to explain your answers to get any credit.)(a) (Z/6Z)∗ has a primitive root. (b) (Z/13Z)∗ has a generator. (c) (Z/15Z)∗ has a generator.
Similar to Di?e-Hellman, here’s the ?Zhang key-exchange?:? We pick a big prime p and a generator g.? Alice has a secret a ∈ Z/(p − 1)Z. 1
? Bobhasasecretb∈Z/(p−1)Z.
? Alice sends ga to Bob. Bob sends gb to Alice.
(a) Show that a key is indeed exchanged; that is, Alice and Bob can both compute g−a−b (mod p).
(b) Show that this key-exchange is very bad compared to Die-Hellman.
How fast (big O notation is enough) can you check if two lists of nintegers each has at least one integer in common? (hint: sorting a list of n integers ? meaning putting them in order, takes O(n log(n)) time with the best algorithms we have).
Suppose g is a generator for (Z/nZ)∗. Show that if x+y = 0 (mod φ(n)), then gx and gy are inverses (of each other). Is the converse of this state- ment true?