Background

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.

Problem Description

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$.

Input Format

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 Format

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.

7001 4001 7 5
1155511307999246176590006

6

11083610 7305110 52 32
4578384821991465584924042474394616310820101790

39

Hint

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