3

私の仕事は、フェルマーの素因数分解法を使用して非常に大きな合成数を因数分解することです。数値は1024ビットで、10進数で約309桁です。

私は以下のPythonコードを思いつきました。これは、gmpy2正確さのためにモジュールを使用しています。これは、ウィキペディアのページに表示されている擬似コードのPython実装にすぎません。そのページの「ふるいの改善」のセクションを読みましたが、それを実装する方法がわかりませんでした。

def fermat_factor(n):
    assert n % 2 != 0  # Odd integers only

    a = gmpy2.ceil(gmpy2.sqrt(n))
    b2 = gmpy2.square(a) - n
    while not is_square(b2):
        a += 1
        b2 = gmpy2.square(a) - n

    factor1 = a + gmpy2.sqrt(b2)
    factor2 = a - gmpy2.sqrt(b2)
    return int(factor1), int(factor2) 

def is_square(n):
    root = gmpy2.sqrt(n)
    return root % 1 == 0  # '4.0' will pass, '4.1212' won't

このコードは、小さい数値の場合はかなり高速に実行されますが、問題で指定された数値と同じ大きさの数値の場合は時間がかかりすぎます。このコードの速度を改善するにはどうすればよいですか？私は自分のコードを書いてくれる人を探していませんが、いくつかの提案をいただければ幸いです。ご回答ありがとうございます。

4

2 に答える 2

4

特に多数の場合、これほど多くの平方および平方根演算を実行することは避ける必要があります。

それらを回避する簡単な方法は、すべての係数が解であるためには、a ^ 2-N = b^2が真でなければならないことに注意することです。例えば、

a ^ 2 mod 9-N mod 9 = b ^ 2 mod 9

Nが55であるとすると、N mod 9=1です。

ここで、（mod 9）のセットを考え、それをモジュロ9で二乗します。結果のa ^ 2 mod 9は、セット{0、1、4、7}です。同じことがb^2mod9にも当てはまるはずです。

a ^ 2 mod 9 = 0の場合、8は9を法とする数の二乗ではないため、0 --1 = 8（すべてのmod 9）は解ではありません。これにより、（mod 9）= {0、3および6}。

a ^ 2 mod 9 = 1の場合、1-1 = 0（すべてmod 9）であるため、（mod 9）= {1、8}が可能な解決策です。

a ^ 2 mod 9 = 4の場合、4-1 = 3（すべてmod 9）は可能な解決策ではありません。a ^ 2 mod 9=7の場合も同様です。

したがって、その1つのモジュラスは、「mod9」の9つの可能な値のうち7つを排除しました。

そして、あなたは多くのモジュラスを持つことができ、それぞれが可能性の少なくとも半分を排除します。たとえば、10の係数のセットを使用すると、1,000 aの約1つをチェックするだけで、完全な平方であるか、整数の平方根を持つことができます。（私は自分の仕事に約10,000の係数を使用します）。

注：素数の累乗であるModuliは、多くの場合、素数よりも便利です。また、モジュラス16は、N mod 4が1の場合は「a」が奇数である必要があり、N mod 4が3の場合は「a」が偶数である必要があるため、便利な特殊なケースです。 。」

于 2013-02-06T08:11:22.513 に答える
3

このスクリプトを書き直して、任意精度の浮動小数点数ではなく整数のみを使用することを検討してください。

gmpyは整数平方根をサポートしています（効率的に計算された平方根のフロアを返します）。これは、平方根の2乗が元の値と等しいかどうかをテストすることにより、is_square（）関数に使用できます。

gmpy2についてはよくわかりませんが、gmpy.sqrt（）では整数引数が必要であり、整数出力を返します。floatを使用している場合は、おそらくそれが問題です（特に、拡張精度を使用している場合、floatは整数と比較して非常に遅いため）。実際に整数を使用している場合、is_square（）は、呼び出されるたびに整数から浮動小数点への面倒な変換を実行する必要があります（gmpy2.sqrt（）！= gmpy.sqrt（））。

これは難しい問題だと言い続ける人のために、この方法を使用することがヒントであったことを覚えておいてください。フェルマー因数分解アルゴリズムは、因数分解される合成数に近い2つの素因数があるときに存在する弱点に基づいています。お互い。これがヒントとして与えられた場合、問題を提起しているエンティティはこれが事実であることを知っている可能性があります。

編集：どうやら、gmpy2.isqrt（）はgmpy.sqrt（）（sqrtの整数バージョン）と同じであり、gmpy2.sqrt（）は浮動小数点バージョンです。

于 2012-09-26T01:34:29.740 に答える