nombre premier aléatoire

Question

Comment puis-je générer rapidement un nombre premier aléatoire, qui est sûr 1024 peu de temps?

Answer 1

1. Génération 1024 bits aléatoires. Utilisez une source aléatoire qui est assez fort pour votre destination.

2. Définissez les plus élevés et les plus bas bits à 1. Cela fait qu'il n'y a pas zéros (le candidat de choix est assez grand) et il est un nombre pair (certainement pas le premier).

3. Test primalité. Si ce n'est pas un nombre premier, revenir à 1.

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

Answer 2

A l'aide d'une fonction de bibliothèque, comme OpenSSL. Il n'y a pas besoin d'écrire vous-même.

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

Answer 3

1024 est beaucoup. Êtes-vous sûr un premier probabiliste ne le fera pas? Premier générateur probabilistes fait partie de JDK

Answer 4

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

$ openssl prime -generate -bits 1024
140750877582727333214379261853877378646889234118675380673028200387281415297520423589261211081966230040412916644372766351028035798201654335110081318739796178745233127842988596480299276295476504358587725867882394416543075082108266054273016211760684113070285409887820598314292803190900634009988950624354964653677

Si vous avez obtenu le même résultat, quelque chose est très mal avec l'univers.

Ajouter option -hex si vous aimez le système hexadécimal.

Answer 5

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

Edit: Bien entendu, vous ne pouvez pas les générer tous si le mieux que vous pourriez réaliser est pseudo aléatoire à un coût de la mémoire haute. c'est pas bon si vous voulez la sécurité.

Answer 6

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)))