Aide à la recherche des nombres premiers pour cryptosystème
-
22-09-2019 - |
Question
Je suis un étudiant à l'université et ont une mission qui nécessite de trouver un grand nombre de choix. On m'a donné l'algorithme suivant « simple » par le professeur pour trouver 2 probablement nombres premiers.
- générer un aléatoire et p, où 1
- confirmer que PGCD (a, p) = 1 est - c'est supposé supprimer les numéros Carmichael Edit (signifiait égal à 1)
- effectuer "exponentiation modulaire" si x ^ (p-1)% p = 1 où x commence à zéro et par incréments jusqu'à p-1 pour les deux p et
Exemple de la 3ème étape.
p = supposons 5
1 ^ 4% 5 = 1
2 ^ 4% 5 = 1
3 ^ 4% 5 = 1
4 ^ 4% 5 = 1
Cela montre que 5 est premier.
Je réalise à travers cette mission que le calcul des nombres premiers est pas une blague. Le problème que je vois avec l'algorithme ci-dessus est que si je devine un grand nombre et de les tester avec l'exponentiation modulaire, je pourrais être tentais de soulever un grand nombre à un grand nombre. Cela place un doute dans mon esprit. Je l'ai regardé dans déterministes et automates finis d'Eratosthène Sieve ainsi. Quelqu'un at-il des suggestions pour améliorer soit l'algorithme donné ou de fournir tout type d'assistance? Merci pour le temps.
La solution
L'algorithme que vous suivez est appelé Fermat test de primalité. Cependant, il y a plusieurs problèmes avec votre explication:
-
Vous dites "confirmer que PGCD (a, p) est <1". Cela n'a pas de sens que le GCD ne sera jamais inférieur à un. Ce que vous pouvez vérifier que PGCD (a, p) == 1. Si ce n'est pas 1, alors p n'est pas premier. Cela peut détecter un nombre Carmichael, mais peut-être seulement une petite chance de le faire.
-
La façon dont le test est effectué, est que pour une certaine valeur de p, vous choisissez plusieurs valeurs aléatoires d'un et de vérifier si un ^ (p-1)% p == 1. Si l'un d'entre eux est pas 1, alors p n'est pas premier. Les valeurs plus d'un que vous choisissez, plus votre précision.
-
Vous ne pouvez certainement pas vérifier pour tous valeurs de x comme vous le dites - car il y a trop de vérifier
.
-
Il est un moyen rapide pour effectuer exponentiation modulaire, même pour une grande base et exposant. Voir Wikipedia article . Vous aurez toujours besoin d'une méthode pour effectuer la multiplication et modulo sur les grands entiers.
-
Le Sieve d'Eratosthène est seulement utile pour trouver des petits nombres premiers.
-
Ce test peut déterminer à tort que le nombre Carmichael sont premiers. D'autres algorithmes tels que Rabin-Miller n'ont pas ce problème.
Autres conseils
assez simple en C #. Je ne sais pas si ce serait plus rapide en termes de vitesse.
bool IsPrime(long n)
{
if (n == 1)
{
return false;
}
if (n < 4)
{
return true;
}
if ((n % 2) == 0)
{
return false;
}
if (n < 9)
{
return true;
}
if ((n % 3) == 0)
{
return false;
}
long r = (long)Math.Floor(Math.Sqrt(n));
long f = 5;
while (f <= r)
{
if ((n % f) == 0)
{
return false;
}
if ((n % (f + 2)) == 0)
{
return false;
}
f += 6;
}
return true;
}
Il y a quelque temps j'ai écrit quelques fonctions en C # pour un usage personnel. J'espère que c'est bon pour vous
à long tmp public; public long [] = new tabnum longue [1];
priminum public void (longue NUM) { Resto à long; à long RISO;
// 2 is only number pair prime
tabnum[0] = 2;
for (tmp = 3; tmp <= NUM; tmp++)
{
if ((tmp % 2) == 0) continue;// if num it's pair is not prime
for (long Y = 0; Y < tmp; Y++)
{
riso = Math.DivRem(tabnum[Y], tmp, out Resto);
if (Resto == 0) break;
if(riso <= tabnum[Y])
{
Array.Resize(ref tabnum, tabnum.Length + 1);
tabnum[tabnum.Length - 1] = tmp;
List1.Items.Add(tmp.ToString("###,###"));
break;
}
}
}
}
retour suivant vraie fonction si le nombre est premier
private bool IsPrimo (ulong tmpNum) { ulong Y;
if (tmpNum == 2) return true;
if ((tmpNum % 2) == 0) return false;
for (Y = 2; Y <= tmpNum; Y++)
{
if ((tmpNum % Y) == 0) break;
if ((tmpNum / Y) <= Y) return true;
}
return false;
}