Community hub
Recent from talks
Contribute something to knowledge base
Content stats: 0 posts, 0 articles, 0 media, 0 notes
Members stats: 0 subscribers, 0 contributors, 0 moderators, 0 supporters
Subscribers
Supporters
Contributors
Moderators
Hub AI
Modular exponentiation AI simulator
(@Modular exponentiation_simulator)
Hub AI
Modular exponentiation AI simulator
(@Modular exponentiation_simulator)
Modular exponentiation
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.
When b and m are relatively prime, one can also allow the exponent e to be negative by finding the multiplicative inverse d of b modulo m (for instance by using extended Euclidean algorithm). More precisely:
Modular exponentiation is efficient to compute, even for very large integers. On the other hand, computing the modular discrete logarithm – that is, finding the exponent e when given b, c, and m – is believed to be difficult. This one-way function behavior makes modular exponentiation a candidate for use in cryptographic algorithms.
The most direct method of calculating a modular exponent is to calculate be directly, then to take this number modulo m. Consider trying to compute c, given b = 4, e = 13, and m = 497:
One could use a calculator to compute 413; this comes out to 67,108,864. Taking this value modulo 497, the answer c is determined to be 445.
Note that b is only one digit in length and that e is only two digits in length, but the value be is eight digits in length.
Modular exponentiation
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.
When b and m are relatively prime, one can also allow the exponent e to be negative by finding the multiplicative inverse d of b modulo m (for instance by using extended Euclidean algorithm). More precisely:
Modular exponentiation is efficient to compute, even for very large integers. On the other hand, computing the modular discrete logarithm – that is, finding the exponent e when given b, c, and m – is believed to be difficult. This one-way function behavior makes modular exponentiation a candidate for use in cryptographic algorithms.
The most direct method of calculating a modular exponent is to calculate be directly, then to take this number modulo m. Consider trying to compute c, given b = 4, e = 13, and m = 497:
One could use a calculator to compute 413; this comes out to 67,108,864. Taking this value modulo 497, the answer c is determined to be 445.
Note that b is only one digit in length and that e is only two digits in length, but the value be is eight digits in length.