0

この関数を作成するための数学のスキルがありません。

基本的に、乗算すると、引数として指定されたビット X の数を生成する 2 つのランダムな素数を返したいと考えています。

例えば：

X が 3 だとすると、考えられる解決策は次のようになります。

4

2 に答える 2

3

このステートメントの問題は、2 つの「ランダムな」素数を要求することから始まることです。必要なランダム素数の分布に関する明示的な記述がなければ、すでに行き詰まっています。(これは、「ランダムな」整数を生成するよう求められる、古典的なパラドックスの始まりです。)

しかし、ステートメントを任意の 2 つの任意の素数を見つけるように変更すると、指定されたビット数 x で目的の積が得られます。答えは簡単です。

バイナリ表現で正確に x ビットを含む数値のセットは、半開整数セット [2^(x-1),2^x-1] です。

  1. (2^x-1)/2 以下の任意の素数を選択します。それを p1 と呼びます。

  2. 次に、間隔 (2^(x-1)/p1,(2^x-1)/p1) にある 2 番目の素数を選択します。それを p2 と呼びます。

p1*p2 が目的の間隔内にあることは true でなければなりません。

たとえば、x = 10 の場合、積は [512,1023] の区間 (正確に 10 ビットの整数のセット) にある必要があります。(注意してください、その間隔には明らかに 147 のそのような数があり、正確に 2 つの素因数があります。)

ステップ1：

1023/2 = 511.5 以下の任意の素数として p1 を選択します。p1 = 137 を選びます。次に、2 番目の素因数は、間隔内にある素数でなければなりません。

[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) を生成できます。次に、平方根を取り、その両側にある最も近い素数を見つけます。それらを掛け合わせると、ほとんどの場合、正しい範囲の数値が得られます。高すぎる場合は、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 を付けるだけで済みます。

于 2013-01-13T14:36:36.700 に答える