**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 Graph Search.

Lecture# Fermat's Little Theorem

Description

This lecture covers Fermat's Little Theorem, which states that if N is a prime number, then for any integer A not divisible by N, A^(N-1) is congruent to 1 modulo N. The instructor explains the theorem's contrapositive and extensions, highlighting its applications in determining prime numbers and the probability of a number being prime when satisfying the theorem. Various algorithms, such as the Miller-Rabin primality test, are discussed to efficiently test for primality. The lecture also delves into generating random prime numbers and the importance of prime numbers in cryptography.

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.

Ontological neighbourhood

Related lectures (50)

Prime Numbers and Primality Testing

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

Quantum Random Number Generation

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

RSA Cryptography: Primality Testing and Quadratic Residues

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

Probability and Statistics

Introduces probability, statistics, distributions, inference, likelihood, and combinatorics for studying random events and network modeling.

Prime Numbers and Algorithms

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