Prime Number

Un nombre premier est un entier naturel supérieur à 1 divisible uniquement par 1 et par lui-même ; c'est la brique élémentaire de la théorie des nombres, et tout entier se décompose de façon unique en facteurs premiers.

Objectif

Servir de briques élémentaires des entiers, fondement de la théorie des nombres et de la cryptographie (RSA).

Mécanisme

Un entier naturel supérieur à 1 dont les seuls diviseurs sont 1 et lui-même. Théorème fondamental de l'arithmétique : tout entier se décompose de façon unique en nombres premiers. Tests de primalité : division par essais, Miller-Rabin (probabiliste), AKS (déterministe mais lent). Il existe une infinité de premiers (preuve d'Euclide).

Cas d’usage

Génération de clés RSA
Paramètres Diffie-Hellman
Capacités premières de tables de hachage
Recherche en théorie des nombres

Exemples

entrée

The first 10 primes

Output

2,3,5,7,11,13,17,19,23,29

2 is the only even prime

Erreurs courantes

Using small primes for RSA moduli: Use large primes (≥1024 bits)

Termes associés

Modular Arithmetic

L'arithmétique modulaire prend les restes après les opérations entières, en gardant les résultats dans [0, n) ; c'est le fondement de la théorie des nombres et de la cryptographie.

BigInteger est un type d'entier à précision arbitraire, non limité par une taille de mot fixe, utilisé pour des calculs au-delà de la plage des entiers natifs (comme la cryptographie et la combinatoire).

Le PGCD (plus grand commun diviseur) est le plus grand entier positif qui divise deux entiers ou plus, calculé efficacement par l'algorithme d'Euclide.

Outils associés

Générateur d'octets aléatoires

Generate cryptographically secure random bytes or integers. Gratuit, privé et 100% côté client.

Factorisation de Fermat

Fermat Factorization — outil 100% côté client. Confidentialité d'abord, sans aller-retour serveur.

References