Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Montgomery Multiplication

In course

MATH-489: Number theory II.d - Cryptography

. ...

Description

This lecture covers the concept of Montgomery multiplication, focusing on Barrett reduction and the Montgomery form of integers. The instructor explains the rationale behind using larger k's for large numbers and the need for multi-precision floats. The lecture also delves into Montgomery exponentiation and the efficient computation of the Montgomery product.

Instructor

Dimitar Petkov Jetchev

Official source

Related concepts (32)

Integer

An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language of mathematics, the set of integers is often denoted by the boldface Z or blackboard bold . The set of natural numbers is a subset of , which in turn is a subset of the set of all rational numbers , itself a subset of the real numbers . Like the natural numbers, is countably infinite.

Integer overflow

In computer programming, an integer overflow occurs when an arithmetic operation attempts to create a numeric value that is outside of the range that can be represented with a given number of digits – either higher than the maximum or lower than the minimum representable value. The most common result of an overflow is that the least significant representable digits of the result are stored; the result is said to wrap around the maximum (i.e. modulo a power of the radix, usually two in modern computers, but sometimes ten or another radix).

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 was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801. A familiar use of modular arithmetic is in the 12-hour clock, in which the day is divided into two 12-hour periods. If the time is 7:00 now, then 8 hours later it will be 3:00.

Floating-point arithmetic

In computing, floating-point arithmetic (FP) is arithmetic that represents subsets of real numbers using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. Numbers of this form are called floating-point numbers. For example, 12.345 is a floating-point number in base ten with five digits of precision: However, unlike 12.345, 12.3456 is not a floating-point number in base ten with five digits of precision—it needs six digits of precision; the nearest floating-point number with only five digits is 12.

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.

Related lectures (39)

Elementary Algebra: Numeric Sets

Explores elementary algebra concepts related to numeric sets and prime numbers, including unique factorization and properties.

Computer Arithmetic: Floating Point Operations

Covers the basics of computer arithmetic, focusing on floating point numbers and their operations.

Computer Arithmetic (Integers)

Covers binary representation, two's complement, overflow detection, and operations in MIPS for computer arithmetic with integers.

Exponentiation

Covers exponentiation, RSA encryption, big integer multiplication, and primitive roots.

Integer Representation: Positive Integers