**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Lecture# Integer Factorization: Quadratic Sieve

Description

This lecture covers the Quadratic Sieve method for integer factorization, which generalizes to allow for factoring smaller size numbers. The method involves sieving and selecting smooth numbers to efficiently factorize integers. It also discusses the complexity of the Quadratic Sieve algorithm and its application in finding B-smooth numbers. The instructor explains the process step by step, from sieving to selecting numbers to be factored, emphasizing the importance of choosing the right parameters for efficient factorization.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Instructor

In course

Related concepts (214)

MATH-489: Number theory II.c - Cryptography

The goal of the course is to introduce basic notions from public key cryptography (PKC) as well as basic number-theoretic methods and algorithms for cryptanalysis of protocols and schemes based on PKC

The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties.

In mathematics, a square root of a number x is a number y such that ; in other words, a number y whose square (the result of multiplying the number by itself, or ) is x. For example, 4 and −4 are square roots of 16 because . Every nonnegative real number x has a unique nonnegative square root, called the principal square root, which is denoted by where the symbol "" is called the radical sign or radix. For example, to express the fact that the principal square root of 9 is 3, we write .

In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.

In computational mathematics, an iterative method is a mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the n-th approximation is derived from the previous ones. A specific implementation with termination criteria for a given iterative method like gradient descent, hill climbing, Newton's method, or quasi-Newton methods like BFGS, is an algorithm of the iterative method.

In mathematics and computational science, the Euler method (also called the forward Euler method) is a first-order numerical procedure for solving ordinary differential equations (ODEs) with a given initial value. It is the most basic explicit method for numerical integration of ordinary differential equations and is the simplest Runge–Kutta method. The Euler method is named after Leonhard Euler, who first proposed it in his book Institutionum calculi integralis (published 1768–1870).

Related lectures (601)

Explicit Stabilised Methods: Stochastic Differential Equations

Covers explicit stabilized methods for stiff stochastic differential equations, analyzing their properties and applications.

Bernoulli convolutions: The dimension of Bernoulli convolutions

Explores the dimension of Bernoulli convolutions, discussing fair tosses and polynomial roots.

Thermodynamics and Energetics IME-251: Thermodynamics and energetics I

Explores fundamental thermodynamics concepts, laws, energy transfer, and system analysis.

Introduction to Quantum Chaos

Covers the introduction to Quantum Chaos, classical chaos, sensitivity to initial conditions, ergodicity, and Lyapunov exponents.

Periodic Table Elements and Assyr Abdulle's Contributions

Explores the periodic table of elements and Assyr Abdulle's significant contributions to numerical analysis.