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

https://en.wikipedia.org/wiki/Prime_number

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 (65)

Related publications

Related people (5)

Related people

Related units (3)

Related units

Related concepts (231)

Related concepts

Related courses (188)

Related courses

Related lectures (471)

Related lectures

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

2-Selmer groups and the Birch-Swinnerton-Dyer Conjecture for the congruent number curves

Robert Christopher Rhoades

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.

2009

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