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

Concept# Prime number

Summary

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. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.
The property of being prime is called primality. A simple but slow method of checking the primality of a given number n, called trial division, tests whether n is a multiple of any integer between 2 and \sqrt{n}. Faster algorithms include the Miller–Rabin primalit

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.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related publications (65)

Loading

Loading

Loading

Related people (5)

Related concepts (231)

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

Field (mathematics)

In mathematics, a field is a set on which addition, subtraction, multiplication, and division are defined and behave as the corresponding operations on rational and real numbers do. A field is thus

Mathematics

Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These top

Related lectures (471)

Related units (3)

Related courses (188)

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.

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics as diverse as mathematical reasoning, combinatorics, discrete structures & algorithmic thinking.

MATH-313: Introduction to analytic number theory

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

We take an approach toward Counting the number of integers n for which the curve (n),: y(2) = x(3) - n(2)x has 2-Selmer groups of a given size. This question was also discussed in a pair of papers by Roger Heath-Brown. In contrast to earlier work, our analysis focuses oil restricting the number of prime factors of n. Additionally, we discuss the connection between computing the size of these Selmer groups and verifying cases of the Birch and Swinnerton-Dyer Conjecture. The key ingredient for the asymptotic formulae is the "independence" of the Legendre symbol evaluated at the prime divisors of an integer with exactly k prime factors. (C) 2009 Elsevier Inc. All rights reserved.

2009Let 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.

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