Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Multiplication de Montgomery

Dans cours

MATH-489: Number theory II.d - Cryptography

. ...

Description

Cette séance de cours couvre le concept de multiplication de Montgomery, en mettant l'accent sur la réduction de Barrett et la forme Montgomery des entiers. L'instructeur explique la raison d'être de l'utilisation de k plus gros pour les grands nombres et le besoin de flotteurs multi-précisions. La séance de cours se penche également sur l'exposition de Montgomery et le calcul efficace du produit de Montgomery.

Enseignant·e

Dimitar Petkov Jetchev

Source officielle

Concepts associés (32)

Entier relatif

En mathématiques, un entier relatif, un entier rationnel ou simplement un nombre entier est un nombre qui se présente comme un entier naturel auquel on a adjoint un signe positif ou négatif indiquant sa position par rapport à 0 sur un axe orienté. Les entiers positifs (supérieurs à zéro) s'identifient aux entiers naturels : 0, 1, 2, 3... tandis que les entiers négatifs sont leurs opposés : 0, −1, −2, −3... L'entier 0 lui-même est donc le seul nombre à la fois positif et négatif.

Dépassement d'entier

vignette|Le vol 501 d'Ariane 5 en 1996 s'est soldé par sa destruction en raison d'un dépassement d'entier. Un dépassement d'entier (integer overflow) est, en informatique, une condition qui se produit lorsqu'une opération mathématique produit une valeur numérique supérieure à celle représentable dans l'espace de stockage disponible. Par exemple, l'ajout d'une unité au plus grand nombre pouvant être représenté entraîne un dépassement d'entier. Le dépassement d'entier porte le numéro CWE-190 dans la nomenclature Common Weakness Enumeration.

Arithmétique modulaire

En mathématiques et plus précisément en théorie algébrique des nombres, l’arithmétique modulaire est un ensemble de méthodes permettant la résolution de problèmes sur les nombres entiers. Ces méthodes dérivent de l’étude du reste obtenu par une division euclidienne. L'idée de base de l'arithmétique modulaire est de travailler non sur les nombres eux-mêmes, mais sur les restes de leur division par quelque chose. Quand on fait par exemple une preuve par neuf à l'école primaire, on effectue un peu d'arithmétique modulaire sans le savoir : le diviseur est alors le nombre 9.

Virgule flottante

vignette|Comme la notation scientifique, le nombre à virgule flottante a une mantisse et un exposant. La virgule flottante est une méthode d'écriture de nombres fréquemment utilisée dans les ordinateurs, équivalente à la notation scientifique en numération binaire. Elle consiste à représenter un nombre par : un signe (égal à −1 ou 1) ; une mantisse (aussi appelée significande) ; et un exposant (entier relatif, généralement borné).

Exponentiation modulaire

En mathématiques, plus précisément en arithmétique modulaire, l’exponentiation modulaire est un type d'élévation à la puissance (exponentiation) réalisée sur des entiers modulo un entier. Elle est particulièrement utilisée en informatique, spécialement dans le domaine de la cryptologie. Etant donnés une base b, un exposant e et un entier non nul m, l'exponentiation modulaire consiste à calculer c tel que : Par exemple, si b = 5, e = 3, et m = 13, le calcul de c donne 8.

Afficher plus

Séances de cours associées (39)

Algèbre élémentaire: ensembles numériques

Explore les concepts d'algèbre élémentaire liés aux ensembles numériques et aux nombres premiers, y compris la factorisation et les propriétés uniques.

Arithmétique de l'ordinateur: Opérations de points flottants

Couvre les bases de l'arithmétique informatique, en se concentrant sur les nombres de points flottants et leurs opérations.

Ordinateur arithmétique (entiers)

Couvre la représentation binaire, le complément de deux, la détection de débordement, et les opérations en MIPS pour l'arithmétique informatique avec entiers.

Exposentiation

Couvre exponentiation, chiffrement RSA, grande multiplication entière, et racines primitives.

Représentation entière : nombres entiers positifs

Couvre la représentation des entiers positifs, la notation binaire, les limitations de la machine, le débordement et la représentation des points flottants.

Afficher plus

Concepts associés (32)

Entier relatif

Dépassement d'entier

Arithmétique modulaire

Virgule flottante

Exponentiation modulaire

Afficher plus