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查找满足该两个条件的特定范围

回答

相关问题