問題タブ [chinese-remainder-theorem]

私は長整数を持っていますが、10進数ではなく、剰余のセットとして格納されています。

だから、私はN数を持っていませんが、そのような残りのセットを持っています：

Nはこれらの素数の乗算よりも小さいので、中国の剰余定理はここで機能します（http://en.wikipedia.org/wiki/Chinese_remainder_theorem）。

Nこの6つの余りがある場合、10進数で復元するにはどうすればよいですか？これを行うためのプログラム（C / C + GMP / C ++ / perl / java / bc）は素晴らしいでしょう。

たとえば、最小のNがこの剰余のセットを持つことができるものは次のとおりです。

複数の合同を含む複数のセットがあります。

各セットの 1 つのアイテムに中国の剰余定理を適用するときに、最小の剰余を見つけようとしています。

たとえば、2 セットの場合:

セット 1:

7x + 1
7x + 3

セット 2:

11x
11x + 2
11x + 7
11x + 8

7x + 1 & 11x を取ると 77x + 22になります。すべての組み合わせをテストする必要なく
、最小の残り (上記の例では 77x + 8 ) を求めています。

これは私の実際の問題の非常に単純化されたバージョンです (それぞれに ~100 の合同がある ~50 セットです)。

この問題にどのようにアプローチするかについて私は立ち往生しています。アドバイスをいただければ幸いです。

また、数学用語が間違っていたら申し訳ありません。

配列内のモジュロ値とその剰余値が与えられた場合、Matlab で可能な最小値を見つけるにはどうすればよいですか? 例えば：

それが答えにつながります93。これは可能な最小値です。

編集：

これが私のコードですが、残りの配列の最後の値を最小値として表示するだけのようです:

編集 - 明確化

ラグランジュと中国剰余定理を使用して、Java でべき乗剰余を実装しようとしています。

たとえば、素因数 5 と 11 が与えられた場合、N が 55 の場合、ファイは 40 です。したがって、55 未満の N に互いに素な数が 40 あることがわかります。 、5 と 11 を法とする数回の乗算と、両方の結果を結合するための CRT」

私の問題は、これらの数値をどのように計算するかです。計算を完了するためにそれらを中国の剰余定理に入れる必要がありますが、結果として phi(n) を使用して N を循環させる賢い方法は思いつきません。N は非常に大きな数になり、少なくとも 1024 ビットになります。ここで間違った方向に進んでいる可能性があります。これらすべての素数が必要ですか?

答えは拡張されたユークリッド関数に関連していると思われます。これはすでにコーディングしているので、その結果を使用する必要がある場合は問題ありません。

How many numbers below N are coprimes to N?のコードがわかりません。私にとってはあまり役に立ちませんし、私が見ている数学の論文を理解するのは非常に難しいと思います.合計と積のタイプの表記法は私を少し困惑させます. また、一部の回答では、実際には BigInteger のオプションではない平方根とログを使用しています (間違っている場合は修正してください)。

だれか平易な英語で答えてくれませんか??

コードを見せても問題ありません。提出する回答はモンゴメリーを使用しているため、これは学習課題です。(ええ、知っています。数学の公式からモンゴメリーを計算できるのは奇妙ですが、このラグランジュと CRT には完全に困惑しています)

私はこれまで、私が見つけた例に取り組みました。素因数は 7 と 5 であるため、35 の phi は 24 です (私は有効な Euler totient 関数を持っています)。

C＃を使用してRSA暗号化/復号化を実装する必要があります

次のパラメータを持つ秘密鍵があります。

mod n、、、、、、、およびexponent_ p_ q_ dP_dQ(p-1mod q)

上記のパラメータは、中国の剰余アルゴリズムで説明されています

ただし、RSAのC＃.NET実装には、次のように異なるパラメーターセットがあります。

Modulus、、、、、、、、、Exponent_ P_ Q_ DP_ DQ_ D_InverseQ

CRTデータをからにマップしようとするとDOTNET、エラーが発生しますBad Data

、、 の場合p、マッピングは明らかですが、残りのパラメーターについてはわかりません。qdPdQ

これらのパラメータのマッピングについてサポートを得ることができれば素晴らしいと思います

、および( 、およびも利用可能です)Dを使用して検索しようとしています。PQEDpDq(p-1mod q)

この回答とこの回答、およびこの質問の更新によると、次の方法を使用して取得する必要がありますD。

これをテストするために、キー ペアを生成し、既存のものからコンポーネントを計算して、結果をオリジナルと比較しようとしました。を除くすべての結果は良好ですD。上記の回答からコピーした計算に問題があります。誰かが私が間違っていることを教えてくれたらうれしいです。

テストコード

テスト結果

任意の数の要素 (ただし有限)のシーケンスSを整数でエンコードし、最初のシーケンスを取得するためKにデコードできるようにする必要があります。K

コンピュータがその数にうまく対処できるようにする必要がありますK。

私はそうしました（Lispで）：

• シーケンス S に n 個の要素 e1, ... en があるとします。

• 最初の n 個の素数を生成する p1 ... pn

• 書き込み K = p1^e1 + p2 ^ e2 + ... + pn ^ ja

この方法を試しました。しかし、私は膨大な数を取得します。

chinese remainder theoremを使用して問題を解決できることはわかっていますが、K得られる so はそれほど大きくありません。

シーケンスをエンコードするように、誰かがこの定理を使用するのを手伝ってくれますか?

編集：

ch r th具体的な簡単な例を使用して、エンコードのアルゴリズムを確認したいと思います。ウィキペディアやその他の Web リソースからの理論的なアイデアを理解できません。

タプルのベクトル（剰余、モジュラス）から中国剰余定理を計算する場合、次のコードは失敗します。

結果を0として与えます（生成された反復可能オブジェクトは空だと思います）。しかし、次のコードは完全に機能します：

これにより、（a） 8851の正しい結果が得られます。

なぜlist(最初のジェネレーターの1つを使用する必要があるのですか？後続のジェネレーターに追加listしても、失敗（0）の結果は変わりません。この最初のジェネレーターをリストするだけで、正しい結果が得られます。ここで何が起こっているのですか？

nCr mod MM が通常素数である場所を扱うオンライン コーディング プラットフォームについて、私は常に多くの質問に直面してきました。そうでない場合は、通常、中国の剰余定理を使用することを好みます。

中国の剰余定理よりも簡単にこれを行うことができますか?つまり、M が素数でない場合に N mod M を単純に計算する必要がある場合は、より少ないコードを記述することでしょうか?