IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Sécurité Discussion :

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


Sujet :

Sécurité

  1. #1
    Membre actif
    Homme Profil pro
    Développeur .NET
    Inscrit en
    Janvier 2006
    Messages
    958
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Développeur .NET
    Secteur : High Tech - Produits et services télécom et Internet

    Informations forums :
    Inscription : Janvier 2006
    Messages : 958
    Points : 213
    Points
    213
    Par défaut (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?

  2. #2
    Membre confirmé

    Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Novembre 2009
    Messages
    377
    Détails du profil
    Informations personnelles :
    Localisation : Suisse

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Novembre 2009
    Messages : 377
    Points : 597
    Points
    597
    Par défaut
    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 ?

  3. #3
    Membre actif
    Homme Profil pro
    Développeur .NET
    Inscrit en
    Janvier 2006
    Messages
    958
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Développeur .NET
    Secteur : High Tech - Produits et services télécom et Internet

    Informations forums :
    Inscription : Janvier 2006
    Messages : 958
    Points : 213
    Points
    213
    Par défaut
    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!

  4. #4
    Membre confirmé

    Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Novembre 2009
    Messages
    377
    Détails du profil
    Informations personnelles :
    Localisation : Suisse

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Novembre 2009
    Messages : 377
    Points : 597
    Points
    597
    Par défaut
    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 :
    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.

Discussions similaires

  1. Une fonction implémentée en Java pour afficher les nombres premiers
    Par autran dans le forum Codes sources à télécharger
    Réponses: 2
    Dernier message: 01/05/2015, 17h45
  2. Formule mathématique pour générer un nombre entre 32 et 127
    Par taupy dans le forum Débuter avec Java
    Réponses: 5
    Dernier message: 17/04/2012, 00h29
  3. Réponses: 14
    Dernier message: 13/03/2011, 21h14
  4. Générer des nombres premiers trés grands
    Par Midou45 dans le forum Mathématiques
    Réponses: 9
    Dernier message: 04/05/2008, 01h20
  5. Algo pour générer des nombres aléatoires
    Par Admin dans le forum Algorithmes et structures de données
    Réponses: 4
    Dernier message: 12/06/2006, 10h06

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo