Cryptographic algorithms | Modular arithmetic | Computer arithmetic

Montgomery modular multiplication

In modular arithmetic computation, Montgomery modular multiplication, more commonly referred to as Montgomery multiplication, is a method for performing fast modular multiplication. It was introduced in 1985 by the American mathematician Peter L. Montgomery. Montgomery modular multiplication relies on a special representation of numbers called Montgomery form. The algorithm uses the Montgomery forms of a and b to efficiently compute the Montgomery form of ab mod N. The efficiency comes from avoiding expensive division operations. Classical modular multiplication reduces the double-width product ab using division by N and keeping only the remainder. This division requires quotient digit estimation and correction. The Montgomery form, in contrast, depends on a constant R > N which is coprime to N, and the only division necessary in Montgomery multiplication is division by R. The constant R can be chosen so that division by R is easy, significantly improving the speed of the algorithm. In practice, R is always a power of two, since division by powers of two can be implemented by bit shifting. The need to convert a and b into Montgomery form and their product out of Montgomery form means that computing a single product by Montgomery multiplication is slower than the conventional or Barrett reduction algorithms. However, when performing many multiplications in a row, as in modular exponentiation, intermediate results can be left in Montgomery form. Then the initial and final conversions become a negligible fraction of the overall computation. Many important cryptosystems such as RSA and Diffie–Hellman key exchange are based on arithmetic operations modulo a large odd number, and for these cryptosystems, computations using Montgomery multiplication with R a power of two are faster than the available alternatives. (Wikipedia).

Video thumbnail

Modular Forms | Modular Forms; Section 1 2

We define modular forms, and borrow an idea from representation theory to construct some examples. My Twitter: https://twitter.com/KristapsBalodi3 Fourier Theory (0:00) Definition of Modular Forms (8:02) In Search of Modularity (11:38) The Eisenstein Series (18:25)

From playlist Modular Forms

Video thumbnail

Modular forms: Eisenstein series

This lecture is part of an online graduate course on modular forms. We give two ways of looking at modular forms: as functions of lattices in C, or as invariant forms. We use this to give two different ways of constructing Eisenstein series. For the other lectures in the course see http

From playlist Modular forms

Video thumbnail

Modular forms: Introduction

This lecture is part of an online graduate course on modular forms. We introduce modular forms, and give several examples of how they were used to solve problems in apparently unrelated areas of mathematics. I will not be following any particular book, but if anyone wants a suggestion

From playlist Modular forms

Video thumbnail

Jon Keating: Random matrices, integrability, and number theory - Lecture 3

Abstract: I will give an overview of connections between Random Matrix Theory and Number Theory, in particular connections with the theory of the Riemann zeta-function and zeta functions defined in function fields. I will then discuss recent developments in which integrability plays an imp

From playlist Analysis and its Applications

Video thumbnail

23C3: How to implement bignum arithmetic

Speaker: Felix von Leitner A short look at my pet project implementation Assembly language skills are a bonus, but not strictly required. This lecture will explain how software like OpenSSL and GnuPG do their arithmetic on 1024 bit numbers. This is not about how RSA works, or about how

From playlist 23C3: Who can you trust

Video thumbnail

Number Theory | Modular Inverses: Example

We give an example of calculating inverses modulo n using two separate strategies.

From playlist Modular Arithmetic and Linear Congruences

Video thumbnail

Discrete Math - 4.1.2 Modular Arithmetic

Introduction to modular arithmetic including several proofs of theorems along with some computation. Textbook: Rosen, Discrete Mathematics and Its Applications, 7e Playlist: https://www.youtube.com/playlist?list=PLl-gb0E4MII28GykmtuBXNUNoej-vY5Rz

From playlist Discrete Math I (Entire Course)

Video thumbnail

How 2 multiply Day 3

Broadcasted live on Twitch -- Watch live at https://www.twitch.tv/simuleios

From playlist Misc

