**Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?**

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Publication# Primality Testing

Résumé

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.

Official source

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Publications associées (3)

Chargement

Chargement

Chargement

Concepts associés (20)

Racine carrée

En mathématiques élémentaires, la racine carrée d'un nombre réel positif x est l'unique réel positif qui, lorsqu'il est multiplié par lui-même, donne x, c'est-à-dire le nombre positif dont le carré

Nombre

Un nombre est un concept permettant d’évaluer et de comparer des quantités ou des rapports de grandeurs, mais aussi d’ordonner des éléments en indiquant leur rang. Souvent écrits à l’aide d’un ou pl

Nombre premier

vignette|Nombres naturels de zéro à cent. Les nombres premiers sont marqués en rouge.
vignette|Le nombre 7 est premier car il admet exactement deux diviseurs positifs distincts.
Un nombre premier est

This paper presents an algorithm for the fully dynamic biconnectivity problem whose running time is exponentially faster than all previously known solutions. It is the first dynamic algorithm that answers biconnectivity queries in time O(log2 n) in a n-node graph and can be updated after an edge insertion or deletion in polylogarithmic time. Our algorithm is a Las-Vegas style randomized algorithm with the update time amortized update time O(log4 n). Only recently the best deterministic result for this problem was improved to O(Vn log2 n). We also give the first fully dynamic and a novel deletions-only transitive closure (i.e. directed connectivity) algorithms. These are randomized Monte Carlo algorithms. Let n be the number of nodes in the graph and let m be the average number of edges in the graph during the whole update sequence: The fully dynamic algorithms achieve (1) query time O(n/log n) and update time O(mVn log2 n+n); or (2) query time O(n/log n) and update time O[n.pow(m,(u-1)/u)].pow2(log(n)) = O[n.pow(m,0.58).pow2(log(n)], where u is the exponent for boolean matrix multiplication (currently u = 2.38). The deletions-only algorithm answers queries in time O(n/log n). Its amortized update time is O(n log2 n).

Randomization is a fundamental tool used in many theoretical and practical areas of computer science. We study here the role of randomization in the area of submodular function maximization. In this area, most algorithms are randomized, and in almost all cases the approximation ratios obtained by current randomized algorithms are superior to the best results obtained by known deterministic algorithms. Derandomization of algorithms for general submodular function maximization seems hard since the access to the function is done via a value oracle. This makes it hard, for example, to apply standard derandomization techniques such as conditional expectations. Therefore, an interesting fundamental problem in this area is whether randomization is inherently necessary for obtaining good approximation ratios. In this work, we give evidence that randomization is not necessary for obtaining good algorithms by presenting a new technique for derandomization of algorithms for submodular function maximization. Our high level idea is to maintain explicitly a (small) distribution over the states of the algorithm, and carefully update it using marginal values obtained from an extreme point solution of a suitable linear formulation. We demonstrate our technique on two recent algorithms for unconstrained submodular maximization and for maximizing a submodular function subject to a cardinality constraint. In particular, for unconstrained submodular maximization we obtain an optimal deterministic 1/2-approximation showing that randomization is unnecessary for obtaining optimal results for this setting.

This paper presents an algorithm for the fully dynamic biconnectivity problem whose running time is exponentially faster than all previously known solutions. It is the first dynamic algorithm that answers biconnectivity queries in time O(pow2(log(n)) in a n-node graph and can be updated after an edge insertion or deletion in polylogarithmic time. Our algorithm is a Las-Vegas style randomized algorithm with the update time amortized update time O(pow(log(n),4)). Only recently the best deterministic result for this problem was improved to Osqrt(n.pow2(log(n))). We also give the first fully dynamic and a novel deletions-only transitive closure (i.e. directed connectivity) algorithms. These are randomized Monte Carlo algorithms. Let n be the number of nodes in the graph and let M be the average number of edges in the graph during the whole update sequence: The fully dynamic algorithms achieve (1) query time O(n/logn) and update time O(M.sqrt(n.pow2(log(n)))+n); or (2) query time O(n/logn) and update time O[pow(M,(u-1)/u))].pow2(log(n))=O[M.pow(n,0.58).pow2(log(n))], where u is the exponent for boolean matrix multiplication (currently u=2.38). The deletions-only algorithm answers queries in time O(n/logn). Its amortized update time is O(n.pow2(log(n)))

1995