Квадратный корень по модулю: Квадратный корень по простому модулю за $O(\log p)$

{(p-1)/2} = -1 \mod p$. То есть это верно, если отношение — не вычет. Докажем, что все такие числа вида $(z+i)/(-z+i)$ различны для всех $i$, тогда это будет как раз биекция во все вычеты, так что вероятность равна $1/2$.

Пусть $(z +i)/(-z+i) = (z+j)/(-z+j) \mod p$. Домножим на знаменатели, сократим, получим, что $2iz = 2jz \mod p$, то есть $i = j \mod p$.

Вероятность не совсем $1/2$, потому что нужно, чтобы $z + i \neq 0$ и $-z + i \neq 0$. Так что нам не подходят еще два вычета. Алгоритм от этого не страдает, просто для малых $p$ вероятность становится чуть меньше. Можно доказать, что для $p = 3$ все равно все работает.

НОУ ИНТУИТ | Лекция | Основы теории чисел

< Лекция 9 || Лекция 1: 123456789

Аннотация: В первой лекции мы приводим основные понятия теории чисел. Вводим определение сравнимости по модулю и формулируем основные свойства сравнений. Таким образом мы подготавливаем учащегося к освоению собственно криптографических тем.

Ключевые слова: минимум, бесконечное множество, математика, связь, числитель, целое число, частное решение, значение

1.

1 Основы теории чисел

При необходимости более глубокого знакомства с материалом можно воспользоваться любым из университетских учебников алгебры и теории чисел. Кроме того, имеются пособия по криптографии, содержащие необходимый минимум теоретических сведений в указанных областях. В частности, отметим пособие [1], особенно полезными мы считаем главы 2 и 3 этой книги. Мы приводим краткие сведения из теории и примеры решения некоторых задач по теории чисел.

1.1.1 Делимость

Будем считать известными свойства операций над целыми числами (сложения, вычитания, умножения), понятие модуля целого числа и свойства модуля.

Рассмотрим свойства отношения делимости во множестве целых чисел, это множество обозначается .

Определение 1.1 Целое число делится на целое число , если существует такое целое число , что . Число называется делимым, — делителем, — частным.

Если число делится на , то пишут ( кратно ).

Отношение делимости в обладает следующими свойствами:

1. Для любого имеем .
2. Отношение делимости транзитивно, т. е. из и следует .
3. Если , то , и , т. е. отношение делимости сохраняется при изменении знаков делимого и делителя.
4. Если и , то .

5. Если и , то .

   Отметим, что утверждения, обратные 4 и 5, ложны:
   из делимости суммы не вытекает делимость слагаемых, а из делимости произведения не вытекает делимость сомножителей.

   Например, делится на 12, но ни 35, ни 13 не делятся на 12; делится на 12, но ни 3, ни 8 на 12 не делятся.

6. Если , а не делится на , то не делится на .
7. Нуль делится на любое число .
8. Любое число делится на 1.
9. Если , то не существует такого , что .
10. Если , то .

1.1.2 Деление с остатком

Определение 1.2 Разделить целое число на целое число с остатком — это значит найти два таких целых числа и , чтобы выполнялись условия:

2. .

Число называется неполным частным, а число — остатком от деления на .

Заметим, что остаток — всегда есть число неотрицательное, а вот неполное частное может быть каким угодно целым числом. Поэтому на вопрос: «Сколько будет минус пять поделить на три с остатком?», правильный ответ: «Неполное частное минус два, остаток — один».

Теорема 1.1 Каковы бы ни были целое число a и целое число , всегда возможно, и притом единственным способом, разделить на с остатком.

1.1.3 Наибольший общий делитель

Определение 1.3 Целое число называется общим делителем целых чисел , если каждое из этих чисел делится на .

Определение 1.4 Целое число называется наибольшим общим делителем чисел , если:

1. является общим делителем этих чисел;
2. делится на любой общий делитель чисел .

Теорема 1.2 Наибольший общий делитель чисел определён однозначно с точностью до знака (т. е. если и наибольшие общие делители чисел , то либо , либо ).

Условимся всегда рассматривать положительное значение наибольшего общего делителя чисел . Обозначение: .

Пример 1.1

Действительно, множество положительных делителей числа есть , а для числа такое множество имеет вид . Пересечение этих множеств . Число является общим делителем чисел и и делится на все остальные общие делители этих чисел. Значит, . Заметим, что — наибольший по величине положительный общий делитель чисел и .

Для любых целых чисел их наибольший общий делитель является наибольшим по величине положительным общим делителем.

Однако данное здесь определение является более удобным, так как распространяется на достаточно большой класс объектов, в частности, на многочлены. Определение же, включающее слова «наибольший по величине», не применимо к многочленам.

Дальше >>

< Лекция 9 || Лекция 1: 123456789

Модульный квадратный корень — Prime-Wiki

Навигация

Темы	Регистрация • Новости • История • Как • Статистика последовательностей • Прототипы шаблонов

Материал из Prime-Wiki

Перейти к: навигация, поиск

A модульный квадратный корень [math]\displaystyle{ r }[/math] из целого числа [math]\displaystyle{ a }[ /math] целое число по модулю [math]\displaystyle{ m }[/math] больше 1 — это целое число, такое что: 92 \equiv a\ \pmod m }[/math]

В этой статье мы рассмотрим случай, когда модуль простой. В противном случае мы можем вычислить квадратные корни по модулю простых множителей [math]\displaystyle{ m }[/math], а затем сгенерировать решение, используя китайскую теорему об остатках.

