5

In class we found this programming problem, and currently, we have no idea how to solve it.

The positive integer n is given. It is known that n = p * q, where p and q are primes, p<=q and |q-k*p|<10^5 for some given positive integer k. You must find p and q.

Input:

35 1
121 1
1000730021 9

Output:

5 * 7
11 * 11
10007 * 100003

It's not homework, we are just trying to solve some interesting problems. If you have some ideas, please post them here so we can try something, thanks.

4

5 に答える 5

2

大きな整数を因数分解するためにECMメソッドを使用しました。これは、知られている最も効率的なアルゴリズムの 1 つです。アルゴリズムがどのように機能するかを知りたい場合は、多くの本を読む必要がありますが、研究に利用したい場合は、実装した人もいます。たとえば、次のオープン ソース パッケージを入手できます。C/C++ の場合はGMP-ECM、Python の場合はPyecmです。

$ python
>>> import math
>>> import pyecm
>>> n = 1000730021
>>> list(pyecm.factors(n, False, False, 2 * math.log(math.log(n)), 1.0))
[10007, 100003]
于 2010-04-15T18:20:46.217 に答える
1 
n = p * q 
|q-k*p|<10^5

とnがk入力として与えられます。したがって

q-k*p=a

と

-10^5<=a<=10^5

n を掛けq-k*p=aてq代入すると、p*q

q^2-a*q-k*n=0

それぞれについてこの二次方程式を解きaます

-10^5<=a<=10^5`

qが を割るかどうかを確認しnます。二次方程式を解くことは多項式時間で行うことができ、これは2*10^5+1方程式を解く場合にも当てはまります。nと の小さい値、およびもちろんkの大きい値に対してはn、より優れたアルゴリズムがありますk。

ypercube が述べたように、式を確認するだけで済みます。

a^2+4*k*n

は正方形です。

于 2011-05-15T15:03:00.787 に答える
1

ここで話しているサイズの数値の場合、最速の因数分解方法は (おそらく) エラトステネスのふるいを使用して、数値の平方根までの素数を生成し、それらによる試算除算を使用して、どの素数を見つけるかです。 ) は約数です。

かなりの数の因数分解方法が、より大きな数に対して発明されています。「Fermat の因数分解法」、「Pollard Rho」、「Brent の方法」、「Lenstra 楕円曲線」、「多重多項式 2 次ふるい」、および「一般数体ふるい」を Google で検索することをお勧めします。私はそれらを（大まかに）複雑さとより大きな数を因数分解する能力の昇順でリストしました. 一般的な数体ふるいについて言及する必要があるかどうかは疑問の余地がありますが、これは非常に大きな数を素因数分解するために現在知られている最も効率的な方法ですが、非常に大きなマシンでのみ役立ちます-約 110 桁以下、MPQSの方が高速ですが、GNFS の方が高速な大きな数を因数分解するには、

于 2010-04-15T16:25:33.560 に答える
-1

n = p * q および |qk*p|<10^5 で、n と k が入力として与えられます。したがって、qk*p=a、ただし -10^5<=a<=10^5 で qk*p=a を q で乗算し、p*q を n で置換すると、q^2-a*qk*n=0 が得られます。-10^5<=a<=10^5 で各 a についてこの二次方程式を解き、q が n を除算するかどうかを確認します。二次方程式を解くことは多項式時間で行うことができ、これは 2*10^5+1 方程式を解く場合にも当てはまります。n と k の値が小さい場合は、より優れたアルゴリズムがあります

p は区間内にあります

[(sqrt(k*n+2500000000)-50000)/k,(sqrt(k*n+2500000000)+50000)/k]

したがって、p の 10^5/k 値のみをチェックする必要があります。q は区間内にある

[sqrt(k*n+2500000000)-50000,sqrt(k*n+2500000000)+50000]

これには常に約 10^5 の inegers が含まれます

于 2011-05-15T19:19:22.330 に答える