从$x_1\equiv r^a \pmod{p}, x_2\equiv r^b \pmod{p}$和gcd$(b, p-1)=1$中查找$r$

$r$是素数$p$的原始值

$x_1\equiv r^a \pmod{p}$

$x_2\equiv r^b \pmod{p}$

如果$gcd(b, p-1)=1$,如果识别出$p$,$x_2$和$b$,我该如何建立$r$?

0
2019-05-18 20:54:32
资源 分享
答案: 2

提示:如果是gcd$(b,p-1)=1$,那么我们可以写$1 = tb + s(p-1)$。 所以$tb\equiv 1 \pmod{p-1}$。

0
2019-05-21 02:29:45
资源

暗示 $\ $从加法团队$\rm \mathbb Z/(p-1)$到乘法团队$\rm \mathbb Z/p^*\:$的同构$\rm n\to r^n\:$

映射$\rm\ b\to x,\ 2b\to x^2,\: \cdots\:,\: nb\to x^n$。 你寻找$\rm 1\to r\ $所以你需要$\rm\ nb\equiv 1\ $所以$\rm\ n\equiv \:\ldots$

0
2019-05-21 02:22:48
资源