-
二次同餘式
鎖定
二次同餘式(quadratic congruence)亦稱二次同餘方程,是一類同餘方程,它是關於未知數的二次多項式的同餘方程。二次同餘式是研究高次同餘式的基礎,在密碼學中應用很廣泛。一般的二次同餘式求解問題可以歸結到討論形如x2≡a(mod m)的同餘式
[1]
。
- 中文名
- 二次同餘式
- 外文名
- quadratic congruence
- 別 名
- 二次同餘方程
- 屬 性
- 一類同餘方程
- 相關概念
- 二次剩餘,二次非剩餘等
目錄
- 1 基本介紹
- 2 二次同餘式的解數
- 3 二次剩餘與二次非剩餘
二次同餘式基本介紹
注意:用
乘式(1)再加上
,得
二次同餘式二次同餘式的解數
二次同餘式的解數(solution numbers of a quadratic congruence)是對二次同餘式的一種刻畫,即二次同餘方程解的個數的判定:設
為素數,
,且
,二次同餘式
在
時,解的個數為
。
在
時,解的個數有下面三種情形:
1.
,有一個解;
2.
,當
時有二解,
時無解;
二次同餘式二次剩餘與二次非剩餘
定義設m是正整數,若同餘式
下面我們先來討論模為奇素數p的二次同餘式
定理1(歐拉判別條件)設p是奇素數,
,則
(1)
是模p的二次剩餘的充分必要條件是
(2)
是模p的二次非剩餘的充分必要條件是
推論 設p是奇素數,
,則
(1) 如果
都是模p的二次剩餘,則
是模p的二次剩餘;
(2) 如果
都是模p的二次非剩餘,則
是模p的二次剩餘;
(3) 如果
是模p的二次剩餘,而
是模p的二次非剩餘,則
是模p的二次非剩餘。
定理2 設p是奇素數,則模p的簡化剩餘系中二次剩餘與二次非剩餘的個數各為
,且
個二次剩餘與序列