Concept

Test de primalité AKS

Le test de primalité AKS (aussi connu comme le test de primalité Agrawal-Kayal-Saxena et le test cyclotomique AKS) est un algorithme de preuve de primalité déterministe et généraliste (fonctionne pour tous les nombres) publié le par trois scientifiques indiens nommés Manindra Agrawal, Neeraj Kayal et Nitin Saxena (A.K.S). Ce test est le premier en mesure de déterminer la primalité d'un nombre dans un temps polynomial. Ce test a été publié dans un article scientifique intitulé « PRIMES is in P ». Cet article leur a valu le prestigieux prix Gödel 2006. L'algorithme détermine si un nombre est premier ou composé (au sens de la factorisation). L'algorithme repose sur la généralisation suivante du petit théorème de Fermat : pour tout entier n ≥ 2 et tout entier a premier avec n, n est un nombre premier si et seulement si qui résulte d'une propriété des coefficients binomiaux : n est un nombre premier si et seulement si L'objet d'AKS est d'exploiter efficacement cette propriété. L'algorithme est globalement le suivant: procédure AKS(): Si avec et alors renvoyer non-premier (étape 1) Construire le plus petit entier tel que l'ordre de modulo soit supérieur à (étape 2) Si pgcd() != 1 et pgcd()!= n pour un certain alors renvoyer non-premier (étape 3) Si alors renvoyer premier (étape 4) Pour compris entre 1 et faire: Si alors renvoyer non-premier (étape 5) Renvoyer premier (étape 6) On cherche à démontrer que l'algorithme renvoie premier si, et seulement si son argument est un nombre premier. La preuve repose sur des résultats sur les corps finis et de diverses inégalités dont la plupart sont démontrées par récurrence. On note tout au long de la démonstration l'ordre (théorie des groupes) de dans le groupe des inversibles de l'anneau et l'Indicatrice d'Euler. On suppose tout d'abord que est premier, l'algorithme peut renvoyer une valeur (premier ou non-premier) à cinq différentes étapes: Il est clair que l'algorithme ne peut pas renvoyer non-premier aux étapes 1 et 3. D'après le Théorème de Lagrange sur les groupes, l'ordre de tout élément divise l'ordre du groupe.

Source officielle

https://fr.wikipedia.org/wiki/Test_de_primalité_AKS

À propos de ce résultat

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.

Cours associés (4)

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

EE-556: Mathematics of data: from theory to computation

This course provides an overview of key advances in continuous optimization and statistical analysis for machine learning. We review recent learning formulations and models as well as their guarantees

COM-501: Advanced cryptography

This course reviews some failure cases in public-key cryptography. It introduces some cryptanalysis techniques. It also presents fundamentals in cryptography such as interactive proofs. Finally, it presents some techniques to validate the security of crypt ...

Afficher plus

Séances de cours associées (13)

Nombres premiers et algorithmes

Couvre les nombres premiers, les algorithmes de test de primalité, l'arithmétique modulaire et les méthodes d'exponentiation efficaces.

Tests de nombres premiers et de primalité

Couvre les nombres premiers, la cryptographie RSA et les tests de primalité, y compris le théorème des restes chinois et le test de Miller-Rabin.

Petit théorème de Fermat : applications et probabilités

Explore les applications et les probabilités du Petit Théorème de Fermat dans les tests de primalité.

Afficher plus

Publications associées (7)

Decentralized Primal-Dual Learning over Directed Graphs

Distributed adaptation and learning over directed, unbalanced graphs poses unique challenges due to asymmetric communication and heterogeneous data across nodes. In this work, we introduce a novel class of first-order primal–dual stochastic gradient algorithms for such graphs. Our flagship algorithm, called primal-dual pull diffusion stochastic gradient, is designed to update both the decision variables (primal) and the associated multipliers (dual) using two left-stochastic combination matrices. This desig

2026

Mechanized Semantics for JavaScript Regular Expressions

We introduce a mechanization of the JavaScript regexes by transcribing the ECMAScript specification, to which JavaScript conforms, into Coq. We discuss the challenges which arose during this mechanization, and present our efforts to ensure that the result is faithful to the original paper specification. We also use our implementation to prove some properties of the specification, notably that the functions it defines terminate and that no operation ever fails. We extract the implemented engine to OCaml and

EPFL2024

Measurement and characterization of room impulse responses

Room acoustics refers to the audio capture of an enclosed room. It can be seen as its color and fully describes the characteristics of the room, including the shape, size or the population. The goal of the project is to set up a database of Room impulse responses which will be useful in many fields in order to test algorithms. This document covers the way to set up equipment and successfully capture one of those room impulse responses.

2016

Afficher plus

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Source officielle

https://fr.wikipedia.org/wiki/Test_de_primalité_AKS

À propos de ce résultat

Cours associés (4)

COM-401: Cryptography and security

EE-556: Mathematics of data: from theory to computation

COM-501: Advanced cryptography

Afficher plus

Séances de cours associées (13)

Nombres premiers et algorithmes

Couvre les nombres premiers, les algorithmes de test de primalité, l'arithmétique modulaire et les méthodes d'exponentiation efficaces.

Tests de nombres premiers et de primalité

Couvre les nombres premiers, la cryptographie RSA et les tests de primalité, y compris le théorème des restes chinois et le test de Miller-Rabin.

Petit théorème de Fermat : applications et probabilités

Explore les applications et les probabilités du Petit Théorème de Fermat dans les tests de primalité.

Afficher plus

Publications associées (7)

Decentralized Primal-Dual Learning over Directed Graphs

2026

Mechanized Semantics for JavaScript Regular Expressions

EPFL2024

Measurement and characterization of room impulse responses

2016

Afficher plus

Personnes associées (3)

Alessandro Chiesa

Alessandro Chiesa is a faculty member in computer science. He conducts research in complexity theory, cryptography, and security, with a focus on the theoretical foundations and practical implementations of cryptographic proofs that are short and easy to verify. He is a co-author of several zkSNARK libraries, and is a co-inventor of the Zerocash protocol. He has co-founded Zcash and StarkWare Industries. He is a recipient of a Sloan Research Fellowship (2021), an Okawa Foundation Research Grant (2020), and Google Faculty Research Awards (2018 and 2017). He was included in MIT Technology Review's "35 Innovators Under 35" list in 2018.

Dimitar Petkov Jetchev

Philippe Chabloz

Enseignement et PhD Cours Mathématiques MATH-189 Ce cours a pour but de donner les fondements de mathématiques nécessaires à l'architecte contemporain évoluant dans une école polytechnique.

Concepts associés (8)

Test de primalité

vignette|Le 39e nombre premier de Mersenne découvert à ce jour pour un article sur la primalité Un test de primalité est un algorithme permettant de savoir si un nombre entier est premier. Le test le plus simple est celui des divisions successives : pour tester N, on vérifie s’il est divisible par l’un des entiers compris au sens large entre 2 et N-1. Si la réponse est négative, alors N est premier, sinon il est composé.

Complexité en temps

En algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée. Le temps compte le nombre d'étapes de calcul avant d'arriver à un résultat. Habituellement, le temps correspondant à des entrées de taille n est le temps le plus long parmi les temps d’exécution des entrées de cette taille ; on parle de complexité dans le pire cas. Les études de complexité portent dans la majorité des cas sur le comportement asymptotique, lorsque la taille des entrées tend vers l'infini, et l'on utilise couramment les notations grand O de Landau.

Polynôme cyclotomique

En mathématiques, plus précisément en algèbre commutative, le polynôme cyclotomique usuel associé à un entier naturel n est le polynôme unitaire dont les racines complexes sont les racines primitives n-ièmes de l'unité. Son degré vaut φ(n), où φ désigne la fonction indicatrice d'Euler. Il est à coefficients entiers et irréductible sur Q.

Afficher plus

Notebooks associés (1)

Implementing a Fractional Resampler using Local Lagrange Interpolation

FIR Resampling[1]¶

                                      [2]Paolo Prandoni, [3]LCAV, EPFL

In this notebook we will implement a simple fractional resampler that uses local Lagrange interpolation. The resampler can be used to perform any rational sampling rate change (but beware of aliasing when downsampling!) In [1]: import numpy as np import IPython from scipy.io import wavfile Local Lagrange interpolation[4]¶ To perform resampling we will need to compute subsample values and, in