蠻力BigInteger因子分解

正如您可以通過標題所告訴的那樣，我正試圖強制推導其因子爲2個素數的大整數的因式分解。我想知道是否有一種方法在for循環中使用for循環。我知道這是一個可怕的方式來做到這一點，但我想無論如何要這樣做。（我打算使用fermats分解定理，但是無法使用一些額外的方法/庫，無法使用sqrt BigIntegers，所以我不能這麼做）所以試試看看你是否可以幫助我完成我正在做的事情。沿此線成才：蠻力BigInteger因子分解

BigInteger n = new BigInteger("270653957405596110781"); // this is what i need the factors of 
BigInteger TWO = new BigInteger("2"); 
for(BigInteger i = new BigInteger("1"); i < n.divide(TWO); i.nextProbablePrime()){ 
    for(BigInteger k = new BigInteger("1"); k < n.divide(TWO); k.nextPossiblePrime){ 
     if(i.Multiply(k) = n){ 
      //i and k are the factors, and return them 
     } 
    } 
}

顯然這就是殘酷的，我知道，你不能只是說i.nextPossiblePrime（），你會需要它說我增加下一任= i.nextpossible素，我只是向你展示了我想要它工作的方式;但這就是爲什麼我問，因爲idk如果這樣的事情甚至是可能的！

請讓我知道，如果這條路線是可能的，我怎麼可以修復這個不好的代碼來運作，就像我正在想象它！

謝謝！

來源

2013-04-15 erp

蠻力分解是相同的算法，無論它應用於BigIntegers還是常規整數。你可以找到它的僞代碼，例如[這裏]（http://stackoverflow.com/a/15292911/849891）或工作Java代碼[這裏]（http://stackoverflow.com/a/12046123/849891）。 –

我拒絕「只是幫你做你正在做的事。」它不會工作。

我謙虛地在我的博客上推薦文章Programming with Prime Numbers。這裏討論的pollard-rho算法會毫不費力地考慮你的數字。包含使用BigInteger的Java實現。

順便說一句，270653957405596110781 = 7588940707 * 35664260383.

來源

2013-04-15 01:59:26 user448810

感謝您的提示，但我真的只是想知道我說的方式是可能的，我不能真正複製你的文章中的所有代碼並使用它。儘管感謝鏈接 – erp

我還是很新的計算機科學（8個月），這是我第一次回答一個問題，很抱歉，如果我沒有太大的幫助。如果我錯了，請糾正我（嚴重的是，我正在努力學習），但我認爲你在尋找的是二次篩。 http://en.wikipedia.org/wiki/Quadratic_sieve你似乎比我更先進，但我能夠用一天的工作來實現它。它在分解大量數據方面非常有效。

我對Fermat的因式分解方法一無所知，但是難道你不能僅僅繼承BigInteger到一個新的類中，並且使用平方根函數來完成它自己的實現嗎？我不知道你需要什麼樣的準確性，但是你可以總是以BigDecimal爲基礎。

希望這是有益

編輯：我猜你沒有測試代碼。您不能在BigInteger中使用像<這樣的運算符。您需要使用BigInteger.compareTo（BigInteger）

來源

2013-04-16 07:23:06

蠻力BigInteger因子分解

回答

相關問題