**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# Modular exponentiation

Summary

Modular exponentiation is exponentiation performed over a modulus. It is useful in computer science, especially in the field of public-key cryptography, where it is used in both Diffie-Hellman Key Exchange and RSA public/private keys.
Modular exponentiation is the remainder when an integer b (the base) is raised to the power e (the exponent), and divided by a positive integer m (the modulus); that is, c = be mod m. From the definition of division, it follows that 0 ≤ c < m.
For example, given b = 5, e = 3 and m = 13, dividing 53 = 125 by 13 leaves a remainder of c = 8.
Modular exponentiation can be performed with a negative exponent e by finding the modular multiplicative inverse d of b modulo m using the extended Euclidean algorithm. That is:
:c = b''e'' mod m = d−''e'' mod m, where e < 0 and b ⋅ d ≡ 1 (mod m).
Modular exponentiation is efficient to compute, even for very large integers. On the other hand, computing the modular discrete logarithm – that i

Official source

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

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related people

No results

Related units

No results

Related publications (6)

Loading

Loading

Loading

Related concepts (15)

Modular arithmetic

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic wa

Prime number

A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. F

RSA (cryptosystem)

RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem, one of the oldest, that is widely used for secure data transmission. The acronym "RSA" comes from the surnames of Ron Rivest, Adi Shamir and

Related courses (4)

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 as diverse as mathematical reasoning, combinatorics, discrete structures & algorithmic thinking.

MICRO-435: Quantum and nanocomputing

The course teaches non von-Neumann architectures. The first part of the course deals with quantum computing, sensing, and communications. The second focuses on field-coupled and conduction-based nanocomputing, in-memory and molecular computing, cellular automata, and spintronic computing.

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 they work and sketch how they can be implemented.

Related lectures (10)

In this paper we show that the Ate pairing, originally defined for elliptic curves, generalises to hyperelliptic curves and in fact to arbitrary algebraic curves. It has the following surprising properties: The loop length in Miller’s algorithm can be up to g times shorter than for the Tate pairing, with g the genus of the curve, and the pairing is automatically reduced, i.e. no final exponentiation is needed.

Recent attacks on standardised hash functions such as SHA1 have reawakened interest in design strategies based on techniques common in provable security. In presenting the VSH hash function, a design based on RSA-like modular exponentiation, the authors introduce VSH-DL, a design based on exponentiation in DLP-based groups. In this article we explore a variant of VSH-DL that is based on cyclotomic subgroups of finite fields; we show that one can trade-off performance against bandwidth by using known techniques in such groups. Further, we investigate a variant of VSH-DL based on elliptic curves and extract a tighter reduction to the underlying DLP in comparison to the original VSH-DL proposal

2006In this paper, we revisit the construction of fail-stop signatures from the factoring assumption. These signatures were originally proposed to provide information-theoretic-based security against forgeries. In contrast to classical signature schemes, in which signers are protected through a computational conjecture, fail-stop signature schemes protect the signers in an information theoretic sense, i.e., they guarantee that no one, regardless of its computational power, is able to forge a signature that cannot be detected and proven to be a forgery. Such a feature inherently introduced another threat: malicious signers who want to deny a legitimate signature. Many construction of fail-stop signatures were proposed in the literature, based on the discrete logarithm, the RSA, or the factoring assumptions. Several variants of this latter assumption were used to construct fail-sop signature schemes. Bleumer et al. (EuroCrypt ’90) proposed a fail-stop signature scheme based on the difficulty of factoring large integers and Susilo et al. (The Computer Journal, 2000) showed how to construct a fail-stop signature scheme from the so-called “strong factorization” assumption. A later attempt by Schmidt-Samoa (ICICS ’04) was to propose a fail-stop signature scheme from the p2q factoring assumption. Compared to those proposals, we take a more traditional approach by considering the Rabin function as our starting point. We generalize this function to a new bundling homomorphism while retaining Rabin’s efficient reduction to factoring the modulus of the multiplicative group. Moreover, we preserve the efficiency of the Rabin function as our scheme only requires two, very optimized, modular exponentiations for key generation and verification. This improves on older constructions from factoring assumptions which required either two unoptimized or four exponentiations for key generation and either two unoptimized or three modular exponentiations for verifying.