# bigint

2003年12月10日 JavaScriptで巨大整数演算を行うためのライブラリ bigint の高速化を行っています。手元のMozilla で、 bigint v0.4 では、2の800乗を計算するのに約8秒かかりますが、開発中の v0.5 では20ミリ秒程度、という劇的な高速化が記録されています（8秒→0.02秒ですよ！）。逆にいえば bigintライブラリの速度についてこれまで再三不満を言っていたのも、納得のいくことでしょう。

古い bigint v0.2 では2の1000乗の計算に43.5秒かかったが、現在、2の1000乗はMozillaで60～300ミリ秒程度、MSIEなら30ミリ秒だ。 3011桁ある2の10000乗をMozillaでは8～9秒、MSIEではわずか1900ミリ秒で求めることができる。これは2, 4, 8, 16, 32...という倍倍を1万項まで続けた結果のことである。（法で簡約しない「生の掛け算」なので、べき剰余ならもっと速いはず。）

2の1万乗を求めるデモ（これはさらにずっと高速化されました。）

最初はとりあえずそのプログラムが走ることが第一目標で、走らないことには高速化などできません。「4つの4」もバージョンアップのたびに劇的に高速化しました。さしあたっては、JavaScriptの上でRSAをもっと快適に動かしたいです。これまでの実演に使った bigint は特にRSA用にチューンアップしたわけではない汎用ライブラリだったので、高速化の余地はあちこちにあると思っています。

2003年12月11日 2進展開の高速化です。従来の bigint 0.4 では、例えば10進50桁の整数を2進展開するのに、 MSIEで約1450ミリ秒もかかっていました。それが今では10～20ミリ秒です。まだ細部のチューンアップは完了していませんが、これは幸先が良いことです。素数性テストなどで繰り返し二乗法を行うのに、いったん二進展開しているので、これが速くなると、だいぶ全体が速くなるはず。

でたらめに作った10進400桁、1329ビットの整数を二進展開するデモです。これだけ巨大でも500ミリ秒台でいけます。

400桁の整数を2進展開（手元ではMozilla2秒、IE0.5秒）

内部のアーキテクチャで、従来は掛け算してもオーバーフローしないように、10進7桁単位で動いていましたが、足し算などは10進15桁でやってもあふれません。2進展開も7桁ずつから15桁ずつに変更することでも、約40%高速化しています。

2003年12月13日 RSA128ビット鍵生成、高速化版（アルファ版）。まだ細部は詰めてません。確率的なので状況によりますが、 IEで10～20秒程度、Mozillaで20～40秒程度で、鍵を生成できます。 128ビットでこれくらいだと、512ビットまでJavaScriptでそこそこいけると思います。遅くてもよければ、実際に広く使われている1024ビットのPGPを、 JavaScript上でエミュできるかも……。

ECCなら、同じ強さでもっと速いので、 JavaSript上でまじめに実用を考えるならそっちのほうがいい。しかし、RSAと違って、ECCの場合、「運用」はJavaScript上でできるが、「設計」は難しい（手元の実験では、今のところまだ24ビット）。ほかで設計したもっと大きいECCをJavaScript上で動かすことはできるだろうが、最初から最後までJavaScriptだけで、は難しい。一方、RSAは、最初から最後までJavaScript上で実演できる。

2003年12月13日 RSA128ビット鍵生成、高速化版（アルファ版その2）です。割り算のアルゴリズムがめちゃくちゃだったので、書き直しました。まだ完全でなく、特殊なケースにおいて、割り算を間違えます。このデモに影響する確率は極めて低いです。トータルで前日比数割のスピード増加で、所要時間はIEで5～20秒程度、Mozillaで20～30秒程度。まだ細部は詰めていませんが、だいたい5～10秒で鍵が作れると、速いと感じます。もう次の256ビットには王手をかけたと思っています。

約300桁までは、JavaScriptの数値として有効ですが、16桁以上では精度が保証されません。 16桁以上では特別な考慮が必要です。

例えば、2の53乗は16桁の整数 9007199254740992 で、それより1大きい 9007199254740993 で割れば商は0のはずだが、 JavaScriptでは精度の関係で、この商が1と出る。計算上の商が実際の商より1大きくなる例です。

また 144115188075855876 は 144115188075855870 と認識され、末尾の6が0になるが、 48038396025285292 は 48038396025285300 と認識され、末尾の292が300に丸められる。前者は後者のちょうど3倍の数だが、前者を後者で割ると、 JavaScriptでは、2.999…台の数になる。本当の商は3。floorをとると計算上の商が実際より1小さくなる例です。

以上のように、非常に小さい数εがあって、商 q の小数部分がεより小さければ、本当の商の整数部分は計算より1小さいかもしれない。小数部分が1-ε以上だったなら、本当の商の整数部分は計算より1大きいかもしれない。筆算のように商を1桁ずつ求める実装では、さらに、商に10が立つ可能性があることに注意。 10倍に非常に近いが実際には9倍しか引けないケースで、浮動小数点演算の商が9.999999…となって丸めて10になる場合です。

15桁までなら、数値計算は常に正しいが、割る数が15桁ある場合、例えば商に9が立つと、内部的に16桁の演算になる。

割る数が15桁以上ならすべて文字列として、精度が失われないように、巨大整数を自力処理する。

割る数が14桁までなら、割られる数が巨大でも、割る数は数値として数値演算を利用して巨大除法が実装でき、それは前者の文字列による実装より二倍以上高速。また、従来の bigint v0.4 より、ざっと10倍速い。特に、エラトステネスのふるいで小さい約数がないことを見る操作が高速化されるから、RSAの鍵生成の大部分を占める「予選」が速くなり、 RSAの鍵生成は高速化される。割る数が15桁以上では、一般には bigint v0.4 より高速だが、例外として、あまり巨大でないときや、除数と被除数の桁数が近いときは、従来のほうがやや速い。（この問題は後に解決されました。）

