暗号計算機屋のブログ

なにか思いついたことを不定期に更新。

廃棄するHDDレコーダからHDD 80GBを回収

日立製作所 2003年製のHDDレコーダを放置していたがHDDが足りなくなったので、HDDレコーダから回収することに。 中を開けてみると、でてきたHDDはSAMSUNG製(韓国)だった。

日立すら買わない日立のHDDを誰が買うのだと思いつつ、日本のHDD事業について調べてみた。縮小傾向だが東芝がまだやっているようだ。少し調べたくらいで、どうこう言えるほどではない。

しかし、一般的な話として、強く思うことはある。

経営者からしてみれば、海外の安いHDDを導入しHDDレコーダの価格を下げたほうが、いいのはわかる。しかし、その結果、将来、HDD事業を撤退することになった。

経営者に、将来日本が困るから、HDDを買い支えるよう、指示する仕組みは、あるのだろうか? なければ、同じことが、繰り返される。 日本人が愚かな民だと思いたくはない。

海外製のHDDに、リモートでHDD上のファイルを改ざんしてウィルスが発生する仕組みがあるかもしれない。 海外のHDDの工場にいって、1台1台製造に付き合っていたら、トータルで、割高になってしまうとか、なりそうで怖い。 なにか事業をしようとして、HDDの信頼性の問題に気が付き、割高くらいでは、すまなくなって後悔しまくることにならないだろうか?

f:id:icf:20160823230244j:plain

3、5、7で割った余りを計算する演算器

はじめに

1999年に世界一高速なRSA暗号のLSIを開発したが、その後、いろいろ研究していたときに見つけたのが7で割った余りを高速に演算する論理だった。 今では高校の数学で整数の性質で習う合同式を使えば簡単に証明できるが、それは2014年以降の話で、2000年頃にはまだそういうものはなかった。

3で割った余りが何の役に立つの?

LSIではノイズや宇宙線によってビットが反転し正しく動作しないことがある。パリティによってチェックすることもあるが乗算器のビット反転はパリティでは不可能だ。 乗算器を2重化すればいいが、トランジスタ数が増大する。そこでレシジュという方法が用いられていた。乗数と被乗数の3で割った余りを乗算して、乗算結果と比較するのだ。 3で割った余りどうしの乗算なので2bitの乗算器程度のトランジスタ数でいいためトランジスタ数の増大を防げる。 このときあった3で割った余りを計算する演算器を5、7に応用したのが「3、5、7で割った余りを計算する演算器」です。 3で割った余りを計算してくれる演算器に証明がついていれば良かったのだが、そういう便利なものはなく、自分で証明するしかなかった。ちなみに15で割った余りも可能です。 「すべてがFになる(計算機工学版)」がなぜ計算機工学なのかは、そういう理由からです。

3、5、7で割った余りが何の役に立つの?

3ではなく5や7で割った余りを使えば乗算器の誤りを検出する精度が上がる。が、それはおいておいて 素数判定をするにはミラー・ラビン素数判定法のような確率的アルゴリズムでも時間のかかる処理です。 そういった時間のかかる素数判定の前処理として「3、5、7で割った余りを計算する演算器」を使えば素数判定を高速化できる、、、と思っていた。 事実、GNUのGMPというライブラリでmpz_nextprime()という関数は3、5、7のような小さい素数で割り切れるかをテストしている。 しかし与えられた数よりも大きい素数を探すのに毎回、3、5、7で割れるかを判定しているわけではなく、前回の結果を記録しておいて、 増分を計算して判定するため、「3、5、7で割った余りを計算する演算器」の高速性は活かされないことが判明した。 VHDLなどの論理シミュレータでレシジュのシミュレーションを高速化できるなどの超マイナーな用途は、見つけたが、みなさんにも 考えてもらえるといいかなぁと。

7で割った余りを高速に演算する方法

f:id:icf:20160711083634p:plain f:id:icf:20160711083654p:plain f:id:icf:20160711083708p:plain

7で割った余りが演算できることの証明

計算機なので2進数です。3bitづつにまとめて8進数で考えます。 8進数は

 {
\begin{align}
A_n×8^n + A_{n-1}×8^{n-1} + … + A_2×8^{2} + A_1×8^{1} + A_0 
\end{align}
}

と表せます。

 {
A_n×8^n + A_{n-1}×8^{n-1} + … + A_2×8^{2} + A_1×8^{1} + A_0 (mod\;7)\\
= A_n + A_{n-1} + … + A_2 + A_1 + A_0\\
  \;\; + A_n×(8^n-1) + A_{n-1}×(8^{n-1}-1) + … + A_2×(8^{2}-1) + A_1×(8^{1} -1) (mod\;7) 
}

mが1以上の任意の整数に対して次が成り立ので

 {
\begin{align}
8^m-1 &= 7×8^{m-1} + 8^{m-1} - 1\\
 &= 7×8^{m-1}+7×8^{m-2}+8^{m-2} - 1\\
 &= 7×8^{m-1}+7×8^{m-2}+7×8^{m-3}+8^{m-3} - 1\\
 &= 7×8^{m-1}+7×8^{m-2}+7×8^{m-3}+7×8^{m-4}+…+8-1 \\
 &= 7×8^{m-1}+7×8^{m-2}+7×8^{m-3}+7×8^{m-4}+…+7 \\
 &= 7×(8^{m-1}+8^{m-2}+8^{m-3}+8^{m-4}+…+1)
\end{align}
}
 {
= A_n + A_{n-1} + … + A_2 + A_1 + A_0\\
  \;\; + A_n×(8^n-1) + A_{n-1}×(8^{n-1}-1) + … + A_2×(8^{2}-1) + A_1×(8^{1} -1) (mod\;7)\\
= A_n + A_{n-1} + … + A_2 + A_1 + A_0 (mod\;7)
}

あとはAnからA0を7で割った余りを求めながら加算していけば答えが計算されます。 これは7以外の3、15、31でも同じ方法で証明できます。

3,5で割った余りは、どうするの?

3だけなら7と同じ方法でいいのですが15で割った余りを計算してから3と5で割った余りを計算すると 一度に3,5が計算できます。

GMPよりも高速に計算できる?

GMPとはThe GNU MP Bignum Library の略で多倍長計算を非常に高速に行うライブラリです。 ハードウェア向きのアルゴリズムですがソフトウェアで実装するとどうなるか、やってみました。

mpz_fdiv_ui(p,3)

これを代替する関数をC言語で作ってみました。WORDSは8バイト単位で1024bitなら16です。 3固定のコードですがmpz_export()でデータを取り出さないといけない分、代替関数が不利です。

unsigned long mod3(mpz_t p,int WORDS) {
    static unsigned long long w[64];
    unsigned long W;
    size_t count = WORDS;       
    mpz_export (w, &count, -1, sizeof(unsigned long long), 0, 0, p);
    W = (unsigned long)(w[0]%15);
    for(int j=1 ; j < WORDS ; j++) W += (unsigned long)(w[j]%15);
    return W%3;
}

恐らく環境によって違ってくると思いますがCore i5 4690Tでは2048bitくらいまでは 代替関数が高速です。それより長いbit長ではGMPに負けます。 Core i5のAVX2命令を使ってもう少し高速化したものが、次です。 はじめてAVX2命令を使ったので十分に高速化できてないかもしれないですが C言語の代替関数よりも20%くらい高速化されました。

unsigned long mod3_avx(mpz_t p,int WORDS) {
    static unsigned long long w[64] __attribute__((aligned(32)));
    unsigned long long W;
    __m256i W0,W1,W2,W3,W4,W5,W6,W7;
    size_t count = WORDS;
    mpz_export (w, &count, -1, sizeof(unsigned long long), 0, 0, p);
    W = 0;        
    for(int j=0 ; j < WORDS/16 ; j++) {
        W0 = _mm256_load_si256((const __m256i *)(w+j*16+0));
        W1 = _mm256_load_si256((const __m256i *)(w+j*16+4));
        W2 = _mm256_slli_epi64(W0,32);
        W += (unsigned long)(w[j*16+8]%15);
        W4 = _mm256_slli_epi64(W1,32);
        W += (unsigned long)(w[j*16+9]%15);
        W3 = _mm256_srli_epi64(W0,32);
        W += (unsigned long)(w[j*16+10]%15);
        W5 = _mm256_srli_epi64(W1,32);
        W += (unsigned long)(w[j*16+11]%15);
        W6 = _mm256_srli_epi64(W2,32);
        W += (unsigned long)(w[j*16+12]%15);
        W7 = _mm256_srli_epi64(W4,32);
        W += (unsigned long)(w[j*16+13]%15);
        W0 = _mm256_add_epi64(W3,W6);
        W += (unsigned long)(w[j*16+14]%15);
        W1 = _mm256_add_epi64(W5,W7);
        W += (unsigned long)(w[j*16+15]%15);
        W2 = _mm256_add_epi64(W0,W1);
        W += _mm256_extract_epi64(W2,0);
        W += _mm256_extract_epi64(W2,1);
        W += _mm256_extract_epi64(W2,2);
        W += _mm256_extract_epi64(W2,3);
    }
    return W%3;
}

最後に

ここにあるような余りを求める計算など整数の性質が実社会で何の役に立つか? 僕の経験を話します。 IBMの暗号LSIを買ってきて日立の大型コンピュータの暗号装置として製品化することがあった。 国内向けの需要で暗号LSIから秘密鍵をバックアップできる必要があった。 しかしIBMが、その方法を教えてくれるはずもなかった。 なぜなら秘密鍵の盗難の方法を教えるのと同じだからだ。 別の暗号装置にリストアすることはできないが、同一の暗号装置ならバックアップできる方法はあった。 暗号装置にRSA公開鍵暗号を設定することで、それが可能になる。 説明は省略するがRSAの鍵は周期が大きくなるように作る。 そこに敢えて1とnを繰り返す周期の鍵を設定する。 暗号装置内部で生成される乱数によって1かnかになる。確率50%で1になる。 1であることがわかれば、それを利用してバックアップする方法が見つかった。 確率50%では、何度か繰り返せば、普通にバックアップが可能だ。

この話が整数の性質の学習の動機付けになればと思います。

すべてがFになる (計算機工学版)

【すべてがFになる】「すべてがFになる (計算機工学版)」イラスト/izuna [pixiv]