0

我缺乏制作这个功能的数学技能。

基本上，我想返回 2 个随机素数，当它们相乘时，产生作为参数给出的位数 X。

例如：

如果我说我的 X 是 3，那么可能的解决方案是：p = 2 和 q = 3，因为 2 * 3 = 6（110 有 3 位）。

4

2 回答 2

3

这个陈述的一个问题是它首先要求两个“随机”素数。如果没有任何关于所需随机素数分布的明确声明，我们已经陷入困境。（这是一个经典悖论的开始，我们被要求生成一个“随机”整数。）

但是假设我们将语句更改为找到任意两个任意素数，这会产生具有给定位数 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 的素数。我会选择 p1 = 137。那么第二个素数因子必须是位于区间内的素数

[512 1023]/137
ans =
    3.7372    7.4672

因此是 5 或 7。

dec2bin(137*[5 7])
ans =
    1010101101
    1110111111
于 2013-01-13T16:10:30.203 回答
2

如果您知道位数，则可以生成一个数字 2^(x-2) < x < 2^(x-1)。然后取平方根并在它的任一侧找到最接近的素数。在大多数情况下，将它们相乘会得到一个正确范围内的数字。如果它太高，你可以直接在它的下侧取两个素数。

伪代码：

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 附加到末尾。

于 2013-01-13T14:36:36.700 回答