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