@user-my3ty8mz8r 3 ай бұрын
m=m1×2^32+m2 と32bitで分割して(nも) mn=(m1n1)×2^64+(m1n2+m2n1)×2^32+m2n2 として実装したなぁ。 mi×njは64bitをでなくて2のべき乗倍はmod NのNの大きさによって繰り返し4倍法や繰り返し16倍法をオーバーフローしないように選んで計算する。
@aqua_length 4 ай бұрын
これ昔符号付き32bit整数しか使えない環境でNTT実装しようとして悩んだ記憶。懐かしい 最初に思い付いたのがGarnerでゴリ押しなんですけど、大量の素数(3つほど)を用意しなきゃいけないんですよね。 その後モンゴメリ乗算に切り替えたんですけど、前処理が面倒で結局未だに凍結状態なんですよね。 さて、どう解くのか 追記 力！ 繰り返し2倍法はヒューマンリソースマシーンで使ったな…懐かしい。
@user-rc2tv2ho4f 4 ай бұрын
aをa%mとa%m-mのうち絶対値の小さい方にする（bも同様）ではダメなのでしょうか？
@AngrySadEight 4 ай бұрын
この方法ではできません。a%mとa%m-mのうち、小さい方の絶対値の最大値は、m/2程度になります。よって、この方法でa, bの絶対値を小さくしても、a×bの絶対値は最悪でm^2/4程度となり、mが最大で2^60程度となることから掛け算の計算結果が64bit型に収まりません。
@user-rc2tv2ho4f 4 ай бұрын
普通に勘違いしてました。ありがとうございます。