模块化算术

我是密码学和模块化算术的新手.所以,我确定这是一个愚蠢的问题,但我无法帮助它.

如何计算一个从
     POW(一,q)= 1(模p),
其中p和q是已知的？我没有得到"1(mod p)"部分,它等于1,不是吗？如果是这样,那么"mod p "是什么？
这与
     pow(a,-q)(mod p)= 1相同吗？

(mod p)部分不是指右边,而是指等号:它表示模p,pow(a,q)和1是相等的.例如,"模10,246126和7868726相等"(并且它们也等于6模10):如果两个数x和y在除以p时具有相同的余数,则它们等于模p,或等效地,如果p除了xy.

既然你似乎是从编程的角度来看,另一种说法就是pow(a,q)%p = 1,其中"%"是以多种语言实现的"余数"运算符(假设p> 1) ).

你应该阅读关于模块化算术的维基百科文章,或者任何基本数论理论书(甚至是加密书,因为它可能会引入模运算).

回答你的另一个问题:一般来说,没有找到这样一个a(据我所知)的一般公式.假设p是素数,并使用费马的小定理来减少q模p-1,并假设q除p-1(或者没有这样的存在),你可以通过取p 的原始根来产生这样的a将其提高到功率(p-1)/ q.[更一般地说,当p不是素数时,你可以减少q模数φ(p),然后假设它除了φ(p)并且你知道一个原始根(比如说r)mod p,你可以将r取为r的幂φ(p)/ q,其中φ是整数函数 - 这来自欧拉定理.

完全不傻,因为这是公钥加密的基础.您可以在http://home.scarlet.be/~ping1339/congr.htm#The-quation-a%3Csup%3Ex找到一个很好的讨论.

PKI通过选择p而工作,并且q是大而且相对较高的.一(比方说p)将成为您的私人密钥和其它(q)是你的公钥.加密是"破",如果一个攻击者猜测p,鉴于aq(加密消息)和q(公钥).

那么,回答你的问题:

aq = 1 mod p

这意味着aq是一个在除以时留下1的余数的数字p.我们不关心的商的整数部分,所以我们可以这样写:

aq/ p= n+ 1 /p

对于任何整数值n.如果我们乘以等式的两边p,我们有:

aq= np+ 1

解决a我们有:

a=(np+1)^{1 /q}

最后一步是找到一个n生成原始值的值 a.除了反复试验之外,我不知道有什么方法可以做到这一点 - 这相当于一个"暴力破解"试图打破加密.