我正在尝试为加密作业实现一些蒙哥马利数学代码;除了需要将BigInteger中的每个位与1进行比较的步骤外,我大部分工作都在进行。

从步骤4开始,我一直在使用的数学算法是

for i = k - 1 down to 0 do
xBar = MonPro(xBar, xBar)
if e[i] = 1 then xBar = MonPro(MBar, xBar)


i只是一个索引,k是BIgInteger中的位数,b是指数。我的尝试是:

for(int i = n.bitLength() - 1; i > 0 ; i--) {
    xBar = monPro(xBar, xBar, r, nPrime, n);
    if (n.testBit(i) == true)
         xBar = monPro(mBar, xBar, r, nPrime, n);
}
return monPro(xBar, BigINteger.ONE, r, nPrime, n);


monPro是一个肯定起作用的辅助功能。同样,该代码段之前省略的步骤肯定可以正常工作。所以主要的问题是,我如何按位迭代BigInteger?除非我对e [i]错误,否则请参见下文。

上一阵子,我已经进行了大量的阅读,而关于实际实现的资源却很少。关于该主题的一些数学论文纯粹是神秘的。

我也不确定上面的e [i]。在书中,它的下面是e,与Log2通常在其下面写有一个2的方式相同。谁能澄清?

我尝试过将BigInteger强制转换为以2为基数的字符串,并使用char数组进行比较,然后将其与1进行比较。我还尝试了BigInteger.toString(2)来创建一个以2为基数的字符串,并使用charAt [i] == 1遍历该字符串。

我确定e [i]以上的所有步骤都是正确的,因为我已经用很多不同的值检查了它们。

如果我在E [i]方面偏离了轨道,那么有人可以解释一下它的实际含义吗?如果没有人能指出任何错误或轻微的指导?

这是一项家庭作业,因此请不要列出摘要以外的任何代码。

任何方向或建议将不胜感激。

最佳答案

for(int i = n.bitLength() - 1; i > 0 ; i--) { ... }


这将丢失位0(因为i==0循环终止时。)
尝试使用>=代替>

for(int i = n.bitLength() - 1; i >= 0 ; i--) { ... }


另外,如果您使用的是Java 7,并且知道n是正数,则可以将其转换为BitSet并遍历其“ 1”位:

static void showBitsOf(BigInteger n) {
    if (n.compareTo(BigInteger.ZERO) < 0) {
        throw new IllegalArgumentException("n must not be negative");
    }
    BitSet bs = BitSet.valueOf(n.toByteArray());
    for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
        System.out.println(i);
    }
}

09-10 23:00
查看更多