Материал: Лекция 2 Генерирование простых чисел [восстановлен]
Применение цепных дробей(продолжение)
П.3. Если НОД (a,b)=1, то подходящая дробь может быть
использована для решения диофантового уравнения
ax +by = d
Целочисленные решения уравнения можно найти как
x = (−1)n−1Q |
, y = (−1)n−1 P |
n−1 |
n−1 |
П.4. Для решения сравнения ax ≡ b(mod n) , полагая что (а,n)=1. Разложим n/a в цепную дробь [a0 , a1, , ak ] , тогда
x = (−1)k b Pk (mod n)
есть искомое решение уравнения.
1. 4. Квадратичные вычеты
Квадратичные вычеты. Рассмотрим поле GF(p), где p – простое число, GF(p) состоит из элементов: 0, 1, 2, 3, … , p - 1 . Предположим, что p>2 . Ставится вопрос: какие из элементов этого поля являются квадратами этих или других элементов этого поля?
Определение 1. Если a GF(p) является квадратом некоторого
элемента b GF(p) , т.е. a= b2, b GF(p) , то такой элемент поля a называется квадратичным вычетом. Остальные элементы поля, не
представимые в таком виде, называются квадратичными невычетами.
Пример 1. Если p = 11, то вычетами в таком поле являются 1, 4, 9, 5, 3, так как 12 = 1, 22 = 4 , 32 = 9, 42 = 5, 52 = 3. Элементы 2, 6, 7, 8, 10
(как легко проверить) будут невычетами.
Если записать ненулевые элементы поля GF(p) как степени
примитивного элемента α , α1 , α 2 , α3 , , α p−1 =1 , то в этом случае квадратичные вычеты имеют вид:α j , где j – четное число.
Чтобы определить, является ли элемент a GF(p`) квадратичным вычетом, используются символы Лежандра.
Определение 2. Символом Лежандра числа a и простого числа p
называется
|
|
a |
|
0, если p | a; |
|
|
|
|
|
еслиa квадратичный вычет в GF( p); |
|
|
|
= +1, |
|||
|
|
|
|
||
|
|
p |
|
еслиa невычет в GF( p). |
|
|
|
|
|
−1, |
|
Утверждение 4. Символ Лежандра может быть вычислен по формуле
a = a(p−1)2 mod p [2, 3].p
Однако данный метод не позволяет найти квадратный корень из a по mod p, даже если известно, что a – вычет.
Нахождение вычетов
Нахождение вычета равносильно решению задачи нахождения квадратного корня уравнения
r=
modp
Простое число p может быть представлено
либо как p=4k+3, либо как p=4k+1, где k положительное целое число.
В первом случае корень находится просто:
-найти r=a^(p+1)/4modp, -выдать в качестве ответа (r,-r).