Prime number theorem

In mathematics, the prime number theorem (PNT) describes the asymptotic distribution of the prime numbers among the positive integers. It formalizes the intuitive idea that primes become less common as they become larger by precisely quantifying the rate at which this occurs. The theorem was proved independently by Jacques Hadamard and Charles Jean de la Vallée Poussin in 1896 using ideas introduced by Bernhard Riemann (in particular, the Riemann zeta function). The first such distribution found is π(N) ~ ''N''/log(''N''), where π(N) is the prime-counting function (the number of primes less than or equal to N) and log(N) is the natural logarithm of N. This means that for large enough N, the probability that a random integer not greater than N is prime is very close to 1 / log(N). Consequently, a random integer with at most 2n digits (for large enough n) is about half as likely to be prime as a random integer with at mo

About this result

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.

Related publications (13)

Related publications

Related people

Related units

Related concepts (45)

Related concepts

Related courses (21)

Related courses

Related lectures (43)

Related lectures

Primality Testing

Kamal Tahiri Jouti

Since the discovery of the utility of the numbers, the human being tried to differentiate them. We decide between them according to whether they are even or odd. Or, according to the fact that they are prime or composite. A natural number n >1 is called a prime number if it has no positive divisors other than 1 and n. Therefore, other numbers that are not prime have other divisors. That is why we call them composite numbers because we can write them : n = p*q with {p,q} ≠ {1,n}. The problem has always been to decide whether a number is prime or not. To answer this problem, many algorithms have been created like the Trial Division. It uses the property which says that the biggest divisor of n is smaller or equal to the square root of n. But for numbers that exceed 30 digits, it will take more than 10^13 years to know the answer. So, the interest would be to create an algorithm using mathematical bases which would answer to this question as fast as possible. This is what we will see in this project. The study of prime numbers became really important to code texts. Cryptography is one of the most important application of prime numbers theory. At the beginning, it was only used to code texts during the wars and more recently it was used for other applications, like the security of an account. Fist of all, I will focus on randomized algorithms for primality testing. Then, I will focus on a deterministic algorithm that I have implemented.

2006

Le foncteur de bi-ensembles des modules de p-permutation

Mélanie Baumann

Let k be an algebraically closed field of characteristic p, where p is a prime number or 0. Let G be a finite group and ppk(G) be the Grothendieck group of p-permutation kG-modules. If we tensor it with C, then Cppk becomes a C-linear biset functor. Recall that the simple biset functor SH,V are parametrized by pairs (H,V), where H is a finite group and V a simple COut(H)-module. If we only consider p'-groups, then Cppk = CRk is the usual representation functor and we know the simple functors which are its composition factors. If we consider only p-groups, then Cppk = CB is the Burnside functor and we also know the simple functors which are its composition factors. We want to find the composition factors of Cppk in general. In order to achieve this, we first show that the composition factors from the special cases above are also composition factors for Cppk. Then, we consider groups of little order and try to find new composition factors. This leads us to find the following new composition factors : The simple factors SCm,Cξ and SCp×Cp× Cm,Cξ, where (m,ξ) runs over the set of all pairs formed by a positive integer m prime to p and a primitive character ξ : (Z/mZ)* → C*. Their multiplicity as composition factors is 1. The simple factors SCp⋊Cl, C, where l is a number prime to p, the action of Cl on Cp is faithful and C is the trivial COut(Cp ⋊ Cl)-module. Their multiplicity as composition factors is φ(l). The simple functors SG,C, where G is a finite p-hypo-elementary B-group (for which an explicit classification is done) and C the trivial COut(G)-module. We also show that some specific simple functors appear, indexed by the groups C3 ⋊ C4, C5 ⋊ C4 and A4. On the way, we find all the composition factors of the subfunctor of permutation modules.

EPFL2012

The functor of p-permutation modules for abelian groups

Mélanie Baumann

Let k be a field of characteristic p, where p is a prime number, let pp_k(G) be the Grothendieck group of p-permutation kG-modules, where G is a finite group, and let Cpp_k(G) be pp_k(G) tensored with the field of complex numbers C. In this article, we find all the composition factors of the biset functor Cpp_k restricted to the category of abelian groups.

Elsevier2013

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 they work and sketch how they can be implemented.

MATH-313: Introduction to analytic number theory

The aim of this course is to present the basic techniques of analytic number theory.

MATH-106(e): Analysis II

Étudier les concepts fondamentaux d'analyse et le calcul différentiel et intégral des fonctions réelles de plusieurs variables.

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. F

Riemann hypothesis

In mathematics, the Riemann hypothesis is the conjecture that the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part 1/2. Man

Number theory

Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. German mathematician Carl F