加快我的費馬因式分解函數（Python）

我的任務是使用Fermat's factorization method來分解非常大的合成數。數字大小爲1024位，大約爲309位十進制數字。加快我的費馬因式分解函數（Python）

我已經拿出下面的Python代碼，它使用gmpy2模塊來提高準確性。它只是Wikipedia page上顯示的僞代碼的Python實現。我閱讀該頁面上的「Sieve Improvement」部分，但不知道如何實現它。

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

此代碼運行速度相當之快的小數目，但花費太長的大題目中所給那些數字。我怎樣才能提高這段代碼的速度？我不是在尋找人爲我編寫代碼，但希望得到一些建議。謝謝你的回覆。

來源

2012-09-26 LonelyWebCrawler

請考慮重寫此腳本以僅使用整數而不是任意精度浮點數。

gmpy支持整數平方根（返回平方根的底面，有效計算）。這可以通過測試平方根的平方等於原始值來用於is_square（）函數。

我不確定gmpy2，但在gmpy.sqrt（）需要一個整數參數，並返回一個整數輸出。如果您使用的是浮點數，那麼這可能是您的問題（因爲浮點數與整數相比非常慢，特別是在使用擴展精度時）。如果實際上使用整數，那麼每次調用is_square（）時都必須將整數轉換爲浮點，並進行繁瑣的轉換（和gmpy2.sqrt（）！= gmpy.sqrt（））。

對於那些一直說這是一個難題的人，請記住，使用這種方法是一個提示：Fermat因子分解算法是基於存在的弱點，當要分解的複合數有兩個素因子彼此接近。如果這是作爲暗示給出的，那麼造成問題的實體很可能知道這是事實。編輯：顯然，gmpy2.isqrt（）與gmpy.sqrt（）（sqrt的整數版本）相同，而gmpy2.sqrt（）是浮點版本。

來源

2012-09-26 01:34:29 Collin

神聖煙，這使我的功能快8倍！我所要做的只是用'gmpy2.isqrt'替換'gmpy2.sqrt'並刪除'gmpy2.ceil'。謝謝！ – LonelyWebCrawler

你需要避免做很多平方和sqrt操作，特別是對於大數量的操作。

避免它們的簡單方法是注意a^2 - N = b^2對於所有的模都必須是真的纔是解。例如，

一個^ 2模9 - N模9 = B^2模9

比方說，你N是55，所以N模9 = 1

現在考慮的一組（一個模9），並將其平方9。得到的a^2模9是集合{0,1,4,7}。如果a^2模9 = 0，則0-1 = 8（所有模9）不是解決方案，因爲8不是a的平方，所以對於b^2模9同樣必須是真的。模數爲9.這消除了（mod 9）= {0,3和6}。

如果a^2 mod 9 = 1，則1 - 1 = 0（所有mod 9），所以（a mod 9）= {1,8}是可能的解決方案。

如果a^2 mod 9 = 4，那麼4-1 = 3（所有mod 9）不是可能的解決方案。同上^ 2 mod 9 = 7。

所以，這一個模數消除了'a mod 9'的9個可能值中的7個。

你可以有許多模數，每一個至少消除一半的可能性。使用一組（例如10個模），您只需檢查1000個a中的1個是完美正方形還是具有整數平方根。（我爲我的作品使用了大約10,000模數）。

注意：素數的權力通常比素數更有用。此外，16的模數是一個有用的特殊情況，因爲當N mod 4爲1時，'a'必須是奇數，，當N mod 4是3時，'a'必須是偶數。「證明留作練習學生「。

來源

2013-02-06 08:11:22

加快我的費馬因式分解函數（Python）

回答

相關問題