**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# Prime Numbers and Primality Testing

Description

This lecture covers the concepts of prime numbers, primality testing, and RSA cryptography. It explains the Chinese Remainder Theorem, Euler's Totient Function, Carmichael numbers, the Miller-Rabin primality test, and the generation of prime numbers. The instructor discusses the significance of the Fermat test, Carmichael numbers, and the correctness of RSA. The lecture also delves into the implementation of primality tests, the Miller-Rabin criterion, and the ElGamal vs. RSA comparison.

Login to watch the video

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

COM-401: Cryptography and security

This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how

Instructor

Related concepts (273)

Related lectures (596)

Primality test

A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy (its running time is polynomial in the size of the input).

Twin prime

A 'twin prime is a prime number that is either 2 less or 2 more than another prime number—for example, either member of the twin prime pair or In other words, a twin prime is a prime that has a prime gap of two. Sometimes the term twin prime is used for a pair of twin primes; an alternative name for this is prime twin' or prime pair. Twin primes become increasingly rare as one examines larger ranges, in keeping with the general tendency of gaps between adjacent primes to become larger as the numbers themselves get larger.

Fermat primality test

The Fermat primality test is a probabilistic test to determine whether a number is a probable prime. Fermat's little theorem states that if p is prime and a is not divisible by p, then If one wants to test whether p is prime, then we can pick random integers a not divisible by p and see whether the congruence holds. If it does not hold for a value of a, then p is composite. This congruence is unlikely to hold for a random a if p is composite. Therefore, if the equality does hold for one or more values of a, then we say that p is probably prime.

Public-key cryptography

Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic algorithms based on mathematical problems termed one-way functions. Security of public-key cryptography depends on keeping the private key secret; the public key can be openly distributed without compromising security.

Prime number

A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4.

RSA Cryptography: Primality Testing and Quadratic Residues

Explores RSA cryptography, covering primality testing, quadratic residues, and cryptographic applications.

Elementary Algebra: Numeric Sets

Explores elementary algebra concepts related to numeric sets and prime numbers, including unique factorization and properties.

Quantum Random Number Generation

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

Finite Abelian Groups

Covers Cauchy's theorem, classification of finite abelian groups, direct product properties, and more.

Shor's factoring algorithm: Quantum Phase Estimation

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