Discrete maths

Identifying primes

Identifying primes

different to factorising. We don’t care what the actual factors are, just see if it’s prime

Fermat’s primality test

Fermat’s little theorem recap

Fermat’s primality test

From Fermat’s little theorem we know

\(a^{n-1}=1 mod(n)\)

Where \(a\) is an integer and \(n\) is prime.

Integer factorisationn

Trial division

We have x

Divide by numbers between 2 and x

Only need to go to sqrt x

Don’t need to divide by even numbers other than 2

algorithm for checking if number is a prime

loop up dividing number from 2

if divides, add factor list and divide target number by that

stop when i reaches number

eg for 45

divide 2? no

divide 3? yes :> 15

divide 3? yes :> 5

divide 4? no

divide 5? yes :> 1

6>1 so stop

number is prime if list just contains target

don’t have to worry about including non primes in list, as will already have divded by that amount

Fermat’s method

Identify the integer as the difference of two squares, and use this.

\(x=a.b\)

We use the midpoint of the two as \(c=\dfrac{a+b}{2}\)

This only works for odd numbers. If we have

The we have:

  • \(a=c+d\)

  • \(b=c-d\)

  • \(x=(c+d)(c-d)\)

  • \(x=c^2-d^2\)

We can test this by trying \(a\) to get \(a^2-x\), and seeing if this is a square number.