# Very Smooth
## Description
Forget safe primes... Here, we like to live life dangerously... >:)
[gen.py](https://artifacts.picoctf.net/c/135/gen.py)
[output.txt](https://artifacts.picoctf.net/c/135/output.txt)

## solution
The name of the challenge and the hint refernce to Pollard's p − 1 algorithm.

Pollard's p − 1 algorithm is a number theoretic integer factorization algorithm - you can read more about it on [wikipedia](https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm) :)

We found a piece of code that can help us factor n:

```
import math

def pollard(n):
a = 2
b = 2
while True:
a = pow(a, b, n)
d = math.gcd(a - 1, n)
if 1 < d < n: return d
b += 1
```

We got q and p, and from here it's a classic RSA:

```
#!/bin/python3

from Crypto.Util.number import inverse, long_to_bytes
import math
import binascii

p = 177529604771775811447794627528898905563608127308618713400260159684003628121897638346581772088147960905570447556763891720452738611287634839201158386379116429397697859892035253074680507674006763427672353958542251411700851999453703543179036524728177137039687762641769500501195739670681098180171316381127270595227

q = 164605327901737124994495240514963132711119880263548875469413634209843421608331532413725908549738247339988511183442179013710866395980475766695666579326675217280967182799100068138408362426253645047678448844920272489814433869044523491025443060926656512153072234650261104282229763306821456650374030627172191797163

c = 13010514034607141562990961854253226627861002586197069546517673323412890814300986383680712969614149724108883933042503584882393498362658843505851729286866283790092858236292468941447618685586044626835557550501768025500143708643761124780657643596818313492632174224213481474976505657558397107646891344842030474580610063358971205834520023889891001993067256944887210213458968081751388423730232468384293570413751860971226254102868209638538149347492509555974694589612690294866044434722108701736832130486843522518480112266062028569177405257376202037932064333801240849051995453092216261557259012463852052902773972960583171478005

e = 0x10001

n = q*p
phi = (q-1)*(p-1)
d = inverse( e, phi )
m = pow( c, d, n )
print(long_to_bytes(m))
```