本文记录 NSS 靶场 tangcuxiaojkuai 的 easy_factor 系列题解/学习笔记。该系列主要围绕 费马小定理 展开，核心收获是：当已知 φ(n)，或者已知形如 k·φ(n) 的信息时，可以利用这些条件对 n 进行分解，从而还原 RSA 的关键参数。 这个假期整体状态不算太好——毕竟过年嘛，比赛也比较少，刷题节奏自然就慢了些。靶场里一些相对简单的密码题我基本都做得差不多了（/(ㄒoㄒ)/~~），接下来打算把重心放到更进阶的方向：二元 Coppersmith、广义 RSA，以及 LWE 相关问题上…

整理完之后发现，这类题本身难度不算特别大，但我之前因为数学基础薄弱，很多关键点理解不到位；再加上没有熟悉的解题模板/套路，导致遇到不互素的题目时经常卡住，甚至做不出来。现在把这类问题系统地整理一下，方便之后复盘和套用。 整体思路：e小的时候使用有限域开方，e如果比较大，需要使用AMM算法，常用算法还有CRT算法和hensel定理。 AMM算法是什么：本质上也是一种有限域开方。 CRT什么时候用：如果说m的位数比较小，小于其中一个素数，那么就不需要使用CRT，如果CRT的位数比较大，则需要在各素数下进行有限域开方，然…