{"problem":{"name":"[NFLSPC #6] 挑战大数因子分解","description":{"content":"由于图片可能看不清，我们重新描述这个加密算法： - 假设 *SolarPea* 要给 *PolarSea* 发一个消息 $M'$，那么他们会进行如下的操作。 - *PolarSea* 首先生成五个大整数 $P, S_4, S_6, S_7, S_1$，使得 $P < S_6 < S_4P$ 且 $S_5 = S_4P + S_6$ 且 $(S_6\\bmod P) ^ 3 < S_4 ^ 3 < ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9929"},"statements":[{"statement_type":"Markdown","content":"由于图片可能看不清，我们重新描述这个加密算法：\n\n- 假设 *SolarPea* 要给 *PolarSea* 发一个消息 $M'$，那么他们会进行如下的操作。\n- *PolarSea* 首先生成五个大整数 $P, S_4, S_6, S_7, S_1$，使得 $P < S_6 < S_4P$ 且 $S_5 = S_4P + S_6$ 且 $(S_6\\bmod P) ^ 3 < S_4 ^ 3 < S_1 ^ 3 < (S_1 + 1) ^ 3 < S_7 ^ 3 < P$，并计算 $S_3 = S_4P + S_5$。\n- 然后 *PolarSea* 将 $S_3, S_5, S_7, S_1$ 发给 *SolarPea*。\n- *SolarPea* 拿到了 *PolarSea* 给他发的四个数。首先，他需要构造一个 $M$ 使得 $S_1 < M < S_7$，并且和 *PolarSea* 商量好一个通过 $M$ 算出 $M'$ 的方法（例如若 $M'$ 为比较小的正整数，则可以令 $M = M' + S_1$），这个方法是不保密的，所以拿到 $M$ 就相当于拿到 $M'$ 了，所以你可以不用关心 $M'$ 而是只关心 $M$。\n- *SolarPea* 生成了两个满足 $(S_3 - S_5) ^ 3 < r < w$ 的数 $w, r$，并计算 $C = (S_3 - S_5) ^ 3w + MS_5 + r(S_3 - S_5)$，然后将 $C$ 发给 *PolarSea*。\n- *PolarSea* 只需计算 $\\frac{C \\operatorname{\\bmod} P}{(2S_5 - S_3) \\operatorname{\\bmod} P}$ 即可获得 $M$。\n\n现在你截获了 *PolarSea* 和 *SolarPea* 之间的所有通信（即 $S_3, S_5, S_7, S_1, C$），请你利用已知的信息破解出 $M$。\n\n## Input\n\n第一行，读入四个整数 $S_3, S_5, S_7, S_1$，表示公钥。\n\n第二行，读入一个整数 $C$，表示密文。\n\n## Output\n\n输出一行，包含一个值在 $S_1 < M < S_7$ 的整数 $M$，表示破解的明文。可以证明在给定限制下 $M$ 唯一。\n\n[samples]\n\n## Background\n\n`NFLSPC #6` 在即，来不了现场的 *SolarPea* 要把自己的题目的 std 发给能去现场的 *PolarSea*。\n\n为了防止有选手窃听他们的通信以获得 std，他们打算使用一个公钥加密算法来确保通信的安全性。\n\n于是 *SolarPea* 使用了他在知乎上看到的有 “最大的加解密速度和安全性” 的算法，这个算法的安全性 “依赖于大数因子分解难题”：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/bc5hi2d2.png)\n\n你是一名拥有 `factorization oracle` 的参赛选手，并且你已经获得了公钥和明文。请你利用手上的 `factorization oracle`，破解出 std 吧。\n\n## Note\n\n### 样例 1 解释\n\n生成的 $P=1000$，$S_4=3$，$S_6=1001$，$S_7=7$，$S_1=5$。计算出的 $S_5=4001$，$S_3=7001$。\n\n密文 $M=6$。加密时选取的 $w=42796713439376$，$r=15045364725522$，加密结果 $C=1155511307999246176590006$。\n\n当然，这次加密是很弱的，因为 $6$ 是 $5$ 和 $7$ 中间的唯一整数。\n\n### 数据范围与约定\n\n对于所有数据， $P < 10 ^ {500}$，$C < P^{10}$。\n\n- 子任务 1（$20$ 分）：$P < 10 ^ 6$。\n- 子任务 2（$20$ 分）：$P < 10 ^ {18}$。\n- 子任务 3（$20$ 分）：$P$ 为质数。\n- 子任务 4（$20$ 分）：所有数均为随机生成。\n- 子任务 5（$20$ 分）：无特殊限制。\n\nSource：NFLSPC #6 E by asmend","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9929","tags":["O2优化"],"sample_group":[["7001 4001 7 5\n1155511307999246176590006\n","6\n"],["11083610 7305110 52 32\n4578384821991465584924042474394616310820101790\n","39\n"]],"created_at":"2026-03-03 11:09:25"}}