次のことができるかどうか疑問に思っていました：
我々は持っています：
X素数の積であるNため、一意であると仮定します。C定数です。Cそれが素数の一部であるNかどうかを保証できます。どちらが最もうまくいくでしょう。X mod C = Z
私たちは持っていてZ、それが-素数の積であったCことを知っています。制限されている場所は、最初の100個の素数と言えます。XNN
とにかく私たちは戻ることができますXか？
6 に答える
2
私はそうは思わない。C は X の一部ではないため、X mod C 操作を行うと情報が失われます。さらに、mod は操作の一部のみを返し、結果の他の部分を取得するには div が必要です。
例: (3*5) % 7 = 1. 情報を失ったので、div 部分を直接使わずに 1 と 7 から 15 に戻す方法がわかりません。7 を加算し、残りを加算して比較し、方程式の不足している div 部分をシミュレートする必要があります。
于 2010-05-19T20:19:21.427 に答える
2
いいえ。反例は次のとおりです。
X = 105 ( = 3x5x7 ) とします。
C = 13 とすると、X mod C = Z = 1 となります。
しかし、 X = 118 ( = 2x59 ) は C = 13 で Z = 1 も与えます。
于 2010-05-19T20:27:27.683 に答える
0
無限の素数 (したがって素数の無限の積) がありますが、可能な値はNだけです。したがって、圧倒的な確率で、を満たす有効なものは無限に存在します。CX mod CXX mod C = Z
したがって、それらのどれが元の であったかを判断しようとしている場合、Xいいえ、それはできません。
于 2010-05-20T21:19:48.613 に答える
0
あなたの質問は理解するのがかなり難しいですが、中国の剰余定理について読みたいと思うかもしれません。
于 2010-05-19T20:18:44.140 に答える
0
これを理解するには、さらに情報が必要です。たとえば、X が最初の N 個の素数 (N <= 100) の積であることを意味する場合、総当たり検索が機能します。
X が最初の 100 個の素数のサブセットの積であることを意味する場合、それはより困難です。あなたは基本的に、X が滑らかであるか、X mod Z が与えられていないかを判断できるかどうかを尋ねています。それができれば、さまざまな形式の滑らかな数の検出に依存するため、おそらく最もよく知られている整数因数分解アルゴリズムを改善できるでしょう。 .
もちろん、X mod C = X となる十分な大きさの C を選択できれば、それは簡単です。
滑らかな数については、http://en.m.wikipedia.org/wiki/Smooth_numberを参照してください。
于 2010-05-19T20:44:55.420 に答える
0
あなたの質問を正しく理解しているかどうかはわかりませんが、Z と C が与えられ、X を計算したい場合は.
X mod C = Z の場合、ある自然数 q に対して qC+Z = X が成り立つことを意味します。q は未知であるため、一般に X を正確に計算することは不可能ですが、次を満たす数の無限の集合が存在します。この方程式。これも不思議ではありません。解となる可能性のある X' があると仮定すると、X'' = X'+C も同様に有効な解になります。
C と X が互いに素であるかどうか (つまり、共通の素因数を持たないかどうか) は関係ありません。ただし、X と C が p1、p2、... pn などの共通の素因数を持つ場合、各有効な解も p1*p2*...*pn で割り切れる必要があるため、解セットが少し小さくなります。
于 2010-05-19T20:48:47.563 に答える