Помощь в поиске простых чисел для криптосистемы

Question

Я учусь в колледже и имею задание, которое требует нахождения больших простых чисел. Профессор дал мне следующий «простой» алгоритм для нахождения 2 вероятных простых чисел.

1. генерирует случайные a и p, где 1 подтвердите, что gcd (a, p) = 1 - это предполагает удаление чисел Кармайкла. Edit (означающее 1)
2. выполнить "модульное возведение в степень" если x ^ (p-1)% p = 1, где x начинается с нуля и увеличивается до p-1 как для р, так и для

Пример 3-го шага.

предположим, что p = 5

1 ^ 4% 5 = 1

2 ^ 4% 5 = 1

3 ^ 4% 5 = 1

4 ^ 4% 5 = 1

Это показывает, что 5 - простое число.

Благодаря этому заданию я понимаю, что вычисление простых чисел - не шутка. Проблема, которую я вижу с вышеупомянутым алгоритмом, состоит в том, что, если я угадываю большие числа и проверяю их с модульным возведением в степень, я мог бы пытаться поднять большое число до большого числа. Это ставит под сомнение мой разум. Я также изучил детерминированные конечные автоматы и сито Эратосфена. У кого-нибудь есть предложения по улучшению данного алгоритма или оказанию какой-либо помощи? Спасибо за время.

Answer 1

Алгоритм, который вы используете, называется тестом примитивности Ферма . Однако в вашем объяснении есть несколько проблем:

• Вы говорите «подтвердите, что gcd (a, p) <1». Это не имеет смысла, поскольку gcd никогда не будет меньше единицы. Вы можете проверить, что gcd (a, p) == 1. Если это не 1, то p не простое число. Это может обнаружить числа Кармайкла, но может иметь лишь небольшой шанс сделать это. </p>

• Способ проведения теста заключается в том, что для определенного значения p вы выбираете несколько случайных значений a и проверяете, является ли ^ (p-1)% p == 1. Если одно из них не 1, то р не простое число. Чем больше значений вы выберете, тем выше будет ваша точность.

• Вы, конечно, не можете проверить все значения x, как вы говорите - поскольку их слишком много для проверки.

• Существует быстрый способ выполнения модульного возведения в степень, даже для большой базы и экспоненты. См. Статью Википедии . Вам все еще понадобится метод для умножения и по модулю больших целых чисел.

• Сито Эратосфена полезно только для поиска небольших простых чисел.

• Этот тест может неправильно определить, что числа Кармайкла являются простыми. Другие алгоритмы, такие как Рабин-Миллер , не имеют этой проблемы.

Answer 2

Довольно просто в C #. Я понятия не имею, будет ли это быстрее с точки зрения скорости.

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

Некоторое время назад я написал некоторые функции на C # для личного использования. Я надеюсь, что это хорошо для вас

публичная длинная тмп; public long [] tabnum = new long [1];

public void priminum (длинный NUM) { долгий ресто; длинный рисо;

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

}

следующая функция возвращает true, если число простое

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;

}