[NFLSPC #6] 挑战大数因子分解

Luogu

IDLGP9929

Time1000ms

Memory1024MB

DifficultyP5

O2优化

由于图片可能看不清，我们重新描述这个加密算法： - 假设 *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 < S_1 ^ 3 < (S_1 + 1) ^ 3 < S_7 ^ 3 < P$，并计算 $S_3 = S_4P + S_5$。 - 然后 *PolarSea* 将 $S_3, S_5, S_7, S_1$ 发给 *SolarPea*。 - *SolarPea* 拿到了 *PolarSea* 给他发的四个数。首先，他需要构造一个 $M$ 使得 $S_1 < M < S_7$，并且和 *PolarSea* 商量好一个通过 $M$ 算出 $M'$ 的方法（例如若 $M'$ 为比较小的正整数，则可以令 $M = M' + S_1$），这个方法是不保密的，所以拿到 $M$ 就相当于拿到 $M'$ 了，所以你可以不用关心 $M'$ 而是只关心 $M$。 - *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*。 - *PolarSea* 只需计算 $\frac{C \operatorname{\bmod} P}{(2S_5 - S_3) \operatorname{\bmod} P}$ 即可获得 $M$。现在你截获了 *PolarSea* 和 *SolarPea* 之间的所有通信（即 $S_3, S_5, S_7, S_1, C$），请你利用已知的信息破解出 $M$。 ## Input 第一行，读入四个整数 $S_3, S_5, S_7, S_1$，表示公钥。第二行，读入一个整数 $C$，表示密文。 ## Output 输出一行，包含一个值在 $S_1 < M < S_7$ 的整数 $M$，表示破解的明文。可以证明在给定限制下 $M$ 唯一。 [samples] ## Background `NFLSPC #6` 在即，来不了现场的 *SolarPea* 要把自己的题目的 std 发给能去现场的 *PolarSea*。为了防止有选手窃听他们的通信以获得 std，他们打算使用一个公钥加密算法来确保通信的安全性。于是 *SolarPea* 使用了他在知乎上看到的有 “最大的加解密速度和安全性” 的算法，这个算法的安全性 “依赖于大数因子分解难题”： ![](https://cdn.luogu.com.cn/upload/image_hosting/bc5hi2d2.png) 你是一名拥有 `factorization oracle` 的参赛选手，并且你已经获得了公钥和明文。请你利用手上的 `factorization oracle`，破解出 std 吧。 ## Note ### 样例 1 解释生成的 $P=1000$，$S_4=3$，$S_6=1001$，$S_7=7$，$S_1=5$。计算出的 $S_5=4001$，$S_3=7001$。密文 $M=6$。加密时选取的 $w=42796713439376$，$r=15045364725522$，加密结果 $C=1155511307999246176590006$。当然，这次加密是很弱的，因为 $6$ 是 $5$ 和 $7$ 中间的唯一整数。 ### 数据范围与约定对于所有数据， $P < 10 ^ {500}$，$C < P^{10}$。 - 子任务 1（$20$ 分）：$P < 10 ^ 6$。 - 子任务 2（$20$ 分）：$P < 10 ^ {18}$。 - 子任务 3（$20$ 分）：$P$ 为质数。 - 子任务 4（$20$ 分）：所有数均为随机生成。 - 子任务 5（$20$ 分）：无特殊限制。 Source：NFLSPC #6 E by asmend

Samples

Input #1

7001 4001 7 5
1155511307999246176590006

Output #1

Input #2

11083610 7305110 52 32
4578384821991465584924042474394616310820101790

Output #2

API Response (JSON)

{
  "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 < ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments