现有:
y(a,x)=x1(ax1) mod ny(a, x) = x^{-1}*(a^x-1) \ mod\ n
其中a≠0但可自己选择,x是未知偶数,选择不同的a可以有多个y(a, x),问:可解x ?
或者放宽一下条件,mod p ?mod n2n^2
或者说可以证明是不能解的?


PS:这是在解前几天祥云杯的guess的一个子问题(虽然后来并不是这样解的),当时的条件是:
n=pqλ=lcm(p1,q1)=(p1)(q1)gcd(p1,q1)ya=λ1(aλ1) mod n2n = p*q \\ \\ \lambda = lcm(p-1, q-1) = \frac{(p-1)*(q-1)}{gcd(p-1, q-1)}\\ \\ y_a = \lambda^{-1}*(a^\lambda-1) \ mod\ n^2
题目没有限制a≠0,所以很容易就解出来了 :)

© 2018-2025 0xFFFF