(java,cryptographie) rapidité étonnante pour générer un nombre premier

Version imprimable

29/04/2012, 20h50
olivier57b

(java,cryptographie) rapidité étonnante pour générer un nombre premier

bonsoir

j'ai créé il y a de cela quelques temps un programme en VB .NET qui créait des nombres avec un nombre de chiffres élevé (plusieurs centaines) et qui disait si ce nombre avait une forte probabilité d'être premier.

pour cela j'utilisais un test de primalité dont je n'ai compris que l'énoncé, mais enfin ça marchait.

j'utilisais des classes crées par moi, pour la gestion des grands nombres (+,-,*,/,exponentiation modulaire,...).

ma question est la suivante : mon programme mettait plusieurs minutes à déterminer si un nombre était premier, or, j'ai trouvé en java une librairie de gestion des grands nombres avec une méthode qui générait un nombre premier de taille arbitraire.
à l'utilisation, la méthode met quelques secondes pour "sortir" un grand nombre premier.
je veux bien que les API java soient plus rapides que mon programme, mais à ce stade ça devient douteux.
d'où vient cette différence de vitesse?
si j'utilise cette méthode dans un programme, les nombres générés sont-ils vraiment aléatoires?
30/04/2012, 13h39
manticore

Je peux pas te confirmer la méthode utilisé par Java, mais en général on utilise un test de primalité de Miller-Rabin (openssl par exemple).

http://fr.wikipedia.org/wiki/Test_de...e_Miller-Rabin

Est-ce que tu utilisais déjà ce type de test dans ta version sur VB ?

Ensuite, il peut y avoir des différences importante sur la manipulation des grand-nombres, est-ce que tu utilisais des bitsets ?

Quel est le nom de ton API java ?
30/04/2012, 19h04
olivier57b

je n'utilisais ni l'un ni l'autre; pour la formule mathématique, c'était la formule de solovay-strassen (ici utilisant le symbole de legendre, et non je n'utilisais pas les bitsets.
kesako?
j'ai analysé par exemple comment faire une division et j'ai tout codé à la main!
01/05/2012, 00h25
manticore

Citation:

c'était la formule de solovay-strassen (ici utilisant le symbole de legendre, et non je n'utilisais pas les bitsets.
kesako?

Je connaissais pas, mais d'après ce que j'ai lu c'est une alternative tout à fait crédible, cependant il te faut faire de l'exponentiation modulaire afin d'avoir des performance viable.

Le bitset est une façon de représenter des grands nombres en utilisant des bits par exemple 8 = 1000, et avec des masques tu peux faire des opérations très rapides pour des grands nombres.

Si tu travaillais avec des grands nombres avec une représentation standard, c'est normal que tu rencontres un facteurs énorme entre ta version java et VB.

Donc pour ta question :

Citation:

si j'utilise cette méthode dans un programme, les nombres générés sont-ils vraiment aléatoires?

Je dirai oui, cependant, sans avoir le nom de l'API et consulté la doc je peux pas t'en dire plus ;).

De plus la mise en place de l'algorithme demande beaucoup de connaissances d'optimisations et de temps. Ce qui augmente entre la différence que tu constates.