Как мне генерировать 2 случайных простых числа, которые при умножении дают число с X битами? (X дан в качестве аргумента))

Question

Мне не хватает математических навыков, чтобы сделать эту функцию.

в основном, я хочу вернуть 2 случайных простых числа, которые при умножении дают количество битов X, заданных в качестве аргумента.

например:

если я скажу, что мой X равен 3, то возможное решение будет таким: p = 2 и q = 3, потому что 2 * 3 = 6 (110 имеет 3 бита).

Answer 1

Проблема с этим утверждением состоит в том, что оно начинается с запроса двух "случайных" простых чисел. Без какого-либо явного заявления о распределении необходимых случайных простых чисел мы уже застряли. (Это начало классического парадокса, где нас просят сгенерировать "случайное" целое число.)

Но предположим, что мы изменили утверждение, чтобы найти любые два произвольных простых числа, которые дают желаемый продукт с заданным числом битов x. Ответ тривиален.

Множество чисел, у которых в двоичном представлении содержится ровно x битов, является полуоткрытым набором целых чисел [2^(x-1),2^x-1].

1. Выберите произвольное простое число, которое меньше или равно (2^x-1)/2. Назовите это p1.

2. Затем выберите второе простое число, которое лежит в интервале (2^(x-1)/p1,(2^x-1)/p1). Назовите это p2.

Должно быть верно, что p1*p2 будет в желаемом интервале.

Например, если x = 10, то произведение должно лежать в интервале [512,1023] набора целых чисел с ровно 10 битами. (Обратите внимание, что в этом интервале, по-видимому, 147 таких чисел, причем ровно два простых фактора.)

Шаг 1:

Выберите p1 в качестве любого простого числа, не превышающего 1023/2 = 511,5. Я выберу р1 = 137. Тогда второй простой фактор должен быть простым, который лежит в интервале

[512 1023]/137
ans =
    3.7372    7.4672

таким образом, либо 5, либо 7.

dec2bin(137*[5 7])
ans =
    1010101101
    1110111111

Answer 2

Если вы знаете количество битов, вы можете сгенерировать число 2^(x-2)

псевдокод:

x = bits
primelist[] = makeprimelist()
rand = randnum between 2^(x-2) and 2^(x-1)
n = findposition(primelist, rand)
do
    result = primelist[n]*primelist[n+1]
    n--
while result > 2^(x-1)

Обратите внимание, что числа, сгенерированные таким образом, всегда будут иметь "1" в качестве старшего значащего бита, поэтому было бы возможно сгенерировать число битов x-1 и просто прикрепить 1 к концу.