Критерий Эйлера

Критерий Эйлера позволяет определить, является ли данное целое число квадратичным вычетом по модулю простого числа.

Формулировка

Пусть $p>2$ простое. Число a, взаимно простое с $p$ , является квадратичным вычетом по модулю $p$ тогда и только тогда, когда

a^{(p-1)/2}\equiv 1\mod p

и является квадратичным невычетом по модулю $p$ тогда и только тогда, когда

a^{(p-1)/2}\equiv -1\mod p

Литература

Михелович М.Х. Теория чисел. 1967. §3.9. с. 107—109

Похожие исследовательские статьи

Сравне́ние двух целых чисел по мо́дулю натурального числа $\text{[math]}$ — математическая операция, позволяющая ответить на вопрос о том, дают ли два выбранных целых числа при делении на $\text{[math]}$ один и тот же остаток. Любое целое число при делении на $\text{[math]}$ даёт один из $\text{[math]}$ возможных остатков: число от 0 до $\text{[math]}$ ; это значит, что все целые числа можно разделить на $\text{[math]}$ групп, каждая из которых отвечает определённому остатку от деления на $\text{[math]}$ . Эти группы называются классами вычетов по модулю $\text{[math]}$ , а содержащиеся в них целые числа — вычетами по модулю $\text{[math]}$ .

Тест Пепина — тест простоты для чисел Ферма. Тест назван в честь французского математика Феофила Пепина.

Квадратичный закон взаимности — ряд утверждений, касающихся разрешимости квадратичного сравнения по модулю. Согласно этому закону, если $\text{[math]}$ — нечётные простые числа и хотя бы одно из них имеет вид $\text{[math]}$ то два сравнения

\text{[math]}

\text{[math]}

Характер, это определённая арифметическая функция, которая возникает из вполне мультипликативных характеров на обратимых элементах $\text{[math]}$ . Характеры Дирихле используются для определения L-функций Дирихле, которые являются мероморфными функциями со множеством интересных аналитических свойств. Если $\text{[math]}$ является характером Дирихле, его L-ряд Дирихле определяется равенством

\text{[math]}

Символ Лежандра — функция, используемая в теории чисел. Введён французским математиком А. М. Лежандром. Символ Лежандра является частным случаем символа Якоби, который, в свою очередь, является частным случаем символа Кронекера — Якоби, который иногда называют символом Лежандра — Якоби — Кронекера.

Целое число $\text{[math]}$ называется квадратичным вычетом по модулю $\text{[math]}$ , если разрешимо сравнение:

\text{[math]}

Первообразный корень по модулю m ― целое число g такое, что

\text{[math]}

Си́мвол Я́коби — теоретико-числовая функция двух аргументов, введённая К. Якоби в 1837 году. Является квадратичным характером в кольце вычетов.

Алгоритм Адлемана — первый субэкспоненциальный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Алгоритм был предложен Леонардом Максом Адлеманом в 1979 году. Леонард Макс Адлеман — американский учёный-теоретик в области компьютерных наук, профессор компьютерных наук и молекулярной биологии в Университете Южной Калифорнии. Он известен как соавтор системы шифрования RSA и ДНК-вычислений. RSA широко используется в приложениях компьютерной безопасности, включая протокол HTTPS.

Мультипликативная группа кольца вычетов по модулю m — мультипликативная группа обратимых элементов кольца вычетов по модулю m. При этом в качестве множества элементов может рассматриваться любая приведенная система вычетов по модулю m.

Теорема Вильсона — теорема теории чисел, которая утверждает, что

Если $\text{[math]}$ простое число, то формула $\text{[math]}$ делится на $\text{[math]}$ .

Характер биквадратичного вычета — теоретико-числовая функция двух аргументов, являющаяся частным случаем символа степенного вычета. Также является характером в простом поле.

Показателем, или мультипликативным порядком, целого числа $\text{[math]}$ по модулю $\text{[math]}$ называется наименьшее положительное целое число $\text{[math]}$ , такое, что

\text{[math]}

Метод квадратичного решета — метод факторизации больших чисел, разработанный Померанцем в 1981 году. Долгое время превосходил другие методы факторизации целых чисел общего вида, не имеющих простых делителей, порядок которых значительно меньше $\text{[math]}$ . Метод квадратичного решета представляет собой разновидность метода факторных баз . Этот метод считается вторым по быстроте. И до сих пор является самым быстрым для целых чисел до 100 десятичных цифр и устроен значительно проще чем общий метод решета числового поля. Это универсальный алгоритм факторизации, так как время его выполнения исключительно зависит от размера факторизуемого числа, а не от его особой структуры и свойств.

В теории чисел теорема Прота является тестом простоты для чисел Прота.

В теории чисел факторизация методом непрерывных дробей (CFRAC) — это алгоритм разложения целых чисел на простые множители. Это алгоритм общего вида, пригодный для факторизации произвольного целого $\text{[math]}$ .

Алгори́тм Тоне́лли — Ше́нкса относится к модулярной арифметике и используется для решения сравнения

\text{[math]}

Алгоритм Поклингтона — это техника решения конгруэнтного уравнения вида

\text{[math]}

Ле́мма Га́усса позволяет определять, является ли число квадратичным вычетом по модулю простого числа.

Обратное по модулю целого a — это целое число x такое, что произведение ax эквивалентно 1 по модулю m. В стандартных обозначениях модульной арифметики эта эквивалентность записывается как:

\text{[math]}

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.