問題タブ [modular-arithmetic]

エラー訂正を行っているので、Javaのmod11で2桁を分割する必要があります。

モジュラー計算機を使用することで、これがわかりました。

問題は、Javaにこれを計算させることにあります。Javaの場合：

Javaは技術的にモジュラー演算を実行できないことを知っています。私の一部は、逆数を何らかの方法で計算するか、配列を使用して可能な出力値を格納する必要があると考えています。

3つの数値のモジュラー乗算を行うための効率的なアルゴリズムを見つける必要があります。

言い換えれば、Cでこれを見つける方法はありますか？

私は大きな数のために以下の式を計算しようとしています。

この式の値は非常に大きくなるため、この式のモジュラスの値が素数である必要があります。この式の値が でxあり、素数 を選択するとします1000000007。を探していx % 1000000007ます。

これが私のコードです。

しかし、これだけの最適化でも N の値が大きい場合は失敗します。たとえば、N が 50 の場合、正しい出力は です605552882が、これは になります132924730。正しい出力を得るためにさらに最適化するにはどうすればよいですか?

注：私はNを偶数と考えています。

A、B、Cの3つの大きな64ビット数があります。計算したいもの：

私のレジスタが64ビットであることを考えると、つまり、書き込みa * bは実際には（A x B）mod2⁶⁴を生成します。

それを行うための最良の方法は何ですか？私はCでコーディングしていますが、この場合、言語は適切ではないと思います。

この解決策を指すコメントに賛成票を集めた後：

具体的に説明します。（（a％c）*（b％c））はまだ2⁶⁴よりも大きい可能性があり、レジスタがオーバーフローして間違った答えが返されるため、これは解決策ではありません。してただろう：

（（（A mod C）x（B mod C））mod2⁶⁴）mod C

この場合、モジュラ算術演算を作成しようとしています:

私が読んだ限りでは、モンゴメリー乗算を使用するのが最速の方法ですが、VHDLを使用してハードウェアに実装するために実際にどのように行われるのか理解できません。

誰かがそれを行うことができましたか、それを使用できるライブラリを持っていますか?

2 つの数Nとが与えられたときp、 をと で割っkたものの最大べき乗をとします。とは余素です。pp^kN!d = N!/(p^k)dp

どうすれば見つけられますd mod pか? N!が高いと非常に高くなるため、直接反復は実用的ではありませんN。式を見つけるには、より効率的なアルゴリズムが必要です。

Project Euler からの問題 48 の説明:

系列、1^1 + 2^2 + 3^3 + ... + 10^10 = 10405071317。系列の最後の 10 桁を検索します、1^1 + 2^2 + 3^3 + ... + 1000^1000。

Pythonでワンライナーを使用してこの問題を解決しました：

Python では除算 mod n が非常に高速であることを思い出したので、ほぼ瞬時にそのようにしました。しかし、これが内部でどのように機能するのか (Python はどのような最適化を行うのか?)、なぜこれがそれほど高速なのかはまだわかりません。

これについて説明していただけますか？操作はmod 10**10、全体の合計ではなく、リスト内包表記のすべての反復に適用されるように最適化されていますか?

Residual Number Systemの概念とMixed Radix systemの概念は理解していますが、単純なケース スタディで機能する変換方法を取得するのに苦労しています。

私は Knuth の Art of Computer Programming から始めましたが、変換の理論が少し多すぎて、Euler について言及されると途方に暮れました。ウィキペディアにはこの件に関する素晴らしいセクションがあり、こことここで試してみましたが、どちらの場合も、最初の番号に戻ることができませんでした。

ここ (PDF)に良い記事があり、関連するセクションをここに要約しましたが、乗法逆数とその表記法がわかりません。具体的には、どのように y_2 = |(3 - 19)|(1/31)|_7|_7 = |5 * 5|_7 特にどのように |1/31|_7 = 5

2 つの ECDSA 秘密鍵/公開鍵ペアを 1 つに結合するにはどうすればよいですか? それがopensslのモジュラー追加で行われることは知っていますが、それがどのように機能するかわかりません。誰か私にそれを説明できますか？