**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Multiplicative group of integers modulo n

Summary

In modular arithmetic, the integers coprime (relatively prime) to n from the set of n non-negative integers form a group under multiplication modulo n, called the multiplicative group of integers modulo n. Equivalently, the elements of this group can be thought of as the congruence classes, also known as residues modulo n, that are coprime to n.
Hence another name is the group of primitive residue classes modulo n.
In the theory of rings, a branch of abstract algebra, it is described as the group of units of the ring of integers modulo n. Here units refers to elements with a multiplicative inverse, which, in this ring, are exactly those coprime to n.
This quotient group, usually denoted , is fundamental in number theory. It is used in cryptography, integer factorization, and primality testing. It is an abelian, finite group whose order is given by Euler's totient function: For prime n the group is cyclic, and in general the structure is easy to describe, but no simple general formula for finding generators is known.
It is a straightforward exercise to show that, under multiplication, the set of congruence classes modulo n that are coprime to n satisfy the axioms for an abelian group.
Indeed, a is coprime to n if and only if gcd(a, n) = 1. Integers in the same congruence class a ≡ b (mod n) satisfy gcd(a, n) = gcd(b, n), hence one is coprime to n if and only if the other is. Thus the notion of congruence classes modulo n that are coprime to n is well-defined.
Since gcd(a, n) = 1 and gcd(b, n) = 1 implies gcd(ab, n) = 1, the set of classes coprime to n is closed under multiplication.
Integer multiplication respects the congruence classes, that is, a ≡ a' and b ≡ b' (mod n) implies ab ≡ a'b' (mod n).
This implies that the multiplication is associative, commutative, and that the class of 1 is the unique multiplicative identity.
Finally, given a, the multiplicative inverse of a modulo n is an integer x satisfying ax ≡ 1 (mod n).
It exists precisely when a is coprime to n, because in that case gcd(a, n) = 1 and by Bézout's lemma there are integers x and y satisfying ax + ny = 1.

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 publications (1)

Related concepts (36)

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?

COM-401: Cryptography and security

This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how

EE-611: Linear system theory

The course covers control theory and design for linear time-invariant systems : (i) Mathematical descriptions of systems (ii) Multivariables realizations; (iii) Stability ; (iv) Controllability and Ob

Direct product of groups

In mathematics, specifically in group theory, the direct product is an operation that takes two groups G and H and constructs a new group, usually denoted G × H. This operation is the group-theoretic analogue of the Cartesian product of sets and is one of several important notions of direct product in mathematics. In the context of abelian groups, the direct product is sometimes referred to as the direct sum, and is denoted .

Euler's theorem

In number theory, Euler's theorem (also known as the Fermat–Euler theorem or Euler's totient theorem) states that, if n and a are coprime positive integers, and is Euler's totient function, then a raised to the power is congruent to 1 modulo n; that is In 1736, Leonhard Euler published a proof of Fermat's little theorem (stated by Fermat without proof), which is the restriction of Euler's theorem to the case where n is a prime number.

Multiplicative order

In number theory, given a positive integer n and an integer a coprime to n, the multiplicative order of a modulo n is the smallest positive integer k such that . In other words, the multiplicative order of a modulo n is the order of a in the multiplicative group of the units in the ring of the integers modulo n. The order of a modulo n is sometimes written as . The powers of 4 modulo 7 are as follows: The smallest positive integer k such that 4k ≡ 1 (mod 7) is 3, so the order of 4 (mod 7) is 3.

We consider several "provably secure" hash functions that compute simple sums in a well chosen group (G,*). Security properties of such functions provably translate in a natural way to computational problems in G that are simple to define and possibly also hard to solve. Given k disjoint lists Li of group elements, the k-sum problem asks for gi ∊ Li such that g1 * g2 *...* gk = 1G. Hardness of the problem in the respective groups follows from some "standard" assumptions used in public-key cryptology such as hardness of integer factoring, discrete logarithms, lattice reduction and syndrome decoding. We point out evidence that the k-sum problem may even be harder than the above problems. Two hash functions based on the group k-sum problem, SWIFFTX and FSB, were submitted to NIST as candidates for the future SHA-3 standard. Both submissions were supported by some sort of a security proof. We show that the assessment of security levels provided in the proposals is not related to the proofs included. The main claims on security are supported exclusively by considerations about available attacks. By introducing "second-order" bounds on bounds on security, we expose the limits of such an approach to provable security. A problem with the way security is quantified does not necessarily mean a problem with security itself. Although FSB does have a history of failures, recent versions of the two above functions have resisted cryptanalytic efforts well. This evidence, as well as the several connections to more standard problems, suggests that the k-sum problem in some groups may be considered hard on its own, and possibly lead to provable bounds on security. Complexity of the non-trivial tree algorithm is becoming a standard tool for measuring the associated hardness. We propose modifications to the multiplicative Very Smooth Hash and derive security from multiplicative k-sums in contrast to the original reductions that related to factoring or discrete logarithms. Although the original reductions remain valid, we measure security in a new, more aggressive way. This allows us to relax the parameters and hash faster. We obtain a function that is only three times slower compared to SHA-256 and is estimated to offer at least equivalent collision resistance. The speed can be doubled by the use of a special modulus, such a modified function is supported exclusively by the hardness of multiplicative k-sums modulo a power of two. Our efforts culminate in a new multiplicative k-sum function in finite fields that further generalizes the design of Very Smooth Hash. In contrast to the previous variants, the memory requirements of the new function are negligible. The fastest instance of the function expected to offer 128-bit collision resistance runs at 24 cycles per byte on an Intel Core i7 processor and approaches the 17.4 figure of SHA-256. The new functions proposed in this thesis do not provably achieve a usual security property such as preimage or collision resistance from a well-established assumption. They do however enjoy unconditional provable separation of inputs that collide. Changes in input that are small with respect to a well defined measure never lead to identical output in the compression function.

Related lectures (73)

Characters: Linear Algebraic GroupsMATH-479: Linear algebraic groups

Introduces characters as group homomorphisms from linear algebraic groups to multiplicative groups.