想用数学在信息安全中大显身手？先从二次同余方程入手吧！

你是不是还在为密码安全担忧？其实，这背后隐藏着高深的数学原理哦。今天我们就从二次同余方程的解法开始，为你解开这个谜题。

你知道吗？在二次同余方程x² ≡ a (mod m)中，解可不只是简单的正负平方根，它还需要满足互素条件呢。这个平方剩余和非剩余的分类，可真是个大学问。

为什么欧拉判别式这么重要？因为它能快速判断一个数是不是平方剩余，这在加密算法中可大有用途。就像诸葛亮的锦囊妙计一样，关键时刻就能发挥作用。

对了，想不想知道平方剩余在实际中有什么用？它可是RSA加密算法的基石呢，没有它，你的信息可就不安全喽。

二次同余方程的解

• 什么是二次同余方程的解
  注意这里二次同余方程和一次同余方程是不一样的
  在x2x^2x2 三 a (mod m) 方程中举例 ↓
  解即剩余类，因为是模m，所以我们在 [ 0, m-1 ]中逐个代入看是否满足方程式。
• 解的说法有三种：
  ①平方剩余
  ②平方非剩余
  要满足这两种情况的条件：（a,m）= 1，首先要互素，其次再代入完全剩余系看有没有解
  ③既不是平方剩余也不是平方非剩余
  这种情况是在(a,m) 不是互素的情况下，即使是有解，也不是平方剩余和平方非剩余
• 只需要代入一半的完全剩余系的数字
  如下图所示，因为x2x^2x2在模的世界里，m-x与x是差一个正负符号而已，在二次方程式中正好解决了该问题，那么就可以利用该特性，只需要在完全剩余系中找解的时候，
  代入一半即可[0，m/2 ] or [ m/2, m]，代入哪一半都行，这两部分代入后结果是一样的。
  解释：将下图的m-x平方展开后就明白为什么只需要代入一半（记住：是要模m的）
  

欧拉判别式

上面讲述了二次同余方程的解是从何而来，如何找解。那么欧拉判别式就是用来判断一个解是否是二次同余方程式的平方剩余或者平方非剩余

• 使用欧拉判别式的条件
  方程式：x2x^2x2 三 a (mod p)
  1：p必须是奇素数(奇素数，不包括2)
  2：(a, p) = 1，ap必须互素
  （很显然必须要互素，因为本身判断的就是平方剩余/非剩余的关系，开头已经讲清楚了）
  满足以上条件则：
  若$a$(^((p^pp−^-−1^11)^))/^//2^22 三 1 (mod p)，则a是平方剩余。
  若$a$(^((p^p