**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# Discrete Log Problem: Pollard's Rho Method

Description

This lecture covers the discrete log problem and introduces Pollard's rho method, which aims to find collisions in a cyclic group of order N generated by g. The method involves partitioning the group, fixing initial values, and iteratively computing solutions. By adapting Pollard's idea, the lecture explores how to factor integers and find collisions efficiently, with a focus on constant memory usage and recursive computation.

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.

In course

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

Related concepts (96)

Instructor

Integer factorization

In number theory, integer factorization is the decomposition, when possible, of a positive integer into a product of smaller integers. If the factors are further restricted to be prime numbers, the process is called prime factorization, and includes the test whether the given integer is prime (in this case, one has a "product" of a single factor). When the numbers are sufficiently large, no efficient non-quantum integer factorization algorithm is known. However, it has not been proven that such an algorithm does not exist.

Theory of computation

In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., approximate solutions versus precise ones). The field is divided into three major branches: automata theory and formal languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?".

Model of computation

In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input. A model describes how units of computations, memories, and communications are organized. The computational complexity of an algorithm can be measured given a model of computation. Using a model allows studying the performance of algorithms independently of the variations that are specific to particular implementations and specific technology.

Square-free integer

In mathematics, a square-free integer (or squarefree integer) is an integer which is divisible by no square number other than 1. That is, its prime factorization has exactly one factor for each prime that appears in it. For example, 10 = 2 ⋅ 5 is square-free, but 18 = 2 ⋅ 3 ⋅ 3 is not, because 18 is divisible by 9 = 32. The smallest positive square-free numbers are Every positive integer can be factored in a unique way as where the different from one are square-free integers that are pairwise coprime.

Railway track

A railway track (British English and UIC terminology) or railroad track (American English), also known as a train track or permanent way, is the structure on a railway or railroad consisting of the , fasteners, railroad ties (sleepers, British English) and ballast (or slab track), plus the underlying subgrade. It enables trains to move by providing a dependable surface for their wheels to roll upon. Early tracks were constructed with wooden or cast iron rails, and wooden or stone sleepers; since the 1870s, rails have almost universally been made from steel.

Related lectures (42)

Prime Numbers and Primality TestingCOM-401: Cryptography and security

Covers prime numbers, RSA cryptography, and primality testing, including the Chinese Remainder Theorem and the Miller-Rabin test.

Shor's factoring algorithm: Quantum Phase EstimationPHYS-641: Quantum Computing

Covers Shor's factoring algorithm and the link between order finding and factoring.

Logic and AlgorithmsCS-101: Advanced information, computation, communication I

Covers logic, mathematical reasoning, basic structures, and algorithms, exploring proofs, sets, functions, and recursion.

Algorithmic Complexity: Big-O NotationCS-101: Advanced information, computation, communication I

Introduces Big-O notation for analyzing algorithm efficiency, covering logic, structures, and growth functions.

Quantum Random Number GenerationPHYS-758: Advanced Course on Quantum Communication

Explores quantum random number generation, discussing the challenges and implementations of generating good randomness using quantum devices.