java查找滿足該兩個條件的特定範圍

林內的BigInteger顯影用java這就需要找到兩個大整數（Y和Z）的應用程序：java查找滿足該兩個條件的特定範圍

Y^k < N and Z^j < N < Z^(j+1)

N，K和j是已知的。 N是一個大整數（1024bit）。

我目前的實現是通過選擇一個隨機的BigInteger來檢測Y和Z，並測試條件是否滿足。但問題是，有時需要很長時間才能找到解決方案，或者根本找不到解決方案（可能bitSize未正確計算）。有什麼辦法可以加快速度嗎？

代碼：

BigInteger getMessage(int bitSize, int lowerBound, int upperBound, BigInteger module) 
{ 
     boolean foundOne = false; 
     BigInteger candidate = null; 
     while(!foundOne) 
     { 
       candidate = new BigInteger(bitSize,random); 
       foundOne = (upperBound == 0 || candidate.pow(upperBound).compareTo(module) > 0) && (lowerBound == 0 || candidate.pow(lowerBound).compareTo(module) < 0); 
     } 

     return candidate; 
}

來源

2012-09-05 blejzz

使用二進制搜索。例如，要找到Z，以Zmin = 0和Zmax = N開始。計算Zmid =（Zmin + Zmax）/ 2，然後比較Zmid^j與N，如果Zmin^j < N，則設置Zmin = Zmid。否則，設置Zmax = Zmid。最終，您將縮小到O（log（N））時間內的正確Z軸。

來源

2012-09-05 23:06:01

我沒有提到我需要幾個解決方案。我怎麼修改二進制搜索，所以我不總是得到相同的解決方案？ – blejzz

您可以搜索'Z^j

一種方式是通過利用你的表情的對數直接解方程：一旦你已經確定了log(Y)和log(Z)值

k * log (Y) < log (N) 
=> log (Y) < log (N)/k 

    j * log (Z) < log (N) < (j + 1) * log (Z) 
=> log (Z) < log (N)/j AND log (Z) > log (N)/(j + 1)

，你可以取指數（對於log10的nePanan對數或10的冪）來得到Y和Z.

You can read here about various ways of calculating the log of a BigInteger。在BigDecimal上運行計算似乎是明智的，然後對BigInteger進行四捨五入（上或下）並檢查它是否有效。

來源

2012-09-05 22:44:21 assylias

不要隨意調整你當前的猜測，這取決於它與你想要匹配的規格的關係。

例如，從n = N/2開始。

如果n^j> N，則將n降低一定量。

如果n ^Ĵ< N，則檢查N R個（J + 1）> N。

如果n ^（J + 1）< N，然後通過一定量的增加ñ。

等

來源

2012-09-05 22:47:09

數字相當大（至少1024位），（德）遞增1可能需要很長時間。 – blejzz

然後不減1，除以1000或更多，然後減少，因爲你更精確。 –

java查找滿足該兩個條件的特定範圍

回答

相關問題