

Roar CTF

题目：见attachment

分析：

思路1： 第一步：A=(((y%x)**5)%(x%y))**2019+y**316+(y+1)/x

A为2015bit的一个大数，根据y^316可知y肯定不会太大，(y+1 )/x一定为一个整数，(((y%x)**5)%(x%y))**2019可能为1，不难算出 x=2，y=83

第二步：p=next_prime(166*z)=166*z+a,q=next_prime(z)=z+b。a,b的值应该不会太大，故n=p*q=166z^2+(166b+a)z+a*b，

因而166z^2+(166b+a)z+(a*b-n)=0有整数解 (166b+a)^2+4*166(n-a*b)因此是一个平方数，穷举遍历a，b值即可，最后可知p=842868045681390934539739959201847552284980179958879667933078453950968566151662147267006293571765463137270594151138695778986165111380428806545593588078365331313084230014618714412959584843421586674162688321942889369912392031882620994944241987153078156389470370195514285850736541078623854327959382156753458569 q=139916095583110895133596833227506693679306709873174024876891023355860781981175916446323044732913066880786918629089023499311703408489151181886568535621008644997971982182426706592551291084007983387911006261442519635405457077292515085160744169867410973960652081452455371451222265819051559818441257438021073941183 由于不知道e值，猜测e=65537成功求解

思路二：

已知了x=2，y=83后，由于n=p*q=166z^2+(166b+a)z+a*b，z=sqrt(n/166)，可以猜测出z的高比特位的值，借此预测出p，q的部分比特位值后用coppersmith定理恢复出p，q的值，但是这道题发现直接调用sympy.nextprime(z)就可以直接得到了p，q的值。

flag值

RoarCTF{wm-l1l1ll1l1l1l111ll}