### Challenge

1 | RSA challs are always easy, right? Even if N is not a integer. |

file : flag.enc, pubkey.py, rsa.sage

### Some Facts and Definitions From Algebra

- Every polynomial $f(x)$ with coefficients in $GF(2)$ having $f(0) = 1$ divides $xm + 1$ for some $m$.

$\Rightarrow$ The smallest $m$ for which this is true is called the period of $f(x)$ - An irreducible (can not be factored) polynomial of degree $n$ has a period which divides $2^{n} - 1$.
- An irreducible polynomial of degree $n$ whose period is $2^{n} - 1$ is called a primitive polynomial.

### Solution

factor(n) to get

`p`

,`q`

calculate two period : $2^{\ p.degree()}-1$, $2^{\ q.degree()}-1$

The product of two period is multiple of

`phi`

.calculate

`d`

: inverse_mod(e,phi)recover

`m_poly`

: pow(c_poly, d, n)