二次剩余二次剩余本讲内容本讲内容二次剩余的概念二次剩余的概念模为奇素数的二次剩余与二次非剩余模为奇素数的二次剩余与二次非剩余 勒让德符号勒让德符号 RabinRabin公钥密码算法公钥密码算法二次剩余的概念二次剩余的概念二次同余式的一般形式是二次同余式的一般形式是其中其中m是正整数，是正整数，。上式等价于同余式上式等价于同余式设设m是大于是大于1的整数，若同余式的整数，若同余式有解，则有解，则a叫做模叫做模m的二次剩余；否则的二次剩余；否则a叫做模叫做模m的二次非的二次非剩余。剩余。例：求例：求满满足同余式足同余式 的所有的点。的所有的点。模模7的二次剩余是：的二次剩余是：1，2，4；二次非剩余是：；二次非剩余是：3，5，6。对对 ，分别求出，分别求出 对应的的值为对应的的值为 无解无解无解无解二次剩余的分布二次剩余的分布 设设p是奇素数，则模是奇素数，则模p的简化剩余系中二次剩的简化剩余系中二次剩余与二次非剩余的个数各为余与二次非剩余的个数各为 ，且，且 个二次剩余与个二次剩余与序列序列中的一个数同余，且仅与一个数同余。中的一个数同余，且仅与一个数同余。二次剩余的分布规律二次剩余的分
