专栏文章

题解：P12603 RuShiA

LLionBlaze
P12603题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mio3ga08
此快照首次捕获于
2025/12/02 12:44
3 个月前
此快照最后确认于
2025/12/02 12:44
3 个月前
查看原文

Subtask 1

这么小的数据直接上 Pollard-rho 暴力算。对于不会 Pollard-rho 的可以直接找个质因子分解网站（如 https://factordb.com/，下同）解密出来是 {VerY51mpl3RSA}。

Subtask 2

p,qp,q 相差太大，qq 太小，直接 Pollard-rho 暴力算（复杂度是 q\sqrt{q} 的）。解密出来是 Your flag is {P0lL4rD_RhO_is_OK}. STOP BF RSA NOW。

Subtask 3

p,qp,q 差距太小，所以范围不大。不妨假设 p≥qp\ge q，那么 q≥p−1000q\ge p-1000，所以 p(p−1000)≤pq=n≤p2p(p-1000)\le pq=n\le p^2。枚举一下即可。解密出来是 Actually there is another way to do this. Flag is {FeRmat_i5_AWeS0m3}。

Subtask 4

p1=p2p_1=p_2？那么因为 n1≠n2n_1\neq n_2，所以 q1≠q2q_1\neq q_2，所以 p1=p2=gcd⁡(n1,n2)p_1=p_2=\gcd(n_1,n_2)。第一组解密出来是 Be careful with primes. Here is your flag {GCD_solves_th1S_Quiz}，第二组是 USELESSSSSSSSSSSSSSSSSSSSSSSSSSShahahaha。

Subtask 5

c≪nc\ll n，是不是没有取模？对 cc 开三次方根，解密出来 {E_1s_n0t_useLE55}。

Subtask 6

上难度了。我们还需要观察到 n1=n2n_1=n_2。这样我们知道 me1(modn)m^{e_1}\pmod n 和 me2(modn)m^{e_2}\pmod n，并且 e1,e2e_1,e_2 互质，辗转相除就能得到结果。解密结果是 So you understand {D0_Not_S4y_it_2_T1m3s}.。
PYTHON
def boomer6(me1,me2,e1,e2,n):
    if e1 == 1: return me1
    if e2 == 1: return me2
    return boomer6(me2,me1*pow(invert(me2,n),e1//e2,n)%n,e2,e1%e2,n) # invert 是 gmpy2.invert

Subtask 7

解法和 Subtask 5 一样。三组数据解密结果都是 Here you know that {3_t1m35_is_Al50_wE4k}.。

Subtask 8

a=pq+2p+2q+4,n=pq,r=pq−p−q+1a=pq+2p+2q+4,n=pq,r=pq-p-q+1。注意到 a−n−42=p+q\dfrac{a-n-4}{2}=p+q，然后 r=n−(p+q)+1r=n-(p+q)+1，所以能够知道 rr。结果是 As said, {AtT3nT10n_1s_4LL_U_need}。

Subtask 9

数据里提供了 m。结果是 {THX_FOR_YOUR_PLAYING}。
AC 记录。为什么都是 4ms4\mathrm{ms}，洛谷又退化了吗/fn。
总结：因为 Pollard-rho 是紫，所以这题是紫。但如果可以用其他方法质因子分解则大概是绿。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...