Assignment #2: Modular Arithmetic, Random Sequences, and Primes

For this assignment, you will submit a single Python source file `a2.py`.

Your file may not import any modules or employ any external library functions associated with integers and sets (unless the problem statement explicitly permits this). You will be graded on the correctness, concision, and mathematical legibility of your code. The different problems and problem parts rely on each other; carefully consider whether you can use functions you define in one part within subsequent parts.

1. To receive credit for each part below, your solutions must employ `forall`, `exists`, and/or list comprehensions. Solutions that are more than 2-5 lines in length will receive no credit.

1. Define a Python function `commutative(op,S)` that takes two arguments and returns `True` only if the first argument `op`, an operator that takes two arguments, is commutative on the finite set `S`.
```def commutative(op,S) :
return forall(S, lambda x: forall(S, lambda y: op(x,y) == op(y,x)))```
2. Define a Python function `associative(op,S)` that takes two arguments and returns `True` only if the first argument `op`, an operator that takes two arguments, is associative on the finite set `S`.
```def associative(op,S) :
return\
forall(S, lambda x: forall(S, lambda y: forall(S, lambda z:\
op(op(x,y),z) == op(x,op(y,z)))))```
3. Define a Python function `identity(op,S)` that takes two arguments and returns `True` only if the first argument `op` (which is itself a function that takes two arguments) has an identity element in `S`. Note that the identity must be both a left and right identity.
```# It is important to have the right order for the quantifiers.
# There must exist at least one identity element that behaves
# like the identity for /all/ the elements of S:
#
#   exists i in S s.t. for all x in S, op(x,i) == op(i,x) == x
#
# Notice that this is different from a statement such as the one
# below:
#
#   for all x in S, exists i in S s.t. op(x,i) == op(i,x) == x # Incorrect.
#

def identity(op,S) :
return exists(S, lambda i: forall(S, lambda x: op(x,i) == op(i,x) == x))```
4. Define a Python function `inverses(op,S)` that takes two arguments and returns `True` only if for every element in `S`, there is an inverse element with respect to `op`. Note that this is only possible if there is an identity with respect to `op`. You may want to write a few helper functions in order to avoid deeply-nested quantifiers.
```# The following is the correct formula:
#
#   there exists i in S s.t.
#       i is an identity for S
#     and
#       for all x in S, exists y in S s.t. op(x,y) == i
#
# However, equivalents of the following will also be
# accepted:
#
#   for all x in S, exists y in S s.t.
#     op(x,y) == i and i is an identity for S
#
# For either of the above, "i is an identity for S" should
# be a formula equivalent to:
#
#   for all x in S, op(x,i) == op(i,x) == x
#
# Since we did not explicitly specify whether the identity
# must be left- or right-, "op(x,i) == x" or "x == op(x,i)"
# alone would be sufficient.

def inverses(op,S) :
return\
exists(S, lambda i:\
#i is an identity
forall(S, lambda x: op(i,x) == op(x,i) == x)\
and\
forall(S, lambda x: exists(S, lambda y: op(x,y) == i)))```
1. Define a Python function `randFromPrime()` that takes a single input `p`, a prime number, and generates a set of `p` distinct lists, each of length `p`, and each being a "random" reording of the list `[ i for i in range(0,p) ]`.
• Each list must contain `p` distinct integers from the set `{ i for i in range(0,p) }`.
• No individual list should be an ascending or descending sequence of the integers from `{ i for i in range(0,p) }`.
2. Define a Python function `rand()` that takes a single input `n` (which might not be prime) and generates a set of `n` distinct lists, each of length `n`, and each being a "random" reording of the list `[ i for i in range(0,n) ]`.
• Each list must contain `n` distinct integers from the set `{ i for i in range(0,n) }`.
• No individual list should be an ascending or descending sequence of the integers from `{ i for i in range(0,n) }`.
You may find the following points useful:
• Implement the gcd function.
• Recall the fact that if gcd(a,m) = 1, then {(i, (ia) mod m) | i {0,...,m-1}} is a permutation. Implement an algorithm that finds a suitable a quickly for a given m (think about how you can use the gcd function to accomplish this).
• Python provides a built-in function `floor()`. To use it, add ```from math import floor``` to the top of your file.
3. Extra credit: Define a Python function `randExtra()` that takes a single input `n` (which might not be prime) and generates a set of `n*n` distinct lists, each of length `n`, and each being a "random" reording of the list `[ i for i in range(0,n) ]`.
• Each list must contain `n` distinct integers from the set `{ i for i in range(0,n) }`.
• No individual list should be an ascending or descending sequence of the integers from `{ i for i in range(0,n) }`.
1. Define a Python function `randByIndex()` that takes two inputs `n` and `i`. It should return the `i`th element in a "random" sequence of length `n` that contains every number in the set `{ k for k in range(0,n) }`. You should not generate the whole list of length `n` in memory.
1. Define a Python function `generatePrime()` that takes a single input `d` and generates a d-digit (in base 10) probable prime. Your algorithm should be efficient enough to fairly quickly generate a 1000-digit probable prime, and should not run out of memory (although it may take quite some time) when generating a 10000-digit probable prime.
• Make use of your solution from Problem #3 above.
• Define a separate helper function `probablePrime()` that checks if its input is a probable prime.
• Python provides a built-in function `pow(a,b,m)` that efficiently computes ab mod m.
• For the purposes of this assignment, you need not handle Carmichael numbers in any special way that avoids the high likelihood that they are categorized as probably prime. Thus, you may use the Fermat primality test.