# Proj X4: Finding Large Primes (20 pts. extra credit)

What you need:
## Purpose

To implement the Fermat primality test and find large primes.

## Background

Fermat's little theorem states that if p is prime and a is not divisible by p, then:
So testing that condition for several random values of a
can be used as evidence that p is probably prime.

This site explains the Fermat primality test and its flaws in more detail:

https://en.wikipedia.org/wiki/Fermat_primality_test

## Simple Python Implementation

from random import randint
p = int(raw_input("Input potential prime: "))
for i in range(5):
a = randint(2,p-2)
if pow(a, p-1, p) == 1:
print "Test passed for ", a
else:
print "Test failed for ", a

## Demonstration

Try these values: 11, 13, 100, 121.
As shown below,
11 and 13 pass all the tests
because they are prime, but
100 and 121 fail because they aren't.

## Testing Large Numbers

Test this number, which is 1024 bits long, and is prime:
149893897637335061961928327350470188799927663887947357440069371232471599832948115772987524239902313942376737764843434513577954709550540438646101225413150283056505892203493267823497754444007029293809481459043218629633809451460944629963616409822735245271280411960104440928839926847578561621781631648006307217641

It works, because Python really can handle any size of integer,
as shown below.

## Challenge 1: Find the Next Prime (10 pts. extra credit)

This number is not prime:
10**300

Find the first number above it which is prime.

Use the form
below to put your name on the
**WINNERS PAGE**.

Save a whole-screen image of the winners page showing your name,
as shown below,
with the filename "**YOUR NAME Proj 4x1**".

## Challenge 2: Companion Primes (10 pts. extra credit)

11 and 13 are both primes, only differing by two. Such primes are
called *companion primes*.
Find the first set of companion primes above

10**100

Use the form
below to put your name on the
**WINNERS PAGE**.

Save a whole-screen image of the winners page showing your name,
as shown below,
with the filename "**YOUR NAME Proj 4x2**".

## Turning in your Project

Email the images
to **cnit.141@gmail.com** with the subject line:
**Proj X4 from YOUR NAME**.

Posted 11-1-17 by Sam Bowne