Kochanski multiplication

Modular arithmetic | Cryptographic algorithms

Kochanski multiplication is an algorithm that allows modular arithmetic (multiplication or operations based on it, such as exponentiation) to be performed efficiently when the modulus is large (typically several hundred bits). This has particular application in number theory and in cryptography: for example, in the RSA cryptosystem and Diffie–Hellman key exchange. The most common way of implementing large-integer multiplication in hardware is to express the multiplier in binary and enumerate its bits, one bit at a time, starting with the most significant bit, perform the following operations on an accumulator: 1. * Double the contents of the accumulator (if the accumulator stores numbers in binary, as is usually the case, this is a simple "shift left" that requires no actual computation). 2. * If the current bit of the multiplier is 1, add the multiplicand into the accumulator; if it is 0, do nothing. For an n-bit multiplier, this will take n clock cycles (where each cycle does either a shift or a shift-and-add). To convert this into an algorithm for modular multiplication, with a modulus r, it is necessary to subtract r conditionally at each stage: 1. * Double the contents of the accumulator. 2. * If the result is greater than or equal to r, subtract r. (Equivalently, subtract r from the accumulator and store the result back into the accumulator if and only if it is non-negative). 3. * If the current bit of the multiplier is 1, add the multiplicand into the accumulator; if it is 0, do nothing. 4. * If the result of the addition is greater than or equal to r, subtract r. If no addition took place, do nothing. This algorithm works. However, it is critically dependent on the speed of addition. Addition of long integers suffers from the problem that carries have to be propagated from right to left and the final result is not known until this process has been completed. Carry propagation can be speeded up with carry look-ahead logic, but this still makes addition very much slower than it needs to be (for 512-bit addition, addition with carry look-ahead is 32 times slower than addition without carries at all). Non-modular multiplication can make use of carry-save adders, which save time by storing the carries from each digit position and using them later: for example, by computing 111111111111+000000000010 as 111111111121 instead of waiting for the carry to propagate through the whole number to yield the true binary value 1000000000001. That final propagation still has to be done to yield a binary result but this only needs to be done once at the very end of the multiplication. Unfortunately the modular multiplication method outlined above needs to know the magnitude of the accumulated value at every step, in order to decide whether to subtract r: for example, if it needs to know whether the value in the accumulator is greater than 1000000000000, the carry-save representation 111111111121 is useless and needs to be converted to its true binary value for the comparison to be made. It therefore seems that one can have either the speed of carry-save or modular multiplication, but not both. (Wikipedia).

Matrix Multiplication

This is the second video of a series from the Worldwide Center of Mathematics explaining the basics of matrices. This video deals with multiplying two matrices. For more math videos, visit our channel or go to www.centerofmath.org

From playlist Basics: Matrices

Multiplication by 1/2

From playlist Transformations of the Number Line

Multiplication by -3

From playlist Transformations of the Number Line

Multiplication by -3

From playlist Transformations of the Number Line

Matrix Multiplication

This video explains how to multiply matrices. http://mathispower4u.yolasite.com/ http://mathispower4u.wordpress.com/

From playlist Matrices

Complex Multiplication by (cos(72) + isin(72))

From playlist Complex Multiplication

Matrix multiplication

Matrix multiplication. How to multiply matrices. In this video I show you how we define the multiplication of matrices. As you will see, it is not so simply as multiplying two numbers. Matrices can only be multiplied when the number of columns in the first matrix is similar to the numb

From playlist Introducing linear algebra

Matrix Addition, Subtraction, and Scalar Multiplication

This video shows how to add, subtract and perform scalar multiplication with matrices. http://mathispower4u.yolasite.com/ http://mathispower4u.wordpress.com/

From playlist Introduction to Matrices and Matrix Operations

Complex Power: (cos(-72) + isin(-72))^5

From playlist Complex Multiplication

Algebraic Proof - A-level Mathematics

In this video I explain how to solve the following problems: 1. Prove that the square of any natural number is either a multiple of 3 or 1 more than a multiple of 3. [4 marks] 2. Given that a and b are natural numbers, prove that a^2+b^2 is only a multiple of 3 if both a and b ar

From playlist A-level Mathematics Revision

What Is The LCM? (How to Find The Lowest Common Multiple)

Learn how to find the LCM - Lowest Common Multiple. For more in-depth math help check out my catalog of courses. Every course includes over 275 videos of easy to follow and understand math instruction, with fully explained practice problems and printable worksheets, review notes and quizz

From playlist GED Prep Videos

Definition of a Ring and Examples of Rings

Please Subscribe here, thank you!!! https://goo.gl/JQ8Nys Definition of a Ring and Examples of Rings - Definition of a Ring. - Definition of a commutative ring and a ring with identity. - Examples of Rings include: Z, Q, R, C under regular addition and multiplication The Ring of all n x

From playlist Abstract Algebra

Squaring Primes - Numberphile

Matt Parker is squaring primes. The Great Courses Plus free trial: http://ow.ly/JE3G30hIvoE (episode sponsor) More links & stuff in full description below ↓↓↓ More Matt Parker on Numberphile: http://bit.ly/Matt_Videos Matt's book on Amazon... US: http://bit.ly/Matt_4D_US UK: http://bit.l

From playlist Matt Parker (standupmaths) on Numberphile

Blank Editor - Project Euler Problem 1 "Fizz Buzz"

Blank Editor is a show for new programmers who have trouble applying the programming concepts they've learned into real programs. This episode solves problem 1 from the Project Euler site: https://projecteuler.net/problem=1 Github repo with source code: https://github.com/asweigart/blank

From playlist Blank Editor

Let’s Find The LCM (Lowest Common Multiple)….Step-by-Step….

TabletClass Math: https://tcmathacademy.com/ Math help with the LCM (Lowest Common Multiple). For more math help to include math lessons, practice problems and math tutorials check out my full math help program at https://tcmathacademy.com/ Math Notes: Pre-Algebra Notes: https://t

From playlist GED Prep Videos

Monte Carlo Simulation and Python 11 - Using Monte Carlo to find best multiple

Monte Carlo Simulation with Python Playlist: http://www.youtube.com/watch?v=9M_KPXwnrlE&feature=share&list=PLQVvvaa0QuDdhOnp-FnVStDsALpYk2hk0 In this video, we employ our monte carlo simulator to help us locate the best possible multiple to use with our martingale strategy, curious if the

From playlist Monte Carlo Simulation with Python

Factors and multiples

Powered by https://www.numerise.com/ Factors and multiples using Eminem www.hegartymaths.com http://www.hegartymaths.com/

From playlist Basic Arithmetic & Numeracy

8, 20 what is the LCM? (Lowest Common Multiple)

How to find the LCM (lowest common multiple). For more in-depth math help check out my catalog of courses. Every course includes over 275 videos of easy to follow and understand math instruction, with fully explained practice problems and printable worksheets, review notes and quizzes.

From playlist GED Prep Videos

Exponent Rules -- Advanced Problems (TTP Video 63)

https://www.patreon.com/ProfessorLeonard Using all the exponent rules together on some more advanced problems.

From playlist To The Point Math (TTP Videos)

Multiplication By 6

From playlist Transformations of the Number Line

Kochanski multiplication

Related pages