test Miller-Rabin sur de grands nombres

S. D. · June 2006

Titre initial : calcul du temps du test de Miller-Rabin sur de très grands nombres

Bonjour,

Je m'intéresse aux nombres premiers et notamment à la génération de très grands nombres premiers par ordinateur. Je bute actuellement sur un problème technique : comment calculer le temps maximum nécessaire à un ordinateur (mettons de 1,8 GHz) pour réaliser 10 itérations du test probabiliste de Miller-Rabin avec un nombre de x millions de chiffres (mettons 3 millions de chiffres)?
Je connais l'expression du temps d'exécution polynomial du test de Miller-Rabin : Õ(k × log2 n) (avec la multiplication FFT; k est le nombre d'itérations et n le nombre à tester). Mais ce n'est pas ça que je cherche. Je souhaite trouver une formule qui donne un résultat en secondes ou en jours, de manière plus ou moins approximative peu importe.

Merci pour votre aide à tous!

S. D.

[SD : Evite les titres trop longs, ils désorganisent la 1ère page du forum. AD]

Foufoux · June 2006

Bonjour,

Tu peux en déduire le temps, puisque ton O(klog(n)) represente le nombre d'opération moyen.
Connaissant la frequence de ton processeur (le nombre d'operation qu'il traite par sec) tu peux dejà avoir une bonne estimation.
Cependant pour être plus rigoureux, tu dois tenir compte du temps d'acces (en lecture et ecriture) aux memoires vives et caches...

Cordialement,
Foufoux
P.S : Et la NTT ne va pas plus vite que la FTT sur le test de MR?

jobherzt · June 2006

la methode violente :

tu sais que c'est en Õ(k × log2 n) .. ca te donne une idee du nombre d'operation. donc si $\alpha$ est le temps moyen d'une operation, le temps pris va etre de la forme $\alpha$ Õ(k × log2 n).

moralité, fait un programme qui fait ce test sur plein de nombre de plus en plus grand, tu stockes les couples (n,t(n)), et tu fitte avec la fonction... apres, tu en deduis une estimation du temps pour de plus grand nombres.

S. D. · June 2006

Je ne connais pas la NTT Foufoux. En fait, j'utilise le langage C/C++ et la librairie GMP (dans laquelle est implémentée la multiplication FTT). Peut-être que la NTT est utilisée aussi via les fonctions de cette librairie?

Rapelez-moi un détail : log2 n signifie (log n)², log (2n) ou log n² ?

jobherzt, que veux-tu dire par "tu fitte avec la fonction"?
Est-ce que ça signifie que je détermine le coefficient directeur de la droite (encore faut-il que ce soit une droite) afin d'avoir une estimation de t(n) pour de plus grands nombres?

S. D. · June 2006

Je ne connais pas la NTT Foufoux. En fait, j'utilise le langage C/C++ et la librairie GMP (dans laquelle est implémentée la multiplication FTT). Peut-être que la NTT est utilisée aussi via les fonctions de cette librairie?

Rapelez-moi un détail : log2 n signifie (log n)², log (2n) ou log n² ?

jobherzt, que veux-tu dire par "tu fitte avec la fonction"?
Est-ce que ça signifie que je détermine le coefficient directeur de la droite (encore faut-il que ce soit une droite) afin d'avoir une estimation de t(n) pour de plus grands nombres?

jobherzt · June 2006

tout d'abord, log2 c'est le log en base 2, donc log(n)/log(2)

quand je dis tu fittes, oui, ca revient a ca, sauf que ca ne sera pas une droite, mais justement une courbe de fonction de la forme :

$$n\longrightarrow \alpha Õ(k × log2 n)$$

n'importe quel logiciel de calcul numerique (octave par exemple ) te permettra de faire ca, il n'y a qu'un seul parametre a fitter donc ca devrait aller...

jobherzt · June 2006

accessoirement, log2(n) donne une estimation du nombre de chiffre necessaire pour ecrire n en binaire.<BR>

Foufoux · June 2006

Salut,

la NTT ou Number Theory Transform est assez efficace en general.
Nous l'avions utilisé (mon binome et moi) pour implementer AKS, et les gains de temps étant relativement grand. En general elle etait au moins 10 fois plus rapide que la FFT.
Nous avions egalement implementé Miller-Rabin, mais nous nous étions bornés à des nombres de 1000 chiffres. Et notre algo de base (sans NTT) était suffisament rapide.

Bref, nous avions utilisé la bibliotheque Givaro basée sur GMP...

Voilá,
En esperant t'avoir un peu eclairé
Foufoux

Hugo_ · June 2006

Le problème c'est qu'on peut chiffrer le nombre d'opérations à faire, mais le processeur fait beaucoup d'autres choses en mêmes temps, rien que Windows doit utiliser beaucoup plus de ressources que le test en lui même.

jobherzt · June 2006

beaucoup plus, je ne sais pas, mais c'est certain.
<BR>apres, ca permet quand meme d'avoir une estimation... et je ne vois pas comment faire autrement.. finalement, si on suppose que l'utilisation des ressources par le systeme d'exploitation est plus ou moins constant, alors il influe tjrs de la meme maniere sur le temps pris par une operation elementaire.. donc il fera varier le alpha, mais ce sera quand meme coherent.. et je te rappelle que le jour ou l'algo tournera pour de vrai, windows sera tjrs la, donc mieux vaut en tenire compte :-)<BR>

S. D. · June 2006

Prenons n, un nombre de 33 millions de chiffres (je sais c'est ambitieux). Nous ne réaliserons qu'une seule itération du test. Donc, n = 10^33.000.000 et k = 1.

Dîtes-moi si je me trompe dans mes calculs :

$\alpha$ Õ(1x(log 10^33.000.000)/log 2)
= $\alpha$ Õ(1x(log 10^33.000.000)/log 2)
= $\alpha$ Õ(1x33.000.000/log 2)
= $\alpha$ Õ(33.000.000/log 2)
= $\alpha$ Õ(109623627,1)

C'est correct?
Si oui, reste à trouver $\alpha$...

jobherzt · June 2006

a priori c'est correct.. reste a trouver alpha, mais honnetement c'est assez facile d'en avoir une approximation a la louche.. un petit timer dans un programme, tu le lance sur des nombres de taille differente (ratisse large quand meme, vaut mieux laisser tourner l'ordi 24 heure et avoir un resultat vaguement fiable.. )ton prog stocke tout ca dans un fichier, tu ouvre le fichier sous octave, tu fitte et c'est fini !<BR>

test Miller-Rabin sur de grands nombres

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 4