Python 3.6

Main packages used:

• random
• math
• time (for evaluation)
• matplotlib.pyplot (for evaluation plotting)
• sys (for input and output on Kattis)

fraction.py:

In this python file we wrote definitions for all the algorithms as following:

• miller_rabin: implementation of Miller Rabin algorithm to judge prime numbers
• brent: implementation of Pollard's Rho algorithm with Brent for factorization
• pollard: implementation of Pollard's Rho algorithm for factorization
• extract: a sub-function for trial division
• trivial_div: implementation of trial division algorithm

And the last part of "for" loop is for input and output on Kattis.

prime_table.py:

In this python file we generate the prime table for trial division in fraction.py.

evalution.py:

In this python file we wrote the evaluation function for pollard and brent algorithms and it generates a figure for the report.