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桁ずつ消すより数パーセント、ステップを節約できる。
2003年12月17日 bigint.js v0.5 beta1 剰余演算で15桁ずつ消す方法が見つかり、ミラー・ラビンテストが128ビットで5%程度、256ビットでは10%程度、 高速化しました。（商が間違っているかもしれないのを承知で割り算の途中の引き算をとにかくやってみて、 引けなかったら商を1小さくするという単純な考えが、いちばん高速で、安全のようです。商を1減らす作業は、 途中計算が終わっているため、実際には足し算1回の手間なのでコストも小さい。） Mozillaでも運が良いと5秒くらい。 RSA-128。 それとは関係ないですが、 コードを整理したら、2の1万乗が約1秒以下で求まるようになりました。 v0.4では何分もかかる計算で、0.5アルファテストでも2秒くらいかかっていました。 これまでのメモ
2003年12月18日 bigint.js v0.5 beta2 微妙に高速化。バグ修正。 RSA-128。 RSA-128 (抗P±1法）。 RSA-256。 関係ないですが、2568桁ある1000!を1秒で求めるデモ。 手元では、1分42秒で、10000!までやりました。3万桁以上ある答えがでました。 factorial n!の表と見比べると、合ってるみたいです。 JavaScript もあなどれませんね。
Mozilla はIEに比べて数倍遅いので注意。
2003年12月19日 bigint.js v0.5 beta3。
2003年12月21日 bigint.js v0.5 beta4。RSA128ビット、256ビット、360ビット。 128ビットのページに暗号化と復号化のテストを加えた。
2003年12月22日 PigPGP v0.2 alpha test。
これまでのデモと違いページを開いただけでは始まらず、 ページ中ほどの [Run] をクリックすると開始なのでご注意ください。
動的にセッション鍵を発生させ、そのセッション鍵で入力テキストを暗号化するとともに、暗号化した出力の末尾に、復号用セッション鍵をRSAで暗号化したものを付け足します。さらに、デバッグ出力では、この変換を逆向きに行い、原文を復元します。すなわち、暗号文末尾の復号用セッション鍵を読んで、そのRSA暗号を解除して復号用セッション鍵を取り出し、それを使って全体の暗号を解除します。 セッション暗号化の方式と乱数の発生は考える余地がありますが、PGP/RSAの現実の実装の原理はこれです。
PigPGP v0.1 では、たった64ビットなのに、この処理に四苦八苦していました。 新しい Bigint.js v0.5 を使うと128ビットは余裕、360ビットくらいまでは十分、実用になりそうです。 すると110桁の整数なので、容易には分解されません。 数時間（たぶん数日）はかかるので、次のようにして、 初対面の匿名の二人が公衆の面前で堂々とかつ秘密にゲリラ的な通信ができます。
机上の理論では「RSA512ビットは安全でない」と言いますが、 安全でないといっても簡単には解読できません。 1時間稼げれば、十分に秘密の通信が可能です。 解読されても、鍵は使い捨てなので関係ないわけです。
副産物。これまでUTF-16と8の相互変換はビットシフトなどのJavaScriptとしては「高度」な変換だと何となく思い込んでいたのですが、 落ち着いて考えてみたら、だいたいこれだけでした。仕様書がビットシフトっぽいからといって、そのままやることはなかった。
function( nUTF16Code ) {
var pUTF8Code = new Array();
var q, r;
if( nUTF16Code < 128 ) pUTF8Code[0] = nUTF16Code;
else if( nUTF16Code < 2048 ) {
r = nUTF16Code % 64;
q = ( nUTF16Code - r ) / 64;
pUTF8Code[1] = 128 + r;
pUTF8Code[0] = 192 + q;
} else {
r = nUTF16Code % 64;
q = ( nUTF16Code - r ) / 64;
pUTF8Code[2] = 128 + r;
r = q % 64;
q = ( q - r ) / 64;
pUTF8Code[1] = 128 + r;
pUTF8Code[0] = 224 + q;
}
return pUTF8Code;
}
2003年12月23日 PigPGP v0.2 alpha2。Netscape 4.8でも動くようにした。 セッション暗号化の係数を10桁オーダーにした。
2003年12月24日 JavaScriptの低水準:
0x40001000<<1 は左に1ビットずらせ、
つまり2倍しろ、ということだから、直感的には 0x80002000 が返るような気がする。
もちろんUINTとしてである。
JavaScript は 0x40001000 を2倍できる。
0x40001000*2 は 0x80002000 に等しい。
普通の2倍なら、型についてはJavaScriptの側で勝手に面倒を見てくれるのだ。
32ビットどころか53ビットまでは、シームレスに行ける。
型変換の破れ目が見えることは、まずない。
ところが、ビットシフト演算だけは、
興味深いことに、引数が32ビットINTにキャストされるようだ。（というより、
32ビットINTからはみ出そうになっても、自動で型変換してくれない、というべきか。）
0x40001000<<1 とやると、内部的には、
UINT32なら、 0x80002000 だろうが、JavaScript はこの演算を強制的にINT32で行い、
-0x7FFFE000 と答える。
内部的に割り算などでシフトをエミュレートして答えるのでなく、 Cなりの実装言語のシフトを直接コールしているのだろう。 もしかすると2、4……をかけたり割ったりは、この方法が最速なのかもしれない。
次のようなハックも考えられる。
INT32 = function(a) {return (a<<0);}
x = 0xFFFFFFFF;
x = (INT32)(x); // -1
x = 0x100000005;
x = (INT32)(x); // 5
INT32は「0ビットずらせ」、つまり実質的に何もするな、という関数だ。 ところが、その副作用で32ビット符号付きINTにキャストされるので、 0x80000000 より大きい数は、2の32乗未満ならその補数となる。 数値はNumber型一本で内部のゴタゴタは隠してあるはずのJavaScriptだが、 こんなこともあるのだ。
（今日は暗号のヤツは進みません。）
2003年12月25日 つづき。同様に、JavaScript でUINT32へのキャストは >>>=0 と書ける。ちょっとトリッキーだが。
以上を前提に、Mersenne Twister MT19937 を JavaScript にしてみました。 RSAや楕円曲線暗号などの鍵生成、セッション鍵生成で、JavaScriptの組み込み乱数よりもう少し安心して何か使いたかったからです。 これだけではまだセキュアと言えないでしょうが、とりあえずひとつのテスト。
mt = new MersenneTwister( nSeed ); a = mt.getRandomUINT32(); b = mt.getRandomUINT32(); c = mt.getRandomUINT32();
例えば、上のようにして、a、b、c に32ビットUINTの乱数が入ります。
getRandomUINT32 は呼び出すたびに（一般には）異なる数を返します。
オブジェクトを作るときの nSeed は32ビットUINTですが、省略するとデフォルトのシードが使われます。
MersenneTwister = function( nSeed ) {
if( nSeed === void 0 ) nSeed = 4357;
else nSeed >>>= 0;
this.pInteger = new Array( 624 );
for ( var i = 0; i < 624; i++ ) {
this.pInteger[i] = ( nSeed & 0xffff0000 ) >>> 0;
nSeed = ( 69069 * nSeed + 1 ) >>> 0;
this.pInteger[i] =
( this.pInteger[i] | ( nSeed & 0xffff0000 ) >>> 16 ) >>> 0;
nSeed = ( 69069 * nSeed + 1 ) >>> 0;
}
this._initialize();
}
MersenneTwister.prototype.getRandomUINT32 = function() {
if ( this.index > 623 ) this._initialize();
var y = this.pInteger[ this.index++ ];
y ^= y >>> 11, y ^= ( ( y << 7 ) & 0x9d2c5680 ) >>> 0,
y ^= (( y << 15 ) & 0xefc60000 ) >>> 0, y ^= y >>> 18;
return y >>> 0;
}
MersenneTwister.prototype._initialize = function() {
var i;
for( i = 0; i < 227; i++ ) this.pInteger[i] = this._jumble( i, i+1, i+397 );
for( i = 227; i < 623; i++ ) this.pInteger[i] = this._jumble( i, i+1, i-227 );
this.pInteger[623] = this._jumble( 623, 0, 396 );
this.index = 0;
}
MersenneTwister.prototype._jumble = function( nIndex, nIndex2, nIndex3 ) {
var tmp = ( this.pInteger[ nIndex ] & 0x80000000 ) |
( this.pInteger[ nIndex2 ] & 0x7fffffff );
var tmp2 = ( tmp & 0x1 )? 0x9908b0df : 0 ;
return ( this.pInteger[ nIndex3 ] ^ ( tmp >>> 1 ) ^ tmp2 ) >>> 0;
}
getRandomUINT32Fluctuated は、
時計で揺らぎを与える版です。
呼び出されたたびにシステムクロックの10ミリ秒の針を見て、
それに応じて内部ベクトルの成分を0～9個飛ばします。
揺らぎが増える代わりに、乱数列を再現はできなくなり、発生させた乱数の消費速度が平均5倍に増えます。
さらに、引数をつけて呼ぶと、
呼び出し中に無意味に時間がかかる計算をランダムに行って、揺らぎのエントロピーを増やします。
引数を 0x10000 とすると、ダミーのダイアログボックスを出してユーザにOKをクリックさせることで、
計算時間とシステムクロックとの相関性を絶ち、
揺らぎのエントロピーをさらに増やします。複雑な数学計算でエントロピーを増やすより人間さんに手伝ってもらうほうが速いし、
予測不可能性が高い。
demo: セッションキーに使う乱数をMTに変えただけ。
2003年12月28日 bigint.js v0.5 beta9を使ったJavaScript上のRSA
これらの更新はRSA暗号のデモにはあまり関係しません。
2003年12月26日 bigint.js v0.5 beta8を使ったJavaScript上のRSA (PigPGP v0.2 beta): 128～360ビットの指定サイズのRSA鍵ペアを生成。 32ビット×2行2列のヒル暗号でセッション暗号化。
2003年12月31日 bigint.js v0.5 beta10を使ったJavaScript上のRSA
少なくとも360ビットまでは、遅い Mozilla でも十分に動作する。 128ビットはかなり速い。 360ビットでは、鍵生成で30秒～数分かかる。 基本的に109桁の素因数分解になるから、個人の攻撃に対しては、相当の耐性がある。 素因数分解専用のソフトを投入しても2003年時点では109桁は簡単には壊れない。 暗号化は速い。復号化は128ビットで1～2秒程度、360ビットでは10～30秒かかる。 鍵生成のコストは確率的で、運に左右される。 暗号化・復号化は確定的な時間で動作し、運が悪くて待たされるということはない。
2003年5月にやったときは、 128ビットも苦しかったが、今は128ビットは楽勝だ。今2003年5月のデモをやると、あまりの遅さにびっくりする。 エラトステネスを1回通過するだけで10秒くらい待たされる。 これは今なら10ミリ秒オーダーで終わる場所だ。
PigPGP 0.2.0
PigPGP 0.2.1
巨大整数の平方根を実験的に実装。ニュートン法で逐次近似するナイーブなものです。 デモは、2001桁の整数 2*10^2000 の平方根を求めることで、2の平方根を小数1000桁求めます。 コストは10秒程度（アルゴリズムの工夫で高速化の余地があるはず）。[Demo1] をクリックすると実行します。
平方根のアルゴリズムを改善、2*10^2000の平方根が1秒台になりました。 これを使って、円周率を約600桁求めるデモを追加しました。
平方根は依然として通常の（平方根の逆数でなく平方根自身を求める）ニュートン法ですが、 逐次近似の各ステップでその段階で有効でない数字はすべて無視すること、 最終的に必要な精度ぎりぎりでゴールインするように意図的に有効桁数を落とし必要最小限の計算しか行わないことで計算量を節約、 約10秒かかった2*10^2000の平方根が1秒台 2*10^4000が約10秒、^6000が約20～30秒です。 100桁であれば一瞬であり、任意の数の平方根が、有効数字100桁の高精度で、一瞬で求まることに相当します。
Mathematical Information Technology の 平方根のアルゴリズムでは、Javaを使った標準的な実装で平方根の計算が「102000でも40秒かかっていない」とありますが、こっちはそれが1秒台。 リンク先のコードはどこも悪いところはなく、Java自身の実装です。 アグレッシブにチューンアップされたJavaScriptは、Javaのお上品なBigIntegerより、何十倍も速く走ることができます。
例示: JavaScriptの浮動小数点演算は15桁程度の有効数字がある。そしてニュートン法では1回ごとに有効桁が倍になる。 単純に考えると、初期値「有効数字15桁」から30、60、90、180、360、720、1440と7回ループして1000桁の精度に至る。 しかし、実際には有効数字8桁から始めれば、同じ7回で16、32、64、128、256、512、1024となって、これでも1000桁の精度が出る。 しかも各ステップでほぼ半分の桁数の計算で済むので、 計算量がざっと半分になる。 つまり、何桁の精度が必要か自動認識して、 その桁数をぎりぎり超過できる必要最小限の条件を内部的に自動設定することで、 トータルの計算量を最適化できる。
円周率の計算はガウス・ルジャンドルでとりあえずやってみました。 所要時間は手元では8～9秒程度です。
5つの要素からなるテーブル[0][1][2][3][4]を二乗すると、 結果のテーブルでいちばん「重なる」のは添え字4番であり、5通りの発生元がある。 実際には例えば13と31は同じだから片方だけ計算すればいいが、 ここでは結果の大きさを評価するために別々に数える。 すると、結果の添え字4番のところは、第一の数のどのテーブルのますからも発生する。 5より上は入力の添え字0からは作れないから、重複度が低い。 3より下は入力の添え字4からは作れないから、重複度が低い。 一般に、いちばん重複度が高いのは入力テーブルの最後の添え字にあたる場所であり、 テーブルの長さだけ重複できる。 ところが、__BIGINT_JS_INT_MAX / (9999999*9999999) は、90.072だから、重複度90までは精度が保てる。 つまりテーブルの長さ90=630桁の平方までは、 繰り上がり処理を最後に一度だけやればlossyなオーバーフローがないことが保証される （現実にはもう少し大きくても大丈夫だが630桁なら絶対確実に保証される）。 新しいアルゴリズムでは、「テーブル値を増やした結果が (__BIGINT_JS_INT_MAX - (9999999*9999999)*2 - 9999999 ) = 8807199284740991 以下なら、どう転んでも次の加算で __BIGINT_JS_INT_MAX を超過することはない」という考えで動く。 630桁以内ならこのことは起きないから考えないでいい。 それ以上を含む一般の場合、足した結果の現在値が上の値を越えたときだけ繰り上がり処理をする。
_qr_typeX）。
手元では、7万桁÷70桁が10秒程度、7万桁÷350桁が1分程度。
とりあえず動いただけなので、まだ高速化の余地はある。
Bigint.fromFloat は、内部的に文字列を経由させず、直接テーブルを書く（このほうが明らかに効率が良いが、
これまでの100桁、200桁というオーダーでは、大差なかった）。
例えば、Bigint.fromFloat("1.23e+507654") として、50万桁の数字を表すオブジェクトを高速に生成できる。
実際に50万桁分の配列を確保して0は0で埋めるので注意。
JavaScriptの数値型は309桁しか行けず、あとはInfinityに落ちてしまう。
_qr_typeF）より、
6万桁超用に追加した _qr_typeX の方が速い。Mozillaでは、速度の逆転はもっとぎりぎりで起こる。
したがって、プラットフォームによって内部的な関数の選択を変えるようにした。
注意 Operaでは最初のデモはフリーズするかもしれません。 Operaについての不具合は、販売元にお問い合わせください。 （Operaユーザは直接または広告スポンサー経由で発売元に大金を払っているのですから、 買った品物の欠陥について製造元にサポートを要求すべきでしょう。）
Mozilla 「65536桁の壁」の詳細 Mozilla の JavaScript は、String型自体としては原則的に65536以上の長さを持つことができる。
しかし、matches = s.match() としたとき、
matches[0]（マッチした全体）は長さ65536以上になれるものの、
matches[1] 以下は、もしマッチした長さが65536以上だと、65536を法とする最小剰余に切り詰められてしまう。
Stringオブジェクト（ラッパーオブジェクト）のすべてのメソッドが65536の長さをサポートしていないため、
MozillaのStringは一般には65536以上の長さを持てない。
bigint.js のコンストラクタは現在、正規表現を使って入力文字列をパースするため、Mozilla のこのバグの影響を受ける。 正規表現を使わないことで回避は可能。多分、対応でなく回避する予定。
toString のデフォルト toFancyString は、常に10桁区切りにフォーマットされた数値文字列を返す（従来は区切りの位置が不統一だった）。
別ページに階乗のデモを用意しました。 0～20万の好きな数の階乗を計算できます。
bigint.js v0.5 は、JavaScript で巨大な数を扱うための汎用ライブラリです。 このライブラリを使って、例えば、RSA暗号、楕円曲線暗号、巨大な階乗などを実装できます。
このページでは、ばかばかしいほど大きな数が関係する「階乗」のデモをお楽しみください。 別ページに、0から20万のあいだの好きな数の階乗を自由に計算できるデモもあります。 JavaScriptだけで10万の階乗を一桁残らず計算した記録、 「10nの階乗の末尾の0の個数」についてのエッセイをお読みください。
bigint.js v0.5 は現在、開発テスト中のベータで、不具合や未実装の部分も多々あります。 前回からの更新。 お気づきの点があれば掲示板にお願いします。
bigint.js v0.5 は、JavaScript で巨大な数を扱うための汎用ライブラリです。 このライブラリを使って、例えば、RSA暗号、楕円曲線暗号、巨大な階乗、長い桁数の円周率の計算などを実装できます。
bigint.js v0.5 は現在、開発テスト中のベータで、不具合や未実装の部分も多々あります。 前回からの更新。 お気づきの点があれば掲示板にお願いします。
Bigint.serio() が無意味に実体をコピーしていたのを改善、単に同じものへの参照を返す
（beta 21 の Bigint.misha() と同じ）。
return PigPGP._powmod_tunedS の return が抜けていた。Bigint.prototype.isProbablePrime() を10倍以上高速化。
ただし、Bigint._isProbablePrime_typeN を直接呼び出したほうが、さらに2倍速い。
Bigint.getPrimeTable( min, max )は、指定された範囲の素数表を生成する。
Bigint.countPrimes( max )は、指定された数以下の素数の個数を数える。
Bigint.getPseudoprimeTable( min, max, base ) を実装。指定範囲内の底 base のすべての擬素数を配列として返す。デモ付き。
さしあたって、引数の上限は 134217728 （ライブラリ的にはいくらでも大きくできるが、あまり速くない）
Bigint._isProbablePrime_typeN の検査可能範囲を2**27=134217728まで拡張した
Bigint._isProbablePrime_typeN2 を作ったが、内部的に 2**53 の壁を越えて計算精度が失われ、
擬素数かどうか判定できなくなる場合があった。このバグを修正した。
[index]