se demandait comment il est-il possible de générer un nombre de 512 bits (155 chiffres décimaux), dont cinq derniers chiffres décimaux sont spécifiés / fixes (par exemple, *** 28071) ??
Les principes de générer des nombres premiers simples sans aucune spécification sont tout à fait compréhensibles, mais mon cas va plus loin.
Toute astuce pour, au moins, où dois-je commencer?
Java ou C # est préférable.
merci!
8 Réponses :
Je suppose que le seul moyen serait de générer un nombre aléatoire de 150 chiffres décimaux, puis appendez le 28071 derrière celui-ci en faisant bien sûr, cela pourrait prendre un certain temps à calculer; -) numéro = aléatoire * 100000 + 28071 alors brut force la force avec quelque chose comme
Ne serait pas aussi lent que vous n'avez besoin que d'essayer quelques centaines de fois.
@CODEINCHAOS Ce n'est pas que cela n'a besoin que de quelques chèques, c'est que la vérification ISPRIMe sur un si grand nombre va prendre beaucoup de temps.
Il est lent si Isprime vérifie exactement le nombre premier. Le test de phase est meilleur.
J'ai estimé que le temps comme inférieur à 100 ms pour le cas commun (non prime) et si ce test réussit, vous pouvez effectuer un test lent mais complet.
C'est ce que j'ai fait. Brute forcée le nombre = randomnumber * 100000 + 28071 avec ispobableprime. Était assez rapide.
Avez-vous essayé de générer de tels nombres et de les vérifier? Je m'attendrais à ce que cela soit acceptable. La densité principale ne diminue que comme logarithme du nombre, de sorte que je m'attendais à ce que vous essayiez quelques centaines de chiffres jusqu'à ce que vous atteigniez une prime. À peine parlant, le théorème de nombres premiers indique que si un nombre aléatoire à proximité d'un grand nombre N est sélectionné, le risque d'être primordial est environ 1 / ln (n), où ln (n) dénote le logarithme naturel de n . Par exemple, près de N = 10 000, environ un chiffre sur neuf est préféré, tandis que près de N = 1 000 000 000, un seul nombre sur 21 est prime. En d'autres termes, l'écart moyen entre les nombres premiers près de N est grossièrement ln (n)
(de http://en.wikipedia.org/wiki/ Prime_number_theorem ) Il vous suffit de prendre soin d'un numéro de votre chiffre final. Mais je pense que c'est aussi facile que de vérifier que le dernier chiffre n'est pas divisible par 2 ou 5 (c'est-à-dire qu'il est 1, 3, 7 ou 9). selon Donc, vous pourriez faire (pseudocode): et faire des chèques premiers plus vastes sur le résultat de cette fonction. ln (2 ^ 512) = 354 Ainsi, environ un numéro en 350 sera primordial.
2 ^ (p-1) MOD P = 1 qui est une opération MODPOW, vous devez être capable de générer plusieurs nombres premiers avec vos propriétés par seconde.
Vous pouvez prolonger l'un des Méthodes standard pour générer de grands nombres premiers en ajoutant une contrainte supplémentaire, C'est-à-dire que les 5 derniers chiffres décimaux doivent être corrects. Naïvement, vous pouvez simplement ajouter ceci comme test supplémentaire, mais il augmentera le temps nécessaire pour trouver un prime approprié de 10 ^ 5.
Non-SO-Nays: Générez un nombre aléatoire de 512 bits, puis définissez suffisamment de bits à faible ordre de sorte que la représentation décimale se termine par la séquence requise. Puis continuez avec les tests de primalité normaux.
considérons la force brute. Jetez un coup d'œil à ce texte très intéressant appelé "la loterie de nombres premiers":
Vous pouvez simplement essayer les chiffres avec les bons chiffres d'extrémité. Et pour 512 bits Nombres tous les 350ème et non 35ème numéro est préféré.
Vrai, merci pour la correction et les informations 512 bits, je vais éditer!
Comme @Doggot dit, mais commencez par un nombre au moins possible de 150 chiffres qui se termine par 28071, signifie 100 000 .... 0028071, ajoutez-le maintenant avec 100 000 à chaque fois et que les tests utilisent principalement Miller Rabin comme le code que j'ai fourni < Un href = "https://stackoverflow.com/questions/4236673/sample-code-for-fast-primalité-testing-in-c/4236870"> Ici , il a besoin d'une personnalisation. Si la valeur de retour est vraie, vérifiez-la exactement.
Vous pouvez utiliser un tamis contenant uniquement des numéros satisfaisant à votre état spécial pour filtrer les nombres divisibles par de petits nombres premiers.
pour chaque petit Prime Pour les chiffres qui survivent au tamis, vous pouvez utiliser p Vous devez trouver le point de départ correct et étape en tenant compte que seul chaque numéro 100000e est présent dans le tamis.
biginteger.isprobableprable () pour vérifier s'il est primordial avec une probabilité suffisante.
J'ai réécrit l'algorithme de force brute à partir du monde code> monde au Désolé, mais si vous y placez votre gamme, c'est-à-dire 154 sup>; 10 155 sup> -1>, vous pouvez laisser votre ordinateur fonctionner et quand vous avez pris la retraite, vous pouvez avoir le résultat ... c'est sacrément lent! P> Cependant, vous pouvez en quelque sorte Trouvez au moins une partie de cette partie utile en combinaison avec les autres réponses de ce fil. P> BigDecimal code> un à l'aide de la classe BigSquarreroot code> de la classe http://www.merriampark.com/bigsqrt.htm . (Notez que de 1 à 1000 il est dit exactement 168 primes.)
package edu.eli.test.primes;
import java.math.BigDecimal;
public class PrimeNumbersGenerator {
public static void main(String[] args) {
// BigDecimal lowerLimit = BigDecimal.valueOf(10).pow(154); /* 155 digits */
// BigDecimal upperLimit = BigDecimal.valueOf(10).pow(155).subtract(BigDecimal.ONE);
BigDecimal lowerLimit = BigDecimal.ONE;
BigDecimal upperLimit = new BigDecimal("1000");
BigDecimal prime = lowerLimit;
int i = 1;
/* http://www.merriampark.com/bigsqrt.htm */
BigSquareRoot bsr = new BigSquareRoot();
upperLimit = upperLimit.add(BigDecimal.ONE);
while (prime.compareTo(upperLimit) == -1) {
bsr.setScale(0);
BigDecimal roundedSqrt = bsr.get(prime);
boolean isPrimeNumber = false;
BigDecimal upper = roundedSqrt;
while (upper.compareTo(BigDecimal.ONE) == 1) {
BigDecimal div = prime.remainder(upper);
if ((prime.compareTo(upper) != 0) && (div.compareTo(BigDecimal.ZERO) == 0)) {
isPrimeNumber = false;
break;
} else if (!isPrimeNumber) {
isPrimeNumber = true;
}
upper = upper.subtract(BigDecimal.ONE);
}
if (isPrimeNumber) {
System.out.println("\n" + i + " -> " + prime + " is a prime!");
i++;
} else {
System.out.print(".");
}
prime = prime.add(BigDecimal.ONE);
}
}
}
Soit ABCDE être le numéro de cinq chiffres dans la base dix, que vous envisagez. Basé sur Théorème de Dirichlet sur les progressions arithmétiques , si ABCDE et 100000 sont coprime, alors il y a infiniment Beaucoup de nombres premiers de la forme 100000 * K + ABCDE. Depuis que vous recherchez des nombres premiers, ni 2 ni 5 diviseraient l'ABCDE de toute façon, ABCDE et 100000 sont coprime. Donc, il y a
Oui, mais le premier k qui entraîne un premier peut être arbitrairement important. Large comment? Dépend de l'ABCDE. Vous devez donc faire une recherche de force brute de k et le test de primalité coûteux habituel pour chaque candidat k .
Cela semble difficile, sinon impossible sans bruteforcing à travers les primes de 155 chiffres et en vérifiant chacun. Question intéressante cependant: p
En outre, cette question peut être plus adaptée à math.stackexchange.com
Ne faites pas de brute à travers les primes, la bruteforce à travers des chiffres remplissant le critère et les vérifier pour les nombres premiers. Cela ne devrait pas être si lent puisque la densité première est plutôt élevée.
@Thejh: Vous ne pouvez pas tamis jusqu'à 10 ^ 155.
Merci tout le monde pour la contribution! Problème résolu pour l'instant.