プチコン 非公式コミュニティ
プレイ日記
こういち
◆.Id/aHiU36hu
2021/12/7 21:28
2021/12/7 21:28
a*b mod Pがオーバーフローして上手く計算できない問題。想像以上に厄介ですね。うがぁーヾ(`□´)ﾉ
ところで、12/09の21:00からエクスプレスがあるらしいですね。(突然)ついでに、12/08の21:00は株式会社シェガーのミカ・ドロップさんが神巫女やるとか。
コメント
こういち
2021/12/7 21:37
◆.Id/aHiU36hu
いや、a*bは最大で10^18程度だから素数2つじゃ足りなくない？
4つあれば十番か
4つあれば十番か
こういち
2021/12/7 22:43
◆.Id/aHiU36hu
あぁ。モンゴメリ乗算ってこう使うのか？
こういち
2021/12/9 6:06
◆.Id/aHiU36hu
モンゴメリ乗算。もしかして原理にGarnerのアルゴリズムがある？
こういち
2021/12/9 12:22
◆.Id/aHiU36hu
モンゴメリ乗算。説明はできないけど、理解はした。
勝利条件はa*b>>31が求まること。無理そうならa*b>>30で妥協。(ビット1つ減るだけでかなり楽になる。)
勝利条件はa*b>>31が求まること。無理そうならa*b>>30で妥協。(ビット1つ減るだけでかなり楽になる。)
こういち
2021/12/13 12:14
◆.Id/aHiU36hu
モンゴメリ乗算。いざ書いてみる(C言語)と少し厄介。
モンゴメリ乗算はR=1<<31としたとき、
n/R mod PをPによる割り算を行わずRによる割り算だけで行えるのが原理なんだけど、
問題はnが整数に収まらない場面があるのよね。逆変換するときとか。
モンゴメリ乗算はR=1<<31としたとき、
n/R mod PをPによる割り算を行わずRによる割り算だけで行えるのが原理なんだけど、
問題はnが整数に収まらない場面があるのよね。逆変換するときとか。
こういち
2021/12/13 22:47
◆.Id/aHiU36hu
あとは、面倒な多倍長の掛け算を実装しなきゃ。
コメントを書く
- こちらは「プチコン3号」「プチコンBIG」など、プチコンシリーズに関する話題を扱ったコミュニティです
- プチコンシリーズにまったく関係ない書き込みはご遠慮下さい。削除の対象となります
- こちらにはその他のゲームや雑談のコミュニティはなく、作る予定もありません (ひとりで管理できないため)。ごめんなさい
- ユーザー登録なしで書き込みができます
- 秘密の合い言葉は成りすましの防止 (トリップ機能)、書き込みの編集時の本人認証に使用します
- 秘密の合い言葉に他人に推測されやすい言葉、他サービスと同じパスワードは入力しないでください。
- 書き込むと、投稿時に入力したお名前と秘密の暗号が記憶され、ログイン状態になります