Video thumbnail

The Wreck of the S.S. Richard Montgomery

The History Guy remembers why we should not forget the wreck of one of the last Liberty Ships, the S.S. Richard Montgomery. The question of what to do about it, and its load of explosives, remains today. This episode was made for educational purposes. The events are portrayed within the c

From playlist US History

Video thumbnail

Jon Keating: Random matrices, integrability, and number theory - Lecture 2

Abstract: I will give an overview of connections between Random Matrix Theory and Number Theory, in particular connections with the theory of the Riemann zeta-function and zeta functions defined in function fields. I will then discuss recent developments in which integrability plays an imp

From playlist Analysis and its Applications

Video thumbnail

CTNT 2018 - "Elliptic curves over finite fields" (Lecture 4) by Erik Wallace

This is lecture 4 of a mini-course on "Elliptic curves over finite fields", taught by Erik Wallace, during CTNT 2018, the Connecticut Summer School in Number Theory. For more information about CTNT and other resources and notes, see https://ctnt-summer.math.uconn.edu/

From playlist CTNT 2018 - "Elliptic Curves over Finite Fields" by Erik Wallace

Video thumbnail

Random Matrix Theory and Zeta Functions - Peter Sarnak

Random Matrix Theory and Zeta Functions - Peter Sarnak Peter Sarnak Institute for Advanced Study; Faculty, School of Mathematics February 4, 2014 We review some of the connections, established and expected between random matrix theory and Zeta functions. We also discuss briefly some recen

From playlist Mathematics

Video thumbnail

Peter Sarnak - Zeta and L-functions [ICM 1998]

ICM Berlin Videos 27.08.1998 Zeta and L-functions Peter Sarnak Princeton University, USA: Number Theory Thu 27-Aug-98 · 11:45-12:45 h Abstract: The theory of zeta and L-functions is at the center of a number of recent developments in number theory. We will review some of these developm

From playlist Number Theory

Video thumbnail

Geodesic Random Line Processes and the Roots of Quadratic Congruences by Jens Marklof

PROGRAM : ERGODIC THEORY AND DYNAMICAL SYSTEMS (HYBRID) ORGANIZERS : C. S. Aravinda (TIFR-CAM, Bengaluru), Anish Ghosh (TIFR, Mumbai) and Riddhi Shah (JNU, New Delhi) DATE : 05 December 2022 to 16 December 2022 VENUE : Ramanujan Lecture Hall and Online The programme will have an emphasis

From playlist Ergodic Theory and Dynamical Systems 2022

Video thumbnail

14B Complex Number Multiplication

The multiplication of scalar numbers.

From playlist Linear Algebra

Video thumbnail

Lattice Multiplication - Whole Number Multiplication

This video explains how to use the method of lattice multiplication to multiply whole numbers. Library: http://www.mathispower4u.com Search: http://www.mathispower4u.wordpress.com

From playlist Multiplication and Division of Whole Numbers

Video thumbnail

Kiran Kedlaya, The Sato-Tate conjecture and its generalizations

VaNTAGe seminar on March 24, 2020 License: CC-BY-NC-SA Closed captions provided by Jun Bo Lau.

From playlist The Sato-Tate conjecture for abelian varieties

Video thumbnail

Modular forms: Classification

This lecture is part of an online graduate course on modular forms. We first show that the number of zeros of a (level 1 holomorphic) modular form in a fundamental domain is weight/12, and use this to show that the graded ring of modular forms is the ring of polynomials in E4 and E6. Fo

From playlist Modular forms

Related pages

Euclidean division | Quotient ring | Extended Euclidean algorithm | Bézout's identity | Jacobi symbol | Side-channel attack | Carry-save adder | Exponentiation by squaring | Hensel's lemma | Modular exponentiation | Peter Montgomery (mathematician) | Barrett reduction | Diffie–Hellman key exchange | Modular arithmetic | RSA (cryptosystem) | Isomorphism