Когда аргумент конгруэнтен нулю, существует только один модульный квадратный корень, а именно ноль. В противном случае количество квадратных корней может быть равно двум или нулю в зависимости от того, является ли аргумент квадратичным вычетом по модулю [math]\displaystyle{ m }[/math] или нет. Сумма обоих квадратных корней равна нулю. 9{(m-1)/2} \bmod m }[/math] равно 1 (иначе квадратного корня не будет, если [math]\displaystyle{ a \not\equiv 0\ \pmod m }[/math]).

• 1 Модуль равен 2
• 2 Модуль равен 3 по модулю 4
• 3 Модуль конгруэнтен 5 по модулю 8
• 4 Модуль конгруэнтен 1 по модулю 8
• 5 Пример 1
• 6 Пример 2

Модуль равен 2

В этом случае квадратный корень конгруэнтен аргументу [math]\displaystyle{ r }[/math]. 92 \bmod 101 = 10 }[/math]

Обратите внимание, что [math]\displaystyle{ i*i \equiv -1 \,\pmod {101} }[/math]

[математика]\displaystyle{ r = 58*88*(10-1) \bmod 101 = 82}[/math]

Таким образом, модульные квадратные корни равны 82, а его минус 19, что легко проверить: [math]\displaystyle{ 82*82 \equiv 58 \,\pmod {101} }[/math], [math]\displaystyle { 19*19 \эквив 58 \,\pmod {101} }[/math].

Пример 2

Найдите квадратный корень из 111 по модулю 113.

Прежде всего проверяем, что модуль 113 является простым. Тогда мы находим, что оно конгруэнтно 1 по модулю 8. 92 \bmod 113 = 112 }[/math], [math]\displaystyle{ r = 1 }[/math], [math]\displaystyle{ v = 98*62 \bmod 113 = 87 }[/math], [ math]\displaystyle{ w = 112*112 \bmod 113 = 1 }[/math].

Шаг 4: [math]\displaystyle{ w = 1 }[/math], поэтому квадратный корень равен [math]\displaystyle{ \pm v = \pm 87 }[/math].

Таким образом, модульные квадратные корни равны 87, а его минус 26, что легко проверить: [math]\displaystyle{ 87*87 \equiv 111 \,\pmod {113} }[/math], [math]\ displaystyle{ 26*26 \equiv 111 \,\pmod {113} }[/math].

Модульный квадратный корень — Prime-Wiki

Навигация

Темы	Регистрация • Новости • История • Как • Статистика последовательностей • Прототипы шаблонов

Материал из Prime-Wiki

Перейти к: навигация, поиск

A модульный квадратный корень [math]\displaystyle{ r }[/math] из целого числа [math]\displaystyle{ a }[ /math] целое число по модулю [math]\displaystyle{ m }[/math] больше 1 — это целое число, такое что: 92 \equiv a\ \pmod m }[/math]

В этой статье мы рассмотрим случай, когда модуль простой. В противном случае мы можем вычислить квадратные корни по модулю простых множителей [math]\displaystyle{ m }[/math], а затем сгенерировать решение, используя китайскую теорему об остатках.

Когда аргумент конгруэнтен нулю, существует только один модульный квадратный корень, а именно ноль. В противном случае количество квадратных корней может быть равно двум или нулю в зависимости от того, является ли аргумент квадратичным вычетом по модулю [math]\displaystyle{ m }[/math] или нет. Сумма обоих квадратных корней равна нулю. 9{(m-1)/2} \bmod m }[/math] равно 1 (иначе квадратного корня не будет, если [math]\displaystyle{ a \not\equiv 0\ \pmod m }[/math]).

• 1 Модуль равен 2
• 2 Модуль равен 3 по модулю 4
• 3 Модуль конгруэнтен 5 по модулю 8
• 4 Модуль конгруэнтен 1 по модулю 8
• 5 Пример 1
• 6 Пример 2

Модуль равен 2

В этом случае квадратный корень конгруэнтен аргументу [math]\displaystyle{ r }[/math]. 92 \bmod 101 = 10 }[/math]

Обратите внимание, что [math]\displaystyle{ i*i \equiv -1 \,\pmod {101} }[/math]

[математика]\displaystyle{ r = 58*88*(10-1) \bmod 101 = 82}[/math]

Таким образом, модульные квадратные корни равны 82, а его минус 19, что легко проверить: [math]\displaystyle{ 82*82 \equiv 58 \,\pmod {101} }[/math], [math]\displaystyle { 19*19 \эквив 58 \,\pmod {101} }[/math].

Пример 2

Найдите квадратный корень из 111 по модулю 113.

Прежде всего проверяем, что модуль 113 является простым. Тогда мы находим, что оно конгруэнтно 1 по модулю 8. 92 \bmod 113 = 112 }[/math], [math]\displaystyle{ r = 1 }[/math], [math]\displaystyle{ v = 98*62 \bmod 113 = 87 }[/math], [ math]\displaystyle{ w = 112*112 \bmod 113 = 1 }[/math].

Шаг 4: [math]\displaystyle{ w = 1 }[/math], поэтому квадратный корень равен [math]\displaystyle{ \pm v = \pm 87 }[/math].

Таким образом, модульные квадратные корни равны 87, а его минус 26, что легко проверить: [math]\displaystyle{ 87*87 \equiv 111 \,\pmod {113} }[/math], [math]\ displaystyle{ 26*26 \equiv 111 \,\pmod {113} }[/math].