Нахождение квадратичного невычета для простого числа

[alex_mathdone]

Для того, чтобы мне сделать лабораторную работу по предмету, мне необходимо находить квадратичные вычет и невычет простого числа. Я написал небольшую программу, которая реализует критерий Эйлера, но, что возможно закономерно, при длине простого числа в двадцать знаков (например, я использовал число $10977686520374512793$) она уже работает очень долго, не может найти невычет, а вычет находится сразу.

В лабораторной мне нужно будет использовать простое число длиной $10^{100}$, поэтому я прошу дать мне хотя бы небольшую подсказку, как можно ускорить мой алгоритм. Запрограммировать я смогу, а со стороны теории чисел я пока не догадался, как ускорить работу.

[mathematician123]

alex_mathdone в сообщении #1555708 писал(а):

Я написал небольшую программу, которая реализует критерий Эйлера

Критерий Эйлера не самый лучший способ вычисления символа Лежандра. Более быстрый алгоритм использует символ Якоби. Алгоритм есть здесь: https://ru.m.wikipedia.org/wiki/%D0%A1%D0%B8%D0%BC%D0%B2%D0%BE%D0%BB_%D0%AF%D0%BA%D0%BE%D0%B1%D0%B8

[alex_mathdone]

mathematician123 в сообщении #1555710 писал(а):

alex_mathdone в сообщении #1555708 писал(а):

Я написал небольшую программу, которая реализует критерий Эйлера

Более быстрый алгоритм использует символ Якоби

А про него-то я и забыл совсем, аж стыдно. Спасибо вам!

[Someone]

(alex_mathdone)

alex_mathdone в сообщении #1555708 писал(а):

нужно будет использовать простое число длиной $10^{100}$

Аж $10^{100}$ цифр? Может быть, $100$ цифр?

[alex_mathdone]

Someone в сообщении #1555720 писал(а):

(alex_mathdone)

alex_mathdone в сообщении #1555708 писал(а):

нужно будет использовать простое число длиной $10^{100}$

Аж $10^{100}$ цифр? Может быть, $100$ цифр?

Я же написал - длина числа $10^{100}$, я думал, что очевидно, что в этом числе должно быть 100 цифр (так как само по себе число $10^{100}$ состоит из одной $1$ и ста $0$).

[Someone]

(alex_mathdone)

alex_mathdone в сообщении #1555722 писал(а):

Я же написал - длина числа $10^{100}$

Длина числа $10^{100}$ равна $101$ (в десятичной системе счисления), но Вы написали

alex_mathdone в сообщении #1555708 писал(а):

простое число длиной $10^{100},$

и мне пока что очевидно, что Вы хотите использовать простое число с длиной записи $10^{100}$ цифр. Но это всё оффтоп. Просто выражайтесь аккуратнее.