2003年12月14日 RSA128ビット鍵生成、高速化版（アルファ版その3）です。前日比、さらに1～2割は速くなったかな？　手元では、IEで5～10秒、運がいいと3秒を切りました。 MozillaのJavaScriptは少し遅いです。確率的アルゴリズムなので運も大きいです。

今回はラップタイムを表示させています。手元での時間ですが、この規模のSPRPテストは底1つにつき400ミリ秒かかるので、予備審査と底2つでその3倍=1.2秒くらいかかります。素数2つなら2.5秒はかかる計算です。予備審査のふるいを1万までやると500ミリ秒以上かかってました。ミラーテストとコストが逆転しているので、ふるいは5000までにしました。乗算表を作るのがけっこうコストがかかるようなので、同じ乗算表を二度作らないようにしました。このへん、まだ微妙に改善できる場所があります。

大きな数の話: JavaScriptで、浮動小数点として扱える数値の限界は、2の1024乗よりわずかに小さい値で、10進308桁だ。したがって、割る数が307桁以上のときは、直接は浮動小数点演算できないので、先頭の何桁かを切り出して概算するか、あるいは、文字列の比較として数値の比較を行い商を求める。文字列を使う方法は浮動小数点演算よりやや遅いが、劇的には遅くない。これも含めて割り算のアルゴリズムの問題に対応しました。数百桁同士の割り算でも、商・剰余とも速いです。bigint 0.5 自体は、まだまだ開発途上のアルファです。古いコードそのままコピーの場所のつぎはぎがあって、まだごちゃごちゃしています。

2003年12月14日 RSA128ビット鍵生成、高速化版（アルファ版その4）です。（バグがあります。） 14桁以内で割って商は不要で剰余だけ求めればいい場合のアルゴリズムを高速化、エラトステネスのふるいが爆速になったので、1万までふるうように戻しました。トータルで体感できる速度改善ができました。運が悪くても、大半は10秒以内。ミラーテストで数回失敗しても、なお5秒前後。ミラーテストの失敗がないと1秒台も出ます。遅いMozillaでも10秒程度です。

2003年12月15日ちなみに倍のRSA256（遅い）。10～20秒くらいかかります。ミラーテストの失敗回数が増える＝素数の分布が薄くなることが時間コストに跳ね返ってきます。（128ビットとまったく同じライブラリ。）JavaScriptといえども生成される鍵は80桁なので、 Cを使おうがJavaを使おうが尋常な努力では分解できないでしょう。

さらに、時期尚早ですがRSA512。1分程度。160桁ですので、軍事機密はともかく、銀行取引に使えるくらい強力です。ジマーマンはこれを実装して逮捕されましたが（PGP）、それが今ではJavaScript…

2003年12月15日 RSA128ビット鍵生成、高速化（その5）です。法が15桁以上のときの剰余演算 (_mod_typeF)を改善、ボトルネックであったミラー・ラビンのテストが2～3倍に高速化されました。これにより、所要時間はIEで最短1秒を切り、ミラーテストに何度も失敗しても5秒程度でけりがつきます。 Mozillaでもそれなりに十分に体感できる速度改善がありました。

巨大な法に対する _mod_typeF は、一度に14桁みていますが、一度に15桁見たら7%程度は高速化できるはずですが、そのためには、ある問題を解決しなければならず、このデモの場合、40桁程度なので、14ずつでも15ずつでもどっちにしてもほとんど割り算の数を減らせません。

これでアルファテストは、ほぼ終了です。

2003年12月16日 RSA128 Test (alpha 9)。速度に関係しないバグ修正だけ。ミラーテストの剰余演算にあと数パーセントの高速化の余地があることが分かっている。筆算の割り算を考えると、一度に商を1桁ずつ求めて、被除数が1桁ずつ減っていく。剰余演算では商はいらないので、一度に14桁ずつ消せる。例えば40桁の数Aを20桁の数Bで割るとき、 Aを頭から34桁（割る数の桁数プラス14）とってA1とする。残りの6桁はA2とでもしておく。浮動小数点演算でA1/Bを求め、結果の整数部分のB倍をA1から引くと、残りは浮動小数点演算が正しいと仮定してB未満になる（Bで割った余りだから）。 Bは20桁だから、この1ステップで、34桁あったものが20桁以下になる。それにA2をつなげて同じことをやれば、 2回の割り算で剰余が求まる。 Aがもっと長いことを考えると、14桁ずつと言わず15桁ずつ消せたら都合がいい。 JavaScriptの有効数字は16桁しかないので、被除数と除数の桁数差15では、一般に浮動小数点商の整数部分の末尾の位は保証されない。だから「有効数字的に大丈夫なら15桁ずつやって、だめなら14桁ずつ」というふうに割り算のやりかたを1ステップごとに変更するか、または「15桁ずつに決め打ちして、末尾はいつも信用できないものとして扱う」という方法が考えられる。今のところ、除数と被除数の桁数差を14か15か切り替える方式は、切り替えるための条件判断の時間コストで、節約できたステップ数が相殺されてしまう。 15桁ずつ決め打ち方式でも、末尾の誤差処理が煩雑になるので、なかなか一筋縄ではいかない。誤差が大きいと「A1-B×浮動小数点演算で求めた商」がB未満まで減らず、一気に15桁消せないので、14桁ずつやるのと同じことになってしまう。それでも、十分に大きな確率で「A1-B×浮動小数点演算で求めた商」がB未満になってくれれば、例えば平均14.5桁ずつ消せることになって、 14桁ずつ消すより数パーセント、ステップを節約できる。

[index]