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

Lecture

Exponentiation

In course

MATH-489: Number theory II.d - Cryptography

. ...

Description

This lecture covers the concept of exponentiation, RSA encryption and decryption, big integer multiplication, Schönhage-Strassen algorithm, and the use of primitive roots. It explains the computation of x^y, the properties of RSA encryption, and the challenges of working with primitive roots.

Instructor

Dimitar Petkov Jetchev

Official source

Related concepts (26)

Encryption

In cryptography, encryption is the process of encoding information. This process converts the original representation of the information, known as plaintext, into an alternative form known as ciphertext. Ideally, only authorized parties can decipher a ciphertext back to plaintext and access the original information. Encryption does not itself prevent interference but denies the intelligible content to a would-be interceptor. For technical reasons, an encryption scheme usually uses a pseudo-random encryption key generated by an algorithm.

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.

Karatsuba algorithm

The Karatsuba algorithm is a fast multiplication algorithm. It was discovered by Anatoly Karatsuba in 1960 and published in 1962. It is a divide-and-conquer algorithm that reduces the multiplication of two n-digit numbers to three multiplications of n/2-digit numbers and, by repeating this reduction, to at most single-digit multiplications. It is therefore asymptotically faster than the traditional algorithm, which performs single-digit products.

Exponentiation

In mathematics, exponentiation is an operation involving two numbers, the base and the exponent or power. Exponentiation is written as bn, where b is the base and n is the power; this is pronounced as "b (raised) to the (power of) n". When n is a positive integer, exponentiation corresponds to repeated multiplication of the base: that is, bn is the product of multiplying n bases: The exponent is usually shown as a superscript to the right of the base.

Multiplication algorithm

A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are more efficient than others. Efficient multiplication algorithms have existed since the advent of the decimal system. If a positional numeral system is used, a natural way of multiplying numbers is taught in schools as long multiplication, sometimes called grade-school multiplication, sometimes called the Standard Algorithm: multiply the multiplicand by each digit of the multiplier and then add up all the properly shifted results.

Related lectures (33)

Montgomery Multiplication

Covers Barrett reduction, Montgomery form of integers, and efficient Montgomery product computation.

Cyclic Groups: Structure and Applications

Explores cyclic groups, generators, isomorphisms, and the discrete logarithm problem in depth, highlighting their importance and applications.

Algorithms & Growth of Functions

Covers optimization algorithms, stable matching, and Big-O notation for algorithm efficiency.

Exponentiation: Time Complexity

Covers the fast exponentiation algorithm and its time complexity, prime number properties, and the El-Gamal encryption scheme.

Prime Numbers and Algorithms

Covers prime numbers, primality testing algorithms, modular arithmetic, and efficient exponentiation methods.

Related concepts (26)

Encryption

Modular exponentiation

Karatsuba algorithm

Exponentiation

Multiplication algorithm