# Les Nombres Premiers

- Soient \\(a, b \in \mathbb{Z}\\) avec \\(a \neq 0\\)
    - On dit que \\( a \\) **divise** \\( b \\) noté \\( a | b \\)
        - ssi \\( \exists c \in \mathbb{Z} b=ac \\)
        - On dit également que b est un multiple de a

## Propositions de division

- \\( \forall a, b, c, d \in \mathbb{Z}_ 0 \\) 
    a) \\( 1|a \\) 
    b) \\( a|0 \\) 
    c) \\( a|a \\) 
    d) \\( a|b \implies (\forall c \in \mathbb{Z}_ 0 \quad a|(b * c))\\) 
    e) \\( (a|b \land b|c) \implies a|c\\) 
    f) \\( (a|b \land a|c) \implies a | (b+c)\\) 
    g) \\( (a|b \land a|c) \implies a | (b-c)\\) 
    h) \\( (a|b \lor a|c) \implies a | (b * c)\\) 
    h) \\( (a|b \land c|d) \implies (a * c) | (b * d)\\) 


## Algorithme de division d'euclide

- Soient \\( a \in \mathbb{Z} \text{ et } d\in \mathbb{N} _ 0 \\)
    - \\( \exists q, r \in \mathbb{Z} \quad 0 \leq r < d \quad a = dq + r\\)
\mathbb{R}

- Soient \\( a, b \in \mathbb{Z} \quad n \in \mathbb{N} _ 0  \\)
    - On dit que \\( a \\) est **congru** à \\( b \\) modulo n
        - ssi \\( n \vert (a - b) \\)
            - On note \\( a \equiv_n b \\) 

## PGCD & PPCM

- **PGCD** : Plus grand commun diviseur
- **PPCM** : Plus petit commun multiple

On peut calculer le pgcd de deux nombre avec
\\[
    PGCD(a,b) = PGCD(b, a \bmod b)
\\]

On remarque que
\\[
    a * b = PGCD(a,b) * PPCM(a, b)
\\]

Donc si on fait la décomposition en facteur premier d'un nombre, on peut trouver le pgcd et le ppcm comme suit:

\\[
    a = p_1* ...* p_n * q_1* ...* q_n \\\\
    b = p_1* ...* p_n * \tilde{q}_ 1* ...* \tilde{q}_ n
\\]
\\[
    PGCD(a,b) = p_1 * ... * p_n \\\\
    PPCM(a,b) = p_1 * ... * p_n * q_1 * ... * q_n * \tilde{q}_ 1* ...* \tilde{q}_ n
\\]




## La Cryptographie

Lorsqu'un cannal de communication n'est pas sur, il faut crypter les messages.
Le message passe par une fonction pour crypter et une autre fonction pour décrypter. c'est un chiffrement asymetrique

On se base sur les mathématiques modulaires pour crypter

### Les nombres premiers

- Soit \\( p \in \mathbb{N} \\) On dit que \\( P \\) est un **Nombre Premier**
    - ssi il posséde exactement 2 diviseurs 
        - Ces diviseurs sont \\( 1 \text{ et } P \\)  

Un example d'algorithme naïf pour détecter un nombre premier est:
\\[ \forall n \in \mathbb{N}  2 \leq P \leq \sqrt{101} \implies n | 101 \\] 
On testerais ici par example \\( P | 101 \quad \forall P=2,3,5,7 \\) qui sont les racines < que 101

#### Une infinitée de nombre premiers

Nous pouvons prouver qu'il y a une infinitée de nombres premiers.
Pour se faire nous fesons une preuve par l'absurde : Il y a un nombre **fini** de nombres premiers.
mais si on prend \\( \displaystyle (\prod_1^n p_n)+1 \\) soit ce nombre est premier, soit il ne l'est pas.
Dans le cas où il ne le serait pas, alors on peut le décomposer en nombres premiers. sauf que cette formule indique qu'aucuns nombre premiers précédent celui-ci n'est dans la liste des nombres premiers
On aura donc une contradiction

En Cryptographie, l'infinitee de ces nombre premiers et la difficultée de trouver les facteurs premiers d'un grand nombre en fait un bon candidat pour des clés asymétriques

On peut utiliser également un [Algorithme d'exponensiation rapide](https://courses.cs.washington.edu/courses/cse311/21sp/resources/reference-modular-exponentiation.pdf)
