Aide à la recherche des nombres premiers pour cryptosystème

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.

1. générer un aléatoire et p, où 1
2. confirmer que PGCD (a, p) = 1 est - c'est supposé supprimer les numéros Carmichael Edit (signifiait égal à 1)
3. 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.

Answer 1

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.

Answer 2

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;
    }

Answer 3

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;

}