本次文中未注明处n≥3，且为奇数。
一、对称数
上次文中，我们找到了中间数，这里我们来定义一下平方剩余中的对称数。
设a^2≡b (mod n)，其中a的对称数定义为(1≤a≤(n－1)/2)：
k+中间数－a，即：
① n=4k－1时，中间数为k，对称数为：
k+k－a=2k－a
对称数的平方剩余为：(4k≡1 (mod n))
(2k－a)^2≡4kk－4ka+a^2
≡k－a+b
≡k+b－a
( 注：((n－1)/2)^2≡k)
② n=4k+1时，中间数为k+1，对称数为：
k+k+1－a=2k+1－a
对称数的平方剩余为：(4k≡－1 (mod n))
(2k+1－a)^2≡(2k+1)^2－2(2k+1)a+a^2
≡4kk+4k+1－4ka－2a+b
≡－k+a－2a+b
≡n－k+b－a
(注：((n－1)/2)^2≡n－k)
根据上述可知：a的对称数的平方剩余为b－a加上(n－1)/2的平方剩余。
现在来看看以下例子：
ⅰ n=119=7*17
1^2≡1 , 2^2≡4 , 3^2≡9 , 4^2≡16 ,
5^2≡25 , 6^2≡36 , 7^2≡49, 8^2≡64,
9^2≡81, 10^2≡100, 11^2≡2 , 12^2≡25 ,
13^2≡50 , 14^2≡77 , 15^2≡106 , 16^2≡18 ,
17^2≡51 , 18^2≡86 , 19^2≡4 , 20^2≡43 ,
21^2≡84 , 22^2≡8 , 23^2≡53 , 24^2≡100 ,
25^2≡30 , 26^2≡81 , 27^2≡15 , 28^2≡70 ,
29^2≡8 , 30^2≡67 , 31^2≡9 , 32^2≡72 ,
33^2≡18 , 34^2≡85 , 35^2≡35 , 36^2≡106 ,
37^2≡60 , 38^2≡16 , 39^2≡93 , 40^2≡53 ,
41^2≡15 , 42^2≡98 , 43^2≡64 , 44^2≡32 ,
45^2≡2 , 46^2≡93 , 47^2≡67 , 48^2≡43 ,
49^2≡21 , 50^2≡1 , 51^2≡102 , 52^2≡86 ,
53^2≡72 , 54^2≡60 , 55^2≡50 , 56^2≡42 ,
57^2≡36 , 58^2≡32 , 59^2≡30
13及对称数的平方剩余为：
13^2≡50
(2*30－13)^2≡47^2≡30+50－13≡67
对照上面平方剩余，47^2≡67
ⅱ n=93=3*31
1^2≡1 , 2^2≡4 , 3^2≡9 , 4^2≡16 ,
5^2≡25 , 6^2≡36 , 7^2≡49 , 8^2≡64 ,
9^2≡81 , 10^2≡7 , 11^2≡28 , 12^2≡51 ,
13^2≡76 , 14^2≡10 , 15^2≡39 , 16^2≡70 ,
17^2≡10 , 18^2≡45 , 19^2≡82 , 20^2≡28 ,
21^2≡69 , 22^2≡19 , 23^2≡64 , 24^2≡18 ,
25^2≡67 , 26^2≡25 , 27^2≡78 , 28^2≡40 ,
29^2≡4 , 30^2≡63 , 31^2≡31 , 32^2≡1 ,
33^2≡66 , 34^2≡40 , 35^2≡16 , 36^2≡87 ,
37^2≡67 , 38^2≡49 , 39^2≡33 , 40^2≡19 ,
41^2≡7 , 42^2≡90 , 43^2≡82 , 44^2≡76 ,
45^2≡72 , 46^2≡70 ,
14及对称数的平方剩余：
14^2≡10
(2*23+1－14)^2=33^2≡70+10－14≡66
对照上面平方剩余：33^2≡66
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
