OpenSSL の probable_prime 関数

OpenSSL の巨大整数の素数の候補を生成するとき、安全素数に限定せず、合同関係の限定もしない場合、 probable_prime 関数を使います。 そこの、候補からふるい落としをしている箇所の、 コメントの記述とコード自体が合っていません。

⇒ openssl/crypto/bn/bn_prime.c

            /*
             * check that rnd is not a prime and also that gcd(rnd-1,primes)
             * == 1 (except for 2)
             */
            if (((mods[i] + delta) % primes[i]) <= 1) {
                delta += 2;
                if (delta > maxdelta)
                    goto again;
                goto loop;
            }

コードの通りなら、 rnd ではなく rnd+delta ですし、 rnd+delta-1 と primes が互いに素でないときにふるい落とすため、 正しくは不等号です。 ついでに、互いに素ではないと書いたときのふるい落としの条件は負論理なので or です。

            /*
             * check that rnd+delta is not a prime or that gcd(rnd+delta-1,primes)
             * != 1 (except for 2)
             */

この部分が何をしているのか理解するために、 ruby でロジックを書き直してみます。 まず富豪バージョンです。 ふるい落としよりも、 選択する条件の方がわかりやすいので、それで書いてみます。 配列 small_primes は「最初の N 個の素数を求める Dijkstra の方法」 等で作ったものを使います。

# bits 長の奇数の素数候補 rnd を求める。 ここで、rnd と rnd - 1 は両方とも、
# small_primes = [2, 3, 5, 7, 11, 13, ..., 17863] の 2048 個の素数のうち
# 素数 2 を除いて、すべてに互いに素であるものを選ぶ。
# この条件を式で表すと、
# small_primes.all?{|x| x == 2 || (rnd.gcd(x)==1 && (rnd-1).gcd(x)==1) }
# である。
def probable_prime(bits, small_primes)
  centinel = 3 << (bits - 2)
  maxdelta = 0xffffffff - small_primes.last # 32 ビット・マシンの場合
  loop do
    # 最上位 2 ビットを 1 に、再下位 1 ビットを 1 にセットすることで
    # bits 桁の奇数をランダムに選ぶ
    rnd = centinel | rand(1 << (bits - 2)) | 1
    # rnd 以上の奇数を順に調べていき……
    0.step(maxdelta, 2) do |delta|
      # 2 以外のすべての小さな素数 x について、
      # rnd+delta と rnd+delta-1 の両方が互いに素である最初に見つかったものを選ぶ
      # 互いに素なので、 GCD は 1 になる
      if small_primes.all?{|x| x == 2 || ((rnd + delta).gcd(x) == 1 && (rnd + delta - 1).gcd(x) == 1) }
        rnd += delta
        # rnd が bits 桁のとき (桁あふれしていないとき)、rnd を候補として返す
        if (rnd >> bits) == 0
            return rnd
        end
        break # 桁あふれしてしまったときは、奇数のランダム選択からやりなおす
      end
    end
    # 範囲内の奇数の中から条件を満たすものが見つからなかったときも、奇数のランダム選択からやりなおす
  end
  raise 'ここには辿りつかない'
end

引用部分の if 文の条件式はふるい落とし条件なので、 ruby 版の一番内側の if 文の条件式の選択する条件を論理否定したものになっているはずです。

not small_primes.all?{|x| x == 2 || ((rnd + delta).gcd(x) == 1 && (rnd + delta - 1).gcd(x) == 1) }

変形できるか試してみましょう。 まずは、not を分配します。

small_primes.any?{|x| x != 2 && ((rnd + delta).gcd(x) != 1 || (rnd + delta - 1).gcd(x) != 1) }

互いに素ではない判定を GCD から剰余に置き換えます。 互いに素でないということは、割りきれることを意味するため剰余がゼロになります。

small_primes.any?{|x| x != 2 && ((rnd + delta) % x == 0 || (rnd + delta - 1) % x == 0) }

2 番目の合同式の両辺に 1 を足しても、意味が変わりません。

small_primes.any?{|x| x != 2 && ((rnd + delta) % x == 0 || (rnd + delta) % x == 1) }

被除数 rnd + delta も、 除数 x も両方共正であり、 除算の種類によらずに剰余はゼロ以上の正の数になります。 なので、2 つの等号を 1 つの不等式にまとめます。

small_primes.any?{|x| x != 2 && (rnd + delta) % x <= 1 }

ここまでのように巨大整数除算でいちいち剰余を求めなくても、合同式なのでループの外であらかじめ剰余を求め、小さな整数除算で計算しても意味は変わりません。

mods = small_primes.map{|x| rnd % x }
(0 ... small_primes.size).any?{|i| small_primes[i] != 2 && (mods[i] + delta) % small_primes[i] <= 1 }

さらに、 small_primes の先頭要素を必ず素数 2 にしておく暗黙の約束ごとをしておきます。 こうすることで、 添字範囲を 1 から始めて、 素数 2 を除外する条件判定を消せます。

mods = small_primes.map{|x| rnd % x }
(1 ... small_primes.size).any?{|i| (mods[i] + delta) % small_primes[i] <= 1 }

これが、ふるい落としの条件式です。 ちゃんと、 C 言語のコードの条件式に一致しています。

最後に、全体にあてはめてみます。 C 言語の方も、選択する条件式で書いた方が、ロジックをすっきりと書き下せるだろうとは思うのですが、 ふるい落とし条件で goto 文を駆使して記述してこそ、 OpenSSL らしいコードなのでしょう。 コメントとコードが一致しないのも味があって良いのではないでしょうか。

def probable_prime(bits, small_primes)
  centinel = 3 << (bits - 2)
  maxdelta = 0xffffffff - small_primes.last
  loop do
    rnd = centinel | rand(1 << (bits - 2)) | 1
    mods = small_primes.map{|x| rnd % x }
    0.step(maxdelta, 2) do |delta|
      #if (1 ... small_primes.size).all?{|i| (mods[i] + delta) % small_primes[i] > 1 }
      if not (1 ... small_primes.size).any?{|i| (mods[i] + delta) % small_primes[i] <= 1 }
        rnd += delta
        if (rnd >> bits) == 0
          return rnd
        end
        break
      end
    end
  end
  raise 'ここには辿りつかない'
end