# Very Smooth## DescriptionForget 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)
## solutionThe 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_bytesimport mathimport binascii
p = 177529604771775811447794627528898905563608127308618713400260159684003628121897638346581772088147960905570447556763891720452738611287634839201158386379116429397697859892035253074680507674006763427672353958542251411700851999453703543179036524728177137039687762641769500501195739670681098180171316381127270595227
q = 164605327901737124994495240514963132711119880263548875469413634209843421608331532413725908549738247339988511183442179013710866395980475766695666579326675217280967182799100068138408362426253645047678448844920272489814433869044523491025443060926656512153072234650261104282229763306821456650374030627172191797163
c = 13010514034607141562990961854253226627861002586197069546517673323412890814300986383680712969614149724108883933042503584882393498362658843505851729286866283790092858236292468941447618685586044626835557550501768025500143708643761124780657643596818313492632174224213481474976505657558397107646891344842030474580610063358971205834520023889891001993067256944887210213458968081751388423730232468384293570413751860971226254102868209638538149347492509555974694589612690294866044434722108701736832130486843522518480112266062028569177405257376202037932064333801240849051995453092216261557259012463852052902773972960583171478005
e = 0x10001
n = q*pphi = (q-1)*(p-1)d = inverse( e, phi )m = pow( c, d, n )print(long_to_bytes(m))```