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

• Any computer with Python 2.7. If you are using a Mac or Linux machine, Python is already installed. If you are using Windows, follow these instructions to install Python 2.7.

Purpose

Background

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

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

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)

10**300

Find the first number above it which is prime.

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

Your Name (without spaces): Answer, as one long integer, like 11111111111111111111111111111111 :

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

Find the first set of companion primes above

10**100

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

Your Name (without spaces): The lower of the two primes, as one long integer, like 11111111111111111111111111111111 :

Turning in your Project