Эффективно генерировать одно случайное простое число в диапазоне - PullRequest
Новая
       11

Эффективно генерировать одно случайное простое число в диапазоне

0 голосов
/ 26 апреля 2019

Мне нужно получить только одно случайное простое число в диапазоне [2, n ^ 2], где n может быть очень большим (от 10 ^ 9 до 10 ^ 32). Я знаю эти домашние вопросы «как печатать простые числа в заданном диапазоне», «сито Эратосфена» и т. Д.

Я хочу, если возможно, избежать вычисления всех простых чисел и выбрать случайное число.

Я также не уверен, что выбор случайного числа из диапазона и проверка на простоту - это элегантный / эффективный способ решения этой проблемы.

Это не имеет ничего общего с целями безопасности. Это всего лишь часть реализации алгоритма (попытка реализовать), которая проверяет, являются ли два очень больших файла (> 1 ТБ) идентичными или нет.

Есть идеи, как получить одно определенно простое случайное число с акцентом на производительность?

EDIT Очень наивная и упрощенная реализация того, что я пытаюсь сделать: 

import java.math.BigInteger;
import java.util.stream.Collectors;

public class NewClass1 {    

    public static void main(String[] args) {
        //imagine this is my content of first file which is not at the same place as file two
        String file1 = "RDNZL";        
        //convert the content to bits
        file1 = toBits(file1); // 0101001001000100010011100101101001001100  

        //convert bits to number
        BigInteger  x = new BigInteger (file1, 2); //353333303884

        long p = 1187;  // select a random number between 2 and 1600 (String length * 8 bits = 40)
        // send p and x % p to validiate,
        long xMp = x.mod(BigInteger.valueOf(p)).longValue(); 
        System.out.println(check(p, xMp));
    }
    public static String toBits(String file){
        //convert each char to 8 bits and concat to string
        //just for simplification, i'am going to find a better way to solve this
        return file.chars().boxed()
                .map(Integer::toBinaryString).map(e->String.format("%8s", e).replace(' ', '0'))
                .collect(Collectors.joining("")); 
    }
    public static boolean check(long p, long xMp){
        //the other file which is somewhere else, in the cloud etc. 
        String file2 = "RDNZL";        
        file2 = toBits(file2); 

        BigInteger  y = new BigInteger (file2, 2); 
        long yMp = y.mod(BigInteger.valueOf(p)).longValue();
        return yMp == xMp;
    }
}

Если yMp! = XMp со 100% -ной достоверностью, файлы отличаются, если не бесконечно малый шанс того, что алгоритм не распознает, что они различаются.

Ответы [ 2 ]

3 голосов
/ 26 апреля 2019

Используйте BigInteger и его метод nextProbablePrime(). 

public static BigInteger randomPrime(int numBits) {
  BigInteger max = BigInteger.ONE.shiftLeft(numBits);
  BigInteger prime;
  do {
    BigInteger integer = new BigInteger(numBits, ThreadLocalRandom.current()); // Pick a random number between 0 and 2 ^ numbits - 1
    prime = integer.nextProbablePrime(); // Pick the next prime. Caution, it can exceed n^numbits, hence the loop
  } while(prime.compareTo(max) > 0);
  return prime;
}

Альтернативой может быть использование конструктора BigInteger​(int bitLength, int certainty, Random rnd), но он найдет числа с точным bitLength битом, что неудобно, поскольку оно не опускается ниже n ^ (bitLength - 1).

0 голосов
/ 26 апреля 2019

Вероятность найти простое число в точке x составляет 1 / ln (x). В вашем случае это n² с n = 10 ^ 32. Таким образом, вероятность составляет ln (10 ^ 64) или примерно 1/150. Это означает, что вы должны тестировать в среднем около 150 чисел, пока не найдете простое число.

У меня нет Java, но я могу дать вам результат из Python, основанный на тесте PSW на простоту . Кредиты идут на @ primo от Codegolf , особенно этот ответ . 

start = time()
n = next_prime((10**32)**2)
end = time()
print (n, " calcualted in ", end-start)

10000000000000000000000000000000000000000000000000000000000000057 calcualted in  0.00302 sec

Так что да, это возможно эффективным способом в то же время.

Результат подтверждается Wolfram Alpha .

...