C 503: Finding Large Primes

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.


C 503.1: Find the Next Prime (10 pts)

This number is not prime:

10**300

Find the first number above it which is prime. The flag is That number is the flag

The flag is that number as one long integer, like

11111111111111111111111111111111


C 503.2: Companion Primes (10 pts)

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

The flag is the lower of the two primes, as one long integer, like

11111111111111111111111111111111


Posted 11-1-17 by Sam Bowne
Added to Crypto Hero 4-16-18 6:26 am
Ported to new scoring engine 7-8-19