Nombre premier aléatoire

Comment générer rapidement un nombre premier aléatoire, c'est-à-dire avec une longueur de 1024 bits?Nombre premier aléatoire

Source

2009-11-20 gmile

Quelle langue utilisez-vous? –

Voulez-vous dire absolument absolument premier, ou le plus probablement premier à toutes fins pratiques? Ces primes vont-elles être utilisées à des fins de sécurité, ou autre chose? –

@ Mark_Byers J'utilise Ruby. Oui, c'est pour des raisons de sécurité. J'essaye de faire un cryptage RSA. – gmile

Générer 1024 bits aléatoires. Utilisez une source aléatoire suffisamment forte pour l'usage auquel vous vous destinez.
Définissez les bits les plus hauts et les plus bas à 1. Cela s'assure qu'il n'y a pas de zéros en tête (le premier candidat est assez grand) et ce n'est pas un nombre pair (certainement pas premier).
Test for primality. S'il ne s'agit pas d'un nombre premier, revenez à 1.

Vous pouvez également utiliser une fonction de bibliothèque qui génère des nombres premiers pour vous.

Source

2009-11-20 10:52:32 laalto

Facultativement - lisez la distribution des primes pour vous assurer que cet algorithme est faisable (c'est-à-dire qu'il ne nécessitera pas des milliers de tentatives). –

Il n'aura pas besoin de trillions de tentatives: la densité des nombres premiers est très proche de 1 dans ln (x). Dans ce cas, 1 sur 710, mais parce qu'il évite les nombres pairs 1 sur 305. Il faudra des trillions de divisions d'essai pour le prouver, sauf si vous utilisez un test de primalité non trivial. Et si vous avez besoin d'un test de primalité non trivial, il n'est pas clair pour moi pourquoi vous n'utilisiez pas non plus un moyen non trivial de générer de meilleurs candidats. –

Merci, c'était une idée initiale. Bien que je voulais savoir s'il y a une solution plus rapide. – gmile

Utilisez une fonction de bibliothèque, telle que OpenSSL. Il n'y a pas besoin d'écrire cela vous-même.

Exemple: http://ardoino.com/7-maths-openssl-primes-random/

Source

2009-11-20 10:47:28

Pour le commerce mémoire pour la vitesse que vous pouvez simplement les générer et les stocker dans une liste, puis choisir au hasard un.

Editer: Naturellement, vous ne pouvez pas les générer tous de sorte que le meilleur que vous pourriez réaliser est pseudo-aléatoire à un coût élevé en mémoire. Aussi ce n'est pas bon si vous le voulez pour la sécurité.

Source

2009-11-20 10:48:05 Jonas

"les générer"? tous!?! –

Ce ne serait pas une bonne idée si les nombres premiers sont nécessaires pour des raisons de sécurité, comme c'est souvent le cas. –

Marque: Mis à part le problème évident du stockage de tous les nombres premiers à 1024 chiffres, où est le problème? Vous choisiriez un taux aléatoire de toute façon. – Joey

1024 c'est beaucoup. Etes-vous sûr qu'un premier probabiliste ne fera pas? générateur premier probabilistes fait partie de JDK

Source

2009-11-20 10:50:35 glebm

-1, je pense que vous suggérez un générateur primaire probabiliste quand vous dites pseudo premier. Un pseudo prime n'est PAS un nombre premier (c'est-à-dire qu'il a des diviseurs autres que 1 et lui-même) bien qu'il ait certaines propriétés en commun avec des nombres premiers, et un pseudo prime ne remplace pas un nombre premier, en particulier pour la cryptographie. Le fait que les pseudo-nombres premiers qui réussissent les tests probabilistes soient rares, fait que ces tests sont bons pour les grands nombres générés aléatoirement. Mais dire que les besoins OP peuvent être satisfaits par un pseudo prime est évidemment faux. Java a un premier chèque/générateur probabiliste, ce qui est probablement ce que vous vouliez dire. – MAK

Oui, c'est ce que je voulais dire – glebm

@Glex: Alors s'il vous plaît modifier votre réponse afin que ce ne soit pas trompeuse. – MAK

En PARI/GP:

randomprime([2^1023,2^1024])

Si vous souhaitez faire en mode 'bibliothèque'

#include <pari/pari.h> 
// ... 
randomprime(mkvec2(int2u(1023), int2u(1024)))

Source

2015-07-09 18:01:40 Charles

Vous ne spécifiez pas un contexte/langue/plate-forme .. si vous comme d'utiliser le système unix/linux-like et shell, vous pourriez envisager une solution impliquant la version OpenSSL> = 1.0.0:

$ openssl prime -generate -bits 1024 
140750877582727333214379261853877378646889234118675380673028200387281415297520423589261211081966230040412916644372766351028035798201654335110081318739796178745233127842988596480299276295476504358587725867882394416543075082108266054273016211760684113070285409887820598314292803190900634009988950624354964653677

Si vous obtenez le même résultat, il y a quelque chose qui ne va pas dans l'univers.

Ajoutez l'option -hex si vous aimez le système hexadécimal.

Source

2015-08-15 07:53:42 mykhal

Nombre premier aléatoire

Répondre

Questions connexes