README.md

This repository contains the python codes written for the University of Colorado-Boulder class CSCI3104: Algorithms, Fall of 2013.

A description of functions:

• avgDist2Prime:
  • computes avg. numerical distance from nSamp numbers \in {0,10^101 - 1} to the next prime number. calls both nextprime and getrand100
• avgPcntDist2Prime:
  • same as avgDist2Prime, but computes fractional distance to next prime
• badRSADecrypter:
  • demonstrates the calculation of the decryption key for an encrypter using N=p rather than N=p*q
• euclidsExtended:
  • computes gcds and inverses using Euclid's Extended Algorithm
• getrand100:
  • produces a random 100 digit decimal number
• linear_fibonacci:
  • computes the nth fibonacci number in linear time
• modExp:
  • a modular exponentiation function, called as modExp(a, b, N), computing a^b mod N
• nextprime:
  • finds the nextprime number after the input number. calls primeTest
• primeTest:
  • tests for primality using the converse of Fermat's little theorem to a default likelihood > 1-2^(-100). calls modExp
• selection:
  • finds the kth element of the sorted list from an input, unsorted list
• selection2:
  • same as selection, but also returns number of recursive calls needed to find kth element
• smallest3numPprime:
  • finds the smallest number that is simultaneously a pseudoprime to the 3 input numbers. calls smallestPseudoprime
• smallestPseudoprime:
  • finds the smallest pseudoprime to the input
• snakeEyesMonteCarlo:
  • finds the number of random rie rolls necessary to get snakeEyes, averaging over the number of iterations input by the user. calls snakeEyesRoller
• snakeEyesRoller:
  • rolls dice until snake eyes is rolled, returns number of rolls to achieve snake eyes