Summary
In mathematics, particularly in the area of arithmetic, a modular multiplicative inverse of an integer a is an integer x such that the product ax is congruent to 1 with respect to the modulus m. In the standard notation of modular arithmetic this congruence is written as which is the shorthand way of writing the statement that m divides (evenly) the quantity ax − 1, or, put another way, the remainder after dividing ax by the integer m is 1. If a does have an inverse modulo m, then there are an infinite number of solutions of this congruence, which form a congruence class with respect to this modulus. Furthermore, any integer that is congruent to a (i.e., in a's congruence class) has any element of x's congruence class as a modular multiplicative inverse. Using the notation of to indicate the congruence class containing w, this can be expressed by saying that the modulo multiplicative inverse of the congruence class is the congruence class such that: where the symbol denotes the multiplication of equivalence classes modulo m. Written in this way, the analogy with the usual concept of a multiplicative inverse in the set of rational or real numbers is clearly represented, replacing the numbers by congruence classes and altering the binary operation appropriately. As with the analogous operation on the real numbers, a fundamental use of this operation is in solving, when possible, linear congruences of the form Finding modular multiplicative inverses also has practical applications in the field of cryptography, i.e. public-key cryptography and the RSA algorithm. A benefit for the computer implementation of these applications is that there exists a very fast algorithm (the extended Euclidean algorithm) that can be used for the calculation of modular multiplicative inverses. Modular arithmetic For a given positive integer m, two integers, a and b, are said to be congruent modulo m if m divides their difference. This binary relation is denoted by, This is an equivalence relation on the set of integers, Z, and the equivalence classes are called congruence classes modulo m or residue classes modulo m.
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related courses (6)
COM-102: Advanced information, computation, communication II
Text, sound, and images are examples of information sources stored in our computers and/or communicated over the Internet. How do we measure, compress, and protect the informatin they contain?
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-489: Number theory II.c - Cryptography
The goal of the course is to introduce basic notions from public key cryptography (PKC) as well as basic number-theoretic methods and algorithms for cryptanalysis of protocols and schemes based on PKC
Show more
Related lectures (37)
Quantum Random Number Generation
Explores quantum random number generation, discussing the challenges and implementations of generating good randomness using quantum devices.
Modular Arithmetic: Inverses and Equations
Explores modular arithmetic, emphasizing inverses and equations in Z/mZ, with practical examples and exercises.
Euclidean Algorithm: Extended and Applications
Explores the Euclidean Algorithm, its extension, and applications in number theory.
Show more
Related publications (44)

An Optimized Low-Power Band-Tuning TX for Short-Range FMCW Radar in 22-nm FDSOI CMOS

Christian Enz, Francesco Chicco, Sammy Cerida Rengifo

The paper presents a low-power transmitter (TX) as a part of a fully integrated 57-66 GHz FMCW radar system. The TX path includes a BPSK modulator and it is optimized for short-range operation with 0 dBm output power. A band-tuning technique is used for co ...
IEEE2021

Arithmetic and geometric structures in cryptography

Benjamin Pierre Charles Wesolowski

We explore a few algebraic and geometric structures, through certain questions posed by modern cryptography. We focus on the cases of discrete logarithms in finite fields of small characteristic, the structure of isogeny graphs of ordinary abelian varietie ...
EPFL2018

Building Security Protocols Against Powerful Adversaries

Iris Safaka

As our sensitive data is increasingly carried over the Internet and stored remotely, security in communications becomes a fundamental requirement. Yet, today's security practices are designed around assumptions the validity of which is being challenged. In ...
EPFL2016
Show more
Related concepts (16)
Modulo
In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the modulus of the operation). Given two positive numbers a and n, a modulo n (often abbreviated as a mod n) is the remainder of the Euclidean division of a by n, where a is the dividend and n is the divisor. For example, the expression "5 mod 2" would evaluate to 1, because 5 divided by 2 has a quotient of 2 and a remainder of 1, while "9 mod 3" would evaluate to 0, because 9 divided by 3 has a quotient of 3 and a remainder of 0; there is nothing to subtract from 9 after multiplying 3 times 3.
Cryptography
Cryptography, or cryptology (from κρυπτός "hidden, secret"; and γράφειν graphein, "to write", or -λογία -logia, "study", respectively), is the practice and study of techniques for secure communication in the presence of adversarial behavior. More generally, cryptography is about constructing and analyzing protocols that prevent third parties or the public from reading private messages. Modern cryptography exists at the intersection of the disciplines of mathematics, computer science, information security, electrical engineering, digital signal processing, physics, and others.
Finite field arithmetic
In mathematics, finite field arithmetic is arithmetic in a finite field (a field containing a finite number of elements) contrary to arithmetic in a field with an infinite number of elements, like the field of rational numbers. There are infinitely many different finite fields. Their number of elements is necessarily of the form pn where p is a prime number and n is a positive integer, and two finite fields of the same size are isomorphic.
Show more