Сгенерировать большое простое число с указанными последними цифрами

Ответ 1

Я предполагаю, что единственный способ - сначала создать случайное число из 150 десятичных цифр, а затем добавить 28071 за ним, выполнив number = randomnumber * 100000 + 28071, а затем просто перетащить его с помощью чего-то вроде

while (!IsPrime(number))
    number += 100000;

Конечно, это может занять некоторое время, чтобы вычислить; -)

Ответ 2

Вы пытались просто генерировать такие цифры и проверять их? Я ожидал бы, что это будет приемлемо быстро. Основная плотность уменьшается только как логарифм числа, поэтому я ожидаю, что вы попробуете несколько сотен номеров, пока не нажмете премьер. ln(2^512) = 354, поэтому примерно одно число в 350 будет простым.

Грубо говоря, теорема о простых числах гласит, что если выбрано случайное число, близкое к некоторому большому числу N, вероятность его простого составляет около 1/ln (N), где ln (N) обозначает натуральный логарифм N Например, около N = 10000, примерно одно из девяти чисел является простым, тогда как около N = 1,000,000,000, только один из каждых 21 чисел является простым. Другими словами, средний разрыв между простыми числами вблизи N примерно равен ln (N)

(из http://en.wikipedia.org/wiki/Prime_number_theorem)

Вам просто нужно позаботиться о том, чтобы число было для ваших окончательных цифр. Но я считаю, что так же легко проверить, что последняя цифра не делится на 2 или 5 (то есть 1, 3, 7 или 9).

Согласно данным производительности, вы можете сделать около 2000 операций ModPow с 512-битными данными в секунду, а так как простой простой тест проверяя 2^(p-1) mod p=1, которая является одной операцией ModPow, вы должны иметь возможность генерировать несколько простых чисел со своими свойствами в секунду.

Итак, вы можете сделать (псевдокод):

BigInteger FindPrimeCandidate(int lastDigits)
{
    BigInteger i=Random512BitInt;
    int remainder = i % 100000;
    int increment = lastDigits-remainder;
    i += increment;
    BigInteger test = BigInteger.ModPow(2, i - 1, i);
    if(test == 1)
      return i;
    else
      return null;
}

И сделайте более обширные первичные проверки результата этой функции.

Ответ 3

Как сказал @Doggot, но начинайте с наименее возможного 150-значного числа, которое заканчивается 28071, означает 100000.... 0028071, теперь добавляйте его по 100000 каждый раз и для тестирования в первую очередь используйте мельник-рабин, как и код, который я предоставил здесь, он нуждается в некоторой настройке. Если возвращаемое значение истинно, сначала проверьте его на точное.

Ответ 4

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

Для каждого малого простого p вам нужно найти правильную отправную точку и шаг, учитывая, что в сите присутствует только 100000-й номер.

Для чисел, оставшихся в сите, вы можете использовать BigInteger.isProbablePrime(), чтобы проверить, является ли оно простым с достаточной вероятностью.

Ответ 5

Пусть ABCDE будет пятизначным числом в базе десять, которое вы рассматриваете. На основе , если ABCDE и 100000 взаимно просты, то существует бесконечно много простых чисел вида 100000 * k + ABCDE. Поскольку вы ищете простые числа, ни 2, ни 5 не разделили бы ABCDE в любом случае, таким образом ABCDE и 100000 будут взаимно просты. Таким образом, существует бесконечно множество простых чисел формы, которые вы рассматриваете.

Ответ 6

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

Не так наивно: сгенерировать случайное 512-битное число, а затем установить достаточные младшие биты, чтобы десятичное представление заканчивалось требуемой последовательностью. Затем продолжайте обычные тесты на примитивность.

Ответ 7

Давайте рассмотрим грубую силу. Взгляните на этот очень интересный текст под названием "Лотерея с простым номером":

• http://plus.maths.org/content/prime-number-lottery

Учитывая последнюю запись в последней таблице, существует ~ 2.79 * 10 ^ 14 простых чисел менее 10 ^ 16. Таким образом, примерно каждое 35-е число является простым в этом диапазоне.

EDIT: см. комментарий от CodeInChaos - если вы просто пройдете несколько тысяч 512-битных чисел с фиксированными 5-значными цифрами, вы найдете их быстро.

Ответ 8

Я переписал алгоритм грубой силы из мира int в BigDecimal один с помощью класса BigSquareRoot из http://www.merriampark.com/bigsqrt.htm. (Обратите внимание, что от 1 до 1000 говорят, что это точно 168 простых чисел.)

Извините, но если вы разместите там свой диапазон, то есть < 10 ¹⁵⁴; 10 ¹⁵⁵ -1 > , вы можете позволить своему компьютеру работать, и когда вы уйдете на пенсию, вы можете получить результат... это чертовски медленно!

Однако вы можете как-то найти хотя бы часть этого полезного в сочетании с другими ответами в этом потоке.

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

}