Résumé
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. Calculer l'exponentiation modulaire est considéré comme facile, même lorsque les nombres en jeu sont énormes. Au contraire, calculer le logarithme discret (trouver e à partir de b, c et m) est reconnu comme difficile. Ce comportement de fonction à sens unique fait de l'exponentiation modulaire une bonne candidate pour être utilisée dans les algorithmes de cryptologie. Le calcul naïf de l'exponentielle modulaire est le suivant : on multiplie e fois le nombre b par lui-même, et une fois l'entier be obtenu, on calcule son reste modulo m via l'algorithme de division euclidienne. Cette méthode souffre de deux défauts : d'une part, le nombre de multiplications peut facilement être réduit, par la méthode générale d'exponentiation rapide : il n'y aura plus que log(e) multiplications à effectuer. d'autre part, on ne profite pas de la structure d'anneau commutatif du domaine dans lequel on travaille : les entiers modulo m. Or, cette structure autorise que les calculs soient faits directement dans cet anneau, sans passage au préalable par les entiers. Pour mettre en œuvre cette idée, il faut en pratique, à chaque nouvelle multiplication effectuée, calculer un nouveau reste modulo m. On rajoute ainsi de nouvelles opérations (pour chaque multiplication, une division euclidienne), mais on gagne par ailleurs du fait que la taille des données à manipuler est limitée par celle de m. La suite de l'article décrit ces différentes adaptations et discute leur efficacité en fonction notamment de la taille des données.
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Cours associés (5)
CS-101: Advanced information, computation, communication I
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
MATH-417: Number theory II.b - selected topics
This year's topic is "Adelic Number Theory" or how the language of adeles and ideles and harmonic analysis on the corresponding spaces can be used to revisit classical questions in algebraic number th
MATH-521: Advanced analytic number theory
We will present the work of James Maynard (MF 2022) on the existence of bounded gaps between primes
Afficher plus
Séances de cours associées (33)
Génération de nombres aléatoires quantiques
Explore la génération de nombres quantiques aléatoires, en discutant des défis et des implémentations de générer une bonne randomité à l'aide de dispositifs quantiques.
Fenêtre d'exposition
Explore l'exponentiation de fenêtre avec la représentation de base-B et les petites puissances précalculées de x pour un calcul efficace.
Afficher plus
Publications associées (30)

SIMToolbox: a MATLAB toolbox for structured illumination fluorescence microscopy

Tomas Lukes

SIMToolbox is an open-source, modular set of functions for MATLAB equipped with a user-friendly graphical interface and designed for processing two-dimensional and three-dimensional data acquired by structured illumination microscopy (SIM). Both optical se ...
Oxford University Press2016

Colloidal Nanocrystal Frameworks

Raffaella Buonsanti

A review. Colloidal nanocrystal frameworks (CNFs) are a modular class of mesostructured porous materials, which are assembled from pre-formed nanocrystal building units using suitably designed block copolymer architecture-directing agents. The functional a ...
2015

A Fast Modular Method for True Variation-Aware Separatrix Tracing in Nanoscaled SRAMs

Adam Shmuel Teman

As memory density continues to grow in modern systems, accurate analysis of SRAM stability is increasingly important to ensure high yields. Traditional static noise margin metrics fail to capture the dynamic characteristics of SRAM behavior, leading to exp ...
Institute of Electrical and Electronics Engineers2015
Afficher plus
Personnes associées (2)
Concepts associés (12)
Modulo (opération)
En informatique, l'opération modulo, ou opération mod, est une opération binaire qui associe à deux entiers naturels le reste de la division euclidienne du premier par le second, le reste de la division de a par n (n ≠ 0) est noté a mod n (a % n dans certains langages informatiques). Ainsi 9 mod 4 = 1, car 9 = 2×4 + 1 et 0 ≤ 1 < 4, 9 mod 3 = 0, ... L'opération peut être étendue aux entiers relatifs, voire aux nombres réels, mais alors les langages de programmation peuvent diverger, en particulier a mod n n'est plus forcément positif ou nul.
Suite de Lucas
En mathématiques, les suites de Lucas U(P, Q) et V(P, Q) associées à deux entiers P et Q sont deux suites récurrentes linéaires d'ordre 2 à valeurs entières qui généralisent respectivement la suite de Fibonacci et celle de Fibonacci-Lucas, correspondant aux valeurs P = 1 et Q = –1. Elles doivent leur nom au mathématicien français Édouard Lucas. Soient P et Q deux entiers non nuls tels que (pour éviter les cas dégénérés). Les suites de Lucas U(P, Q) et V(P, Q) sont définies par les relations de récurrence linéaire et Notons l'une des deux racines carrées de Δ (éventuellement dans C).
Inverse modulaire
En mathématiques et plus précisément en arithmétique modulaire, l'inverse modulaire d'un entier relatif pour la multiplication modulo est un entier satisfaisant l'équation : En d'autres termes, il s'agit de l'inverse dans l'anneau des entiers modulo n, noté Z/nZ ou Z. Une fois ainsi défini, peut être noté , étant entendu implicitement que l'inversion est modulaire et se fait modulo . La définition est donc équivalente à : L'inverse de a modulo existe si et seulement si et sont premiers entre eux, (c.-à-d.
Afficher plus