Zp中的((a ^ x)^ 1/x)== a？(对于Jablon的协议)

Question

我必须实施Jablon的协议(纸)但我已经坐了两个小时的bug.

我对数学不是很好,所以我不知道写这篇文章是不是我的错,或者这是不可能的.如果不可能,我不知道如何实现Jablon的协议,因为它依赖于((gP ^ x)^ yi)^(1/x)== gP ^ yi的事实.

请使用以下代码.它不起作用.

    BigInteger p = new BigInteger("101");
    BigInteger a = new BigInteger("83");
    BigInteger x = new BigInteger("13");
    BigInteger ax = a.modPow(x, p);
    BigInteger xinv = x.modInverse(p);
    BigInteger axxinv = ax.modPow(xinv, p);

    if (a.equals(axxinv))
        System.out.println("Yay!");
    else
        System.out.println("How is this possible?");

Answer 1

你的问题是你没有正确计算k ^(1/x).我们需要k ^(1/x))k为x.费马的小定理告诉我们k ^p-1是1 mod p.因此我们想找到y使得x*y是1 mod p-1,而不是mod p.

所以你想要BigInteger xinv = x.modInverse(p-1);.

如果x与p-1共用一个公因子,这将不起作用.(你的情况避免了这种情况.)为此,你需要额外的理论.

如果p是素数,则如果r,r ^ 2,r ^ 3,...,r ^(p-2)都不与1 mod p一致,则r是原始根.没有简单的算法来生成原始根,但它们很常见,因此您通常只需要检查一些.(对于p = 101,我尝试的第一个数字,2,原来是一个原始的根.83也是.)测试它们似乎很难,但它并没有那么糟糕,因为事实证明(省略了这里的理论束)只需要检查p-1的除数.例如,对于101,您只需要检查功率1,2,4,5,10,20,25和50.

现在如果r是原始根,那么每个数mod p都是r的一些幂.什么力量？这被称为离散对数问题,并不简单.(难点是RSA的基础,这是一个众所周知的密码系统.)你可以通过试验分工来完成.所以尝试1,2,3,...你最终会发现,例如,83是2 ^ 89(mod 101).

但是,一旦我们知道从1到100的每个数字都是2到一些幂,我们就会有一种计算根的方法.因为将数字提高到x的幂只是将指数乘以x.并且2 ^ 100是1.因此取幂乘以x(mod 100).

因此,假设我们希望y ^ 13为83.那么对于某些k,y是2 ^ k,因此k*13是89.如果你使用中国剩余定理,你可以意识到k = 53有效.因此,2 ^ 53(mod 101)= 93是89的第13根.

这比我们以前做的更难.但是假设我们想要采用44 mod 101的第5根.我们不能使用简单的程序,因为5没有乘法逆mod 100.但是44是2 ^ 15.因此2 ^ 3 = 8是第5根.但还有其他4个,即2 ^ 23,2 ^ 43,2 ^ 63和2 ^ 83.