For this challenge, we're given an RSA key and cipher text: `(N, E, C)` and the goal is to decrypt `C`. But, there's a twist: for any `0 < R < Q`, we can request `P mod R`.
To solve this challenge, note that given `P mod R` and `N mod R` (which we can calculate), we can derive `Q mod R = (N mod R) * (1/P mod R)`. If we choose `R > Q/4` or so, and try `(Q mod R) + k * R` for `0 < k < 4` we can find `Q` itself. Then, we can find `P`, `phi(N) = (P - 1) (Q - 1)`, and decrypt the message as in standard RSA.
For a specific run of the algorithm (using Mathematica, for example):
```n = 30194085398924225282351678114422264985171921769926991465024201683803868181711228702249932973653847310658452425801613e = 65537c = 25822491298088179523546177011435751235334257465043486099388344779694220132747557209828350699569247865723351649846178r = 97870991678321700676071340131569283349
n mod r = 18268463502769046391090238231323513170p mod r = 24455250458991168726340410041803305877q mod r = Mod[nr*ModularInverse[pr, r], r] = 92394284538715380955725584881555213349PrimeQ[qr + r + r] = True # q = qr + 2*r
phi = (q - 1) (n/q - 1)d = ModularInverse[e, phi]m = PowerMod[c, d, n] = 13040004482819619298753302854133292158047496676319949191237785711409716101691013709949396861```
Converting this back to bytes gives
`flag{1dk_what_to_wr1te_h3re_s0_hii_ig}`