Assignment #2: Modular Arithmetic, Random Sequences, and Primes (back to full lecture notes)

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