# 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.