扩展欧几里得 Extended GCD题目描述给定两个质数 p26513, q32321使用扩展欧几里得算法找到整数 u,v满足 puqvgcd(p,q)输出 、 中更小的数字作为 flag。基础理论任意两个不同质数互质gcd(p,q)1因此本题本质是求 26513u32321v1 的整数解。扩展欧几里得算法作用不仅计算最大公约数还求解贝祖等式 axbygcd(a,b)是密码学中求模逆元的基础RSA、椭圆曲线均大量使用。算法原理递归实现思路基线条件gcd(a,0)a对应解 x1,y0递归设 akbr先算 gcd(b,r)g 得到 bx′ry′g回代 ra−kb变形得到 ay′b(x′−ky′)g更新系数 xy′, yx−k⋅y完整求解代码pythondef extended_gcd(a, b): if b 0: return (a, 1, 0) g, x1, y1 extended_gcd(b, a % b) x y1 y x1 - (a // b) * y1 return g, x, y p 26513 q 32321 g, u, v extended_gcd(p, q) print(fgcd {g}) print(fp * {u} q * {v} {p*u q*v}) print(最小数:, min(u, v))拓展密码学意义当需要求 p 在模 q 下的逆元时pu≡1(modq)这里的 u10247 就是 26513 模 32321 的乘法逆元这是 RSA 解密核心步骤。