P9929 [NFLSPC #6] Challenge Big Integer Factorization

`NFLSPC #6` is coming soon. *SolarPea*, who cannot attend on-site, wants to send the std of his problem to *PolarSea*, who can attend. To prevent contestants from eavesdropping on their communication to obtain the std, they plan to use a public-key encryption algorithm to ensure secure communication. So *SolarPea* used an algorithm he saw on Zhihu that claims to have the “highest encryption/decryption speed and security”. Its security “depends on the hard problem of big integer factorization”:  You are a contestant with a `factorization oracle`, and you have already obtained the public key and the plaintext. Please use your `factorization oracle` to crack the std.

Since the image may not be clear, we restate the encryption algorithm here: - Suppose *SolarPea* wants to send a message $M'$ to *PolarSea*. They will perform the following steps. - *PolarSea* first generates five big integers $P, S_4, S_6, S_7, S_1$, such that $P < S_6 < S_4P$ and $S_5 = S_4P + S_6$ and $(S_6\bmod P) ^ 3 < S_4 ^ 3 < S_1 ^ 3 < (S_1 + 1) ^ 3 < S_7 ^ 3 < P$, and computes $S_3 = S_4P + S_5$. - Then *PolarSea* sends $S_3, S_5, S_7, S_1$ to *SolarPea*. - *SolarPea* receives these four numbers from *PolarSea*. First, he needs to construct an $M$ such that $S_1 < M < S_7$, and agree with *PolarSea* on a method to derive $M'$ from $M$ (for example, if $M'$ is a relatively small positive integer, one can set $M = M' + S_1$). This method is not secret, so obtaining $M$ is equivalent to obtaining $M'$. Therefore, you can ignore $M'$ and only focus on $M$. - *SolarPea* generates two numbers $w, r$ satisfying $(S_3 - S_5) ^ 3 < r < w$, and computes $C = (S_3 - S_5) ^ 3w + MS_5 + r(S_3 - S_5)$, then sends $C$ to *PolarSea*. - *PolarSea* only needs to compute $\frac{C \operatorname{\bmod} P}{(2S_5 - S_3) \operatorname{\bmod} P}$ to obtain $M$. Now you have intercepted all communications between *PolarSea* and *SolarPea* (i.e., $S_3, S_5, S_7, S_1, C$). Please use the known information to recover $M$.

The first line contains four integers $S_3, S_5, S_7, S_1$, which represent the public key. The second line contains an integer $C$, which represents the ciphertext.

Output one line containing an integer $M$ satisfying $S_1 < M < S_7$, which is the recovered plaintext. It can be proven that under the given constraints, $M$ is unique.

### Explanation for Sample 1 The generated values are $P=1000$, $S_4=3$, $S_6=1001$, $S_7=7$, $S_1=5$. The computed values are $S_5=4001$, $S_3=7001$. The plaintext is $M=6$. During encryption, the chosen values are $w=42796713439376$, $r=15045364725522$, and the encryption result is $C=1155511307999246176590006$. Of course, this encryption is very weak this time, because $6$ is the only integer between $5$ and $7$. ### Constraints and Notes For all data, $P < 10 ^ {500}$, $C < P^{10}$. - Subtask 1 ($20$ points): $P < 10 ^ 6$. - Subtask 2 ($20$ points): $P < 10 ^ {18}$. - Subtask 3 ($20$ points): $P$ is prime. - Subtask 4 ($20$ points): all numbers are randomly generated. - Subtask 5 ($20$ points): no special restrictions. Source: NFLSPC #6 E by asmend Translated by ChatGPT 5