Accueil > Forum > > > > question à propos du test de Miller-Rabin [édité]
 question à propos du test de Miller-Rabin [édité]
mercredi 5 janvier 2005 à 17:15:47 |
question à propos du test de Miller-Rabin [édité]
scelw
|
Il s'agit d'une question à propos du test de Miller-Rabin.
Pour ceux qui seraient perdus, ce test est un test probabiliste testant la primalité d'un nombre...
(>>  [ Lien ] ...à lire pour comprendre la suite!)
C'est l'un des tests les plus rapides qui existent au monde.
Mais il possède un \"goulot d'étranglement\" qui limite malgré tout sa vitesse d'exécution dès lors que l'on veut tester des nombres de très grande taille (plus d'un million de chiffres). Ce goulot d'étranglement se situe à la ligne qui effectue le calcul de y = a^r mod n (voir lien donné ci-dessus).
Ma question : pour diminuer sensiblement le temps d'exécution de ce test,
serait-il possible de choisir la variable aléatoire a dans l'intervalle ]1 ; (n-1)/2[ , voire ]1 ; (n-1)/(10^1000)[ ??
Quelles répercussions sur le résultat ? La probabilité d'avoir un nombre premier est-elle fortement modifiée?
Merci!
-
|
|
mardi 11 janvier 2005 à 17:10:35 |
Re : question à propos du test de Miller-Rabin [édité]
scelw
|
si cette question et la recherche des nombres premiers vous intéressent, suivez le débat sur : [ Lien ] ! :) amicalement, scelw
|
|
Cette discussion est classée dans : test, propos, question, miller, rabin
 Répondre à ce message
 Sujets en rapport avec ce message
tests de primalité : Miller-Rabin vs Test des 3 Indiens [ par scelw ]
Quel est le test de primalité d'un nombre (pour savoir si un nombre est premier) le plus rapide (en terme de temps d'exécution) entre le test de Mille
aide à propos de Miller-Rabin et du temps d'exécution des tests de primalité en général [ par scelw ]
Bonjour,Deux questions :1°) Pour calculer le nombre d'opérations nécessaires à la réalisation d'un test probabiliste de Miller-Rabin, j'ai entendu dir
Question a propos de 'delete' en C++... [ par akboy7015 ]
Serai t'il possible de detecter si un pointeur vers un objet quelconque instancié avec 'new' et déjà détruit avec 'delete' ou pas?je m'explique:pMonOb
Fonction dans DLL [ par guitoulefoux ]
Bonjour,J'ai une petite question sur les DLL.J'ai fais une DLL avec un fonction "StartProcess".J'arrive bien à appeler la fonction "StartProcess" d'un
Petite question à propos de calloc. [ par heyhi ]
Bonjour tout le monde. J'ai juste une petite question à propos de la fonction calloc. Cette fonction existait déjà dans la lib standard du C, et j'ai
a propos de SNPRINTF [ par xtremejames183 ]
Simple question stupide a propos de snprintf{ char nom[40]; snprintf(nom,sizeof(nom),"votre nom est %s",nom);<
[Sockets] Problèmes de réceptions/envois [ par gg_the_boss ]
Salut à tous !Donc voila j'essaye d'ajouter la gestion des sockets à mon langage de script. J'ai implementé les fonctions mais ca ne marche qu'a moiti
Compilation d'un header avec gcc [ par manta7 ]
Salut je viens juste d'installer linux et je voulais savoir comment compiler des projets avec des headers. Je m'explique : J'ai crée un petit fichier
kernel en C ou C++, possible? [ par veler ]
Salut à tous, c'est la prmeière fois que je pose une question dans la section C/C++, vla, esque c'est possible de faire un Kernel en C++? et, autre qu
Test d'un serveur pop [ par poiuytrez3 ]
Bonjour, Je dois faire un petit programme qui a pour but de vérifier qu'un serveur pop marche bien.Ce programme doit tourner sur linux. Es-ce compliq
 Livres en rapport
|
Derniers Blogs
 TECHDAYS PARIS 2010 : PLEINIèRE DERNIER JOURTECHDAYS PARIS 2010 : PLEINIèRE DERNIER JOUR par ROMELARD Fabrice
Cette session est la dernière pleinière de ces 3 jours de TechDays Paris 2010. Généralement, cette troisième journée est plus axée sur l'avenir vu par Microsoft. Après un retour sur l'avenir vu par la Science Fiction ou par ...
Cliquez pour lire la suite de l'article par ROMELARD Fabrice UNE JOLIE-HORLOGE ET PAS QU'UN PEU !UNE JOLIE-HORLOGE ET PAS QU'UN PEU ! par neodante
Pour les possesseurs d'iPhone, ça y est Bijin Tokei - qui se traduit littéralement en Français par " Jolie Horloge " - est arrivé et GRATUITEMENT s'il vous plaît ! Après la version Tokyo, Hokkaido, night club, racing, Gal, "pour les mademoiselles'", . voi...
Cliquez pour lire la suite de l'article par neodante TECHDAYS PARIS 2010 : CONNECTEZ VOS DONNéES à SHAREPOINT 2010 AVEC LES BUSINESS CONNECTIVITY SERVICESTECHDAYS PARIS 2010 : CONNECTEZ VOS DONNéES à SHAREPOINT 2010 AVEC LES BUSINESS CONNECTIVITY SERVICES par ROMELARD Fabrice
Animé par: Gaetan Bouveret et Julien Chomarat Business Connectivity Services (BCS) est dans SharePoint 2010 la version 2 de Business Data Catalog (BDC dans SharePoint 2007). Il s'agit de la solution permettant de visualiser des données provenan...
Cliquez pour lire la suite de l'article par ROMELARD Fabrice [DIVERS] SUIVRE VOS SéRIES PRéFéRéS SUR LA TOILE[DIVERS] SUIVRE VOS SéRIES PRéFéRéS SUR LA TOILE par orion
Comme de nombreux geek, je suis un grand amateur de série TV et je rate régulièrement des épisodes de mes séries préférés. Une solution s'offre à vous avec ce merveilleux site : Tv Gorge - www.tvgorge.com Moteur de recherche à l'appui, vous pouvez ...
Cliquez pour lire la suite de l'article par orion TECHDAYS PARIS 2010 : LA BI DANS SHAREPOINT 2010TECHDAYS PARIS 2010 : LA BI DANS SHAREPOINT 2010 par ROMELARD Fabrice
Animé par: Vincent Bellet et Baptiste Giraudier La BI dans SharePoint 2010, Les nouveaux services d'application dans SP2010 et SQL Server Reporting services 2008 R2. La BI dans SharePoint est généralisée pour tous afin de permettre à tous les coll...
Cliquez pour lire la suite de l'article par ROMELARD Fabrice
Forum
 RE : WIN APIRE : WIN API par racpp
Cliquez pour lire la suite par racpp
Logiciels
 DB-MAIN (9.1.0)DB-MAIN (9.1.0)DB-MAIN is a data-modeling and data-architecture tool. It is designed to help developers and anal... Cliquez pour télécharger DB-MAIN Xilisoft DPG Convertisseur (5.1.37.0120)XILISOFT DPG CONVERTISSEUR (5.1.37.0120)Xilisoft DPG Convertisseur offre aux fans de Nintendo DS une bonne solution leur permettant de dé... Cliquez pour télécharger Xilisoft DPG Convertisseur GraphicsGale (2.01.01)GRAPHICSGALE (2.01.01)GraphicsGale est un logiciel de PixelArt avec de nombreuse fonctionnalités permettant de réalisé ... Cliquez pour télécharger GraphicsGale Architecte 3D (Platinum 2010)ARCHITECTE 3D (PLATINUM 2010)Architecte 3D Platinium vous permet de concevoir facilement les plans votre future maison, de l'é... Cliquez pour télécharger Architecte 3D TeamViewer 5 (TeamViewer 5)TEAMVIEWER 5 (TEAMVIEWER 5)Dépanner un ami,expliquer une manipulation devient un jeu d'enfant.
Prise en main d'un autre ord... Cliquez pour télécharger TeamViewer 5
|