二次同餘式(quadratic congruence)亦稱二次同餘方程,是一類同餘方程,它是關於未知數的二次多項式的同餘方程。二次同餘式是研究高次同餘式的基礎,在密碼學中套用很廣泛。一般的二次同餘式求解問題可以歸結到討論形如x≡a(mod m)的同餘式。
基本介紹
- 中文名:二次同餘式
- 外文名:quadratic congruence
- 別名:二次同餘方程
- 屬性:一類同餘方程
- 相關概念:二次剩餘,二次非剩餘等
基本介紹,二次同餘式的解數,二次剩餘與二次非剩餘,
基本介紹
![](/img/e/237/wZ2NnLkRmYwIjMlBDOkZjNiV2NiRmM4QGN1ITO3ATZ4ATYyU2LhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/d/b6b/wZ2NnL1QTZ3UWNmhzM0ATN5EGNkVmM5UGO1gTZlJzN3cTMlNzLhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/8/d90/wZ2NnL0Q2YyUzM2UDNxImNlFWZjNWZ4IDM0I2NkVDOxUzN2QzLhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/3/024/wZ2NnLwcDZwgjNzMDN4gTNyEmZ5MDNwIzNiNjNhBDO1IWMmR2LhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/7/a75/wZ2NnLkJGOyYDZ2QDOwMjNiRmNmdDN4YWO2IWZ2MDO5MmZ3gzLhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/3/024/wZ2NnLwcDZwgjNzMDN4gTNyEmZ5MDNwIzNiNjNhBDO1IWMmR2LhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/3/024/wZ2NnLwcDZwgjNzMDN4gTNyEmZ5MDNwIzNiNjNhBDO1IWMmR2LhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
注意:用
乘式(1)再加上
,得
![](/img/8/7a3/wZ2NnL2EWZ2AzMwMGMxgTN1QGM2gDMwMDNwY2MyYjY4IzNhR2LhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/d/a36/wZ2NnL0ADNlRzYjZ2YxYTN1EDMiVWNjV2MlJzN3IWZ1ATY2gzLhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/1/c4d/wZ2NnLzU2Y2Q2Y1ImY5UWMkJGZzEzNzIWY2YWOkJGM1QTN0E2LhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/f/77f/wZ2NnL4IGZlNDO1IjZ4IGZ5UTZ0ATYykzM2EGNwIzM4YDNmZ2LhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/e/3c3/wZ2NnL0IjN1QGMjVmYiJzY3UTM4QjY5kjZzMGN5UmY5ImZlRzLhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/6/298/wZ2NnL0UmYzADMlZ2NzE2M0YzNiZjNzATNxIzMxYWZ5YjNhZ2LhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
二次同餘式的解數
二次同餘式的解數(solution numbers of a quadratic congruence)是對二次同餘式的一種刻畫,即二次同餘方程解的個數的判定:設
為素數,
,且
,二次同餘式
![](/img/a/acf/wZ2NnLhhzMmdzMjVjMmFTOiRzYkFTZyYzMwUTOlZDMjdzY4Q2LhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/f/dc0/wZ2NnLzAjY0MzMkJTZzMTMkVTY5AzYzYGMhlDMihTMlljZ3AzLhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/5/9e6/wZ2NnL1QWY5AzY4UGOjRWY3kTZ0ETMhFjMmJjMiZjY2cDOkZ2LhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/7/a52/wZ2NnLzUjZkhjZhdjNxMmY1IGZlBzMiNmZ4kjYkVTOlJjZ1EzLhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
在
時,解的個數為
。
![](/img/9/95f/wZ2NnLyMDZxQzN5QDZ5UzNxMzY5YWZjVGO5gDNyEDNykzYkV2LhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/3/e44/wZ2NnLiBTMidjM4kDMiJzYzUTYyMmY0MGZjN2NxU2N1kTZ2Y2LhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
在
時,解的個數有下面三種情形:
![](/img/c/643/wZ2NnL5AzNwkjNwUWN3Y2MwEzN0YjNyATOwUGOjRTM4ITN5QzLhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
1.
,有一個解;
![](/img/1/c2e/wZ2NnLklTZiJjZmJ2N5MjN3Q2N2kTYzEDO1MWMwgzMmNTO4E2LhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
2.
,當
時有二解,
時無解;
![](/img/7/e6e/wZ2NnLiRWZjNDM2YTOyY2YldTY0YDZjJ2M5cDZwUWO4YjMmZ2LhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/9/a14/wZ2NnLzYWZiZWOkZ2YkNTMyEDZhZTZwYDZmZjYhJmMhJjY2I2LhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/3/d30/wZ2NnL2MDM4M2NjNTYxEmZiBzYkBzYhdTMxIzNkdjZjRWMxMzLhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
3.
,當
時有四解,
時無解。
![](/img/1/8ea/wZ2NnLjdjZlBDMiNTOyITMwMjMhBjMjdjMyYDM0YWN2cTO3IzLhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/e/7eb/wZ2NnL1QmZiF2M0IDZkRzMmVzY0UWM1YmNjNjZ1czM1EWMjFzLhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/9/c56/wZ2NnLzgTMldTNjRmYmR2NxUGOxUTO3AjMxETYkFTO2YTNmFzLhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
二次剩餘與二次非剩餘
定義設m是正整數,若同餘式
![](/img/d/64e/wZ2NnLmJWY3Q2N5QjNiFDNiJTNzUjYwATYllDZwMDOiZDZxgzLhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/0/0e8/wZ2NnLmJGZiljYmBjM4YjYiRTNwEGOhBDZmdTMmJWZ5gDZ4gzLhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/0/0e8/wZ2NnLmJGZiljYmBjM4YjYiRTNwEGOhBDZmdTMmJWZ5gDZ4gzLhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
下面我們先來討論模為奇素數p的二次同餘式
![](/img/1/e1a/wZ2NnLlNWYkdTZ1cjYwMGOwIWNmV2MwYmM2YTOlJWO5QzMzM2LhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
定理1(歐拉判別條件)設p是奇素數,
,則
![](/img/7/22d/wZ2NnL5EzNihTY2QWOhZTY3YWO4YTO0MDZ1AzMzIjNlVGN3U2LhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
(1)
是模p的二次剩餘的充分必要條件是
![](/img/0/0e8/wZ2NnLmJGZiljYmBjM4YjYiRTNwEGOhBDZmdTMmJWZ5gDZ4gzLhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/d/720/wZ2NnLhNGN1IjZyMjY4gzN3EjY3E2MyQWNlZjYkJmYxcjMzEzLhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
(2)
是模p的二次非剩餘的充分必要條件是
![](/img/0/0e8/wZ2NnLmJGZiljYmBjM4YjYiRTNwEGOhBDZmdTMmJWZ5gDZ4gzLhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/e/52e/wZ2NnLzEDZmFDN0YTYxQ2MmV2N3UTNwI2YxAzM1ETY4EmZ0M2LhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/0/0e8/wZ2NnLmJGZiljYmBjM4YjYiRTNwEGOhBDZmdTMmJWZ5gDZ4gzLhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
推論 設p是奇素數,
,則
![](/img/3/fe6/wZ2NnL3ETMwQTZwQjZlRTOxEGZkJ2NiRGM0ETZmV2MiljNhNzLhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
(1) 如果
都是模p的二次剩餘,則
是模p的二次剩餘;
![](/img/2/2fc/wZ2NnLjVjN3YzNjhTZ4czM0MWMkRTM5QGM2YjMkhzMwMTMjdzLhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/c/15e/wZ2NnLxITZwcDZhVTM4ADZ4IWOiFjMiRTM5YmZwMDMhlTYzE2LhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
(2) 如果
都是模p的二次非剩餘,則
是模p的二次剩餘;
![](/img/2/2fc/wZ2NnLjVjN3YzNjhTZ4czM0MWMkRTM5QGM2YjMkhzMwMTMjdzLhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/c/15e/wZ2NnLxITZwcDZhVTM4ADZ4IWOiFjMiRTM5YmZwMDMhlTYzE2LhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
(3) 如果
是模p的二次剩餘,而
是模p的二次非剩餘,則
是模p的二次非剩餘。
![](/img/f/541/wZ2NnL4EGOwIWYyYDO3kzM4UWNkZjYwM2YwETMkdzYhJzM5czLhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/a/e7d/wZ2NnLzIGO0UjY1IGOmRDMjlTZkNTY3UGM2EDZiJDMxEmZ5U2LhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/c/15e/wZ2NnLxITZwcDZhVTM4ADZ4IWOiFjMiRTM5YmZwMDMhlTYzE2LhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
定理2 設p是奇素數,則模p的簡化剩餘系中二次剩餘與二次非剩餘的個數各為
,且
個二次剩餘與序列
![](/img/7/7de/wZ2NnL0IGMkJ2NzYzNwMDM2QjZkZjYzgDOiNmNmFWYkdTZ0M2LhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/7/7de/wZ2NnL0IGMkJ2NzYzNwMDM2QjZkZjYzgDOiNmNmFWYkdTZ0M2LhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)
![](/img/3/109/wZ2NnL4MmNykjN0QTYzkzY5gjN0MTOmVWYhFWZmJ2NlJ2MzczLhxWdtJ3bm9SbvNmLz9mYlNmYu4GZj5yZtl2ai9yL6MHc0RHa.jpg)