Blum-Blum-Shubを使うには、

• 適切な X0(あたりまえだけど 0 はだめ)
• 適度に大きい素数 p と q
• p - 1 と q - 1 の最大公倍数が 2

というのが重要じゃないかと、書きました。こんなもの手で求められないので、それを求める関数を書きます。

def makebbspq(max, debug=0):
    from random import seed, randint # randomモジュールを使います
    seed() # 現在時刻で初期化します
    g = 0 # GCD(whileループチェッカ)
    while g != 2: # gcd が 2にならなければおわるな
        p = randint(max/7, max) # max/7 から max までの整数が帰ってきます
        q = randint(max/7, max)
        pret = primes(p, p-500) # p-500 から p までの素数を求めます。31bit範囲なら500あれば大丈夫
        qret = primes(q, q-500)
        p = pret[-1] # 最後の素数を p, q とします
        q = qret[-1]
        g = gcd(p-1, q-1) # GCDを求めます
        if debug: print p, q, g, ('NG','OK')[g==2]
    x0 = randint(max/7, max) # x0を求めます。max が 0でない限り、non-zeroです。
    return p, q, x0

これで、そこそこな値(と思われる) p, q, x0 を準備できます。