1

我正在使用 java 开发一个应用程序，它需要找到满足这两个条件的两个大整数（Y 和 Z）：

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

N、k 和 j 是已知的。N 是一个大整数（1024 位）。

我当前的实现通过选择一个随机的 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;
}
4

3 回答 3

1

一种方法是通过取表达式的对数直接求解方程：

   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)

确定 和 的值log(Y)后log(Z)，您可以取结果的指数（对于 neperian log 或 10 的幂对于 log10）返回 Y 和 Z。

您可以在此处阅读有关计算 BigInteger 日志的各种方法。在 BigDecimal 上运行计算似乎是明智的，然后四舍五入（向上或向下）到 BigInteger 并检查它是否有效。

于 2012-09-05T22:44:21.593 回答
1

使用二分查找。例如，要找到 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-05T23:06:01.893 回答
0

不要让它随机，根据它与你想要匹配的规格的关系来调整你当前的猜测。

例如，从 n = N/2 开始。

如果 n^j > N，则将 n 降低一些量。

如果 n^j < N，则检查 n^(j+1) > N。

如果 n^(j+1) < N，则将 n 增加一些量。

等等。

于 2012-09-05T22:47:09.553 回答