3

BBSアルゴリズムを理解するのを手伝ってください。私はこの実装を行いました：

class EmptySequenseError(Exception):                                  
    pass                                                              


class BlumBlumShub(object):                                           
    def __init__(self, length):                                       
        self.length = length                                          
        self.primes = e(1000)  # Primes obtained by my own Sieve of Eratosthenes implementation.                                                                            

    def get_primes(self):                                             
        out_primes = []                                               
        while len(out_primes) < 2:                                    
            curr_prime = self.primes.pop()          
            if curr_prime % 4 == 3:                                   
                out_primes.append(curr_prime)                         
        return out_primes                                             

    def set_random_sequence(self):                                    
        p, q = self.get_primes()                                      
        m = p * q                                                     
        self.random_sequence = [((x+1)**2)%m for x in range(self.length)]

    def get_random_sequence(self):                                    
        if self.random_sequence:                                      
           return self.random_sequence                               
        raise EmptySequenseError("Set random sequence before get it!")

いくつか質問があります。最初はライブラリを使いたくありませんrandom。あまりにも素朴です。私のシーケンスは増加しています。完全にランダムではありません。返されたシーケンスの増加を防ぐ方法は? そして、私はアルゴリズムの説明のこの部分を理解していません:

アルゴリズムの各ステップで、何らかの出力がx n+1から導出されます。出力は通常、 x n+1 のビット パリティか、x n + 1の 1つ以上の最下位ビットです。

意味を教えてください。

要約を編集:

  • アルゴリズムを修正しました。
  • en.wikipedia の引用に置き換えられた引用。
4

3 に答える 3

5 
    for x in range(self.length):                                  
        self.random_sequence.append((x ** 2) % m)

を生成するだけ[(x ** 2) % m for x in range(self.length)]で、おおよそ x n+1 = n 2 mod Mです。

アルゴリズムは次のようになります: x n+1 = x n 2 mod M

バージョンがどこで違うか分かりますか?

引用については、あなたはそれがどこからのものかは言いませんが、ウィキペディアには次のようにあります。

アルゴリズムの各ステップで、何らかの出力がx n+1から導出されます。出力は通常、 x n+1 のビット パリティか、x n + 1の 1つ以上の最下位ビットです。

これは、x n+1が次の反復のシードであることを意味しますが、返される疑似乱数ではありません。代わりに、戻り値は x n+1からそのビット パリティをカウントするか (反復ごとに 0 または 1 になります)、または上位ビットの一部のみを取得することによって導出されます。

于 2013-06-14T11:07:21.653 に答える
3

Blum Blum Shub については、『Handbook of Applied Cryptography』の第 5 章、セクション 5.5.2 で説明されています。その章には、乱数の生成に関する役立つ情報がたくさんあります。

于 2013-06-15T11:41:20.367 に答える