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

Lecture

Coppersmith's Method: Small Roots of Polynomials Mod N

In course

MATH-489: Number theory II.d - Cryptography

. ...

Description

This lecture covers Coppersmith's method, focusing on finding small roots of polynomials modulo N efficiently. The instructor explains the theorem and the process of reducing the problem to root finding over ZCR. Various concepts such as the search for linear combinations and related message attacks are discussed, along with the application of efficient methods like Newton's method.

Instructor

Dimitar Petkov Jetchev

Official source

Ontological neighbourhood

Mathematics

Analysis: Numerical analysis

Related concepts (32)

Chebyshev polynomials

The Chebyshev polynomials are two sequences of polynomials related to the cosine and sine functions, notated as and . They can be defined in several equivalent ways, one of which starts with trigonometric functions: The Chebyshev polynomials of the first kind are defined by Similarly, the Chebyshev polynomials of the second kind are defined by That these expressions define polynomials in may not be obvious at first sight, but follows by rewriting and using de Moivre's formula or by using the angle sum formulas for and repeatedly.

Laguerre polynomials

In mathematics, the Laguerre polynomials, named after Edmond Laguerre (1834–1886), are solutions of Laguerre's differential equation: which is a second-order linear differential equation. This equation has nonsingular solutions only if n is a non-negative integer. Sometimes the name Laguerre polynomials is used for solutions of where n is still a non-negative integer. Then they are also named generalized Laguerre polynomials, as will be done here (alternatively associated Laguerre polynomials or, rarely, Sonine polynomials, after their inventor Nikolay Yakovlevich Sonin).

Legendre polynomials

In mathematics, Legendre polynomials, named after Adrien-Marie Legendre (1782), are a system of complete and orthogonal polynomials with a vast number of mathematical properties and numerous applications. They can be defined in many ways, and the various definitions highlight different aspects as well as suggest generalizations and connections to different mathematical structures and physical and numerical applications. Closely related to the Legendre polynomials are associated Legendre polynomials, Legendre functions, Legendre functions of the second kind, and associated Legendre functions.

Orthogonal polynomials

In mathematics, an orthogonal polynomial sequence is a family of polynomials such that any two different polynomials in the sequence are orthogonal to each other under some inner product. The most widely used orthogonal polynomials are the classical orthogonal polynomials, consisting of the Hermite polynomials, the Laguerre polynomials and the Jacobi polynomials. The Gegenbauer polynomials form the most important class of Jacobi polynomials; they include the Chebyshev polynomials, and the Legendre polynomials as special cases.

Hermite polynomials

In mathematics, the Hermite polynomials are a classical orthogonal polynomial sequence. The polynomials arise in: signal processing as Hermitian wavelets for wavelet transform analysis probability, such as the Edgeworth series, as well as in connection with Brownian motion; combinatorics, as an example of an Appell sequence, obeying the umbral calculus; numerical analysis as Gaussian quadrature; physics, where they give rise to the eigenstates of the quantum harmonic oscillator; and they also occur in some cases of the heat equation (when the term is present); systems theory in connection with nonlinear operations on Gaussian noise.

Related lectures (29)

Attack on RSA using LLL

Covers Coppersmith's method for attacking RSA encryption by efficiently finding small roots of polynomials modulo N.

Complex Roots: Conjugate Pairs and Quadratic Equations

Explores complex roots, conjugate pairs, and quadratic equations solving strategies.

Linear Algebra Exercises MOOC: Linear Algebra (Part 1)

Covers exercises related to linear algebra, focusing on finding bases and completing them in a vector space.

Correlations of the Liouville function

Explores correlations of the Liouville function along deterministic and independent sequences, covering key concepts and theorems.

Interpolation de Lagrange