---
# System prepended metadata

title: Untitled

---

- $x = (p + q)^r \pmod N = \Sigma_{k=0}^n binomial\_of\_(n,k) p^{n-k}.(qr)^k$
- $y = (p + qr)^r \pmod N$
- $N = pqr$


-----
Approach:
Find some expression $z$ such that $z \equiv 0 \pmod P$, for $P \ne N, P \ne 1, P \mid N$ (i.e P is n, p or q)
Why: This allows us to find one of the three primes = key recovery
$z \equiv 0 \pmod P \iff z = k*P$ for some $k$, so we can take $\gcd(z, N) = P


$y = (p + qr)^r \pmod N = \Sigma_{k=0}^r K_k p^{r-k}\cdot(qr)^k \equiv p^r + q^r + pqr\cdot K \pmod N$
In this situation $p^{n-k}.(qr)^k == 0 mod n$ unless $k = 0$ or $k = r$
$\Rightarrow y \equiv p^r \pmod q$

$$
x = (p + q)^r \equiv \sum_{k = 0}^r K_k\cdot p^k \cdot q^{r - k} \equiv p^r \pmod q
$$



$$
y \equiv (p+q)^r \equiv (p+q)(p+q)^{r-1} (mod q) = p(p+q)^{r-1} (mod q) = ... = p^r (mod q)
$$


so $y = p^r + (rq)^r \pmod q$
so $x = p^r + q^r \pmod q$
so $y-x = 0 mod q$

If you do $\gcd(y-x, n) = gcd(kq, pqr) = q$

---
So, status: have $q$, need $p$ or $r$
~~Take $x \mod q = p^r$, take modular $r$th root?~~ Don't know $r$...
Work on $y - x \pmod r$
$x \equiv p^r + q^r \pmod r$
$y \equiv p^r + r^rq^r \pmod r$
$y - x \equiv q(r - 1) \pmod r$
$y - x + q \equiv q-q \equiv 0 \pmod r$
$\implies \gcd(y - x + q, N) = rq$


$y-x \pmod r = -q \pmod r$