Получить формулу квадратного корня для элемента поля

[dgwuqtj]

pppppppo_98 в сообщении #1614629 писал(а):

а в более расширенной версии $Z[\sqrt[3]{p}]$? , p - не куб , но не обязательно простое. А ссылку дайте?

Насчёт ссылок не знаю. В общем виде, пусть $K$ - числовое поле (конечное расширение $\mathbb Q$), $\mathcal O$ - его кольцо целых. Тогда $\mathcal O$ будет решёткой в $K \otimes_{\mathbb Q} \mathbb R$, а тензорное произведение раскладывается в произведение конечного набора копий $\mathbb R$ и $\mathbb C$ (это есть в Касселс, Фрёлих, Алгебраическая теория чисел). Чтобы извлечь корень в $K$ (или найти корень многочлена от одной переменной), можно свести задачу к $\mathcal O$ избавлением от знаменателей (т.к. это кольцо целозамкнуто). В тензорном произведении корни вычисляются обычными численными методами, типа Ньютона. И легко проверить, попал ли корень в заранее заданную решётку.

Хотя и над $\mathbb Q$ можно искать корни многочленов одной переменной тем же методом, без факторизации. Просто избавляемся от знаменателей, делаем старший коэффициент единичным, находим корени приближённо в $\mathbb R$ и проверяем, подходят ли ближайшие к ним целые.

[Rak so dna]

pppppppo_98 я разве что-то писал про умение быстро факторизовать? Смысл вашего (последнего) предложения построить некий аналог RSA, только с потенциальной уязвимостью. Потом непонятно как доказать, что на самом деле уязвимости нет (и это ещё вопрос — нет ли её на самом деле), и получить, в лучшем случае, тот же самый RSA (или что-то подобное, основанное на сложности факторизации). Ну круто, что тут скажешь.

dgwuqtj в сообщении #1614633 писал(а):

Хотя и над $\mathbb Q$ можно искать корни многочленов одной переменной тем же методом, без факторизации. Просто избавляемся от знаменателей, делаем старший коэффициент единичным, находим корени приближённо в $\mathbb R$ и проверяем, подходят ли ближайшие к ним целые.

проверять надо не ближайшие целые, а ближайшие рациональные.

[dgwuqtj]

Rak so dna в сообщении #1614636 писал(а):

Нельзя, т.к. проверять надо не ближайшие целые, а ближайшие рациональные.

Утверждение 1: пусть дан многочлен $P(x) = x^n + a_{n - 1} x^{n - 1} + \ldots + a_0$, где $a_i$ целые. Тогда любой его рациональный корень будет целым.
Утверждение 2: пусть дан многочлен $Q(x) = (b_n x^n + b_{n - 1} x^{n - 1} + \ldots + b_0)/c$, где $b_i$ и $c$ целые, $b_n$ и $c$ ненулевые. Тогда корни многочлена $P(x) = x^n + b_{n - 1} x^{n - 1} + b_n b_{n - 2} x^{n - 2} + \ldots + b_n^{n - 1} b_0$ - это в точности корни $Q$, умноженные на $b_n$, с учётом кратности.
Вроде из этих двух утверждений понятно, как от рациональных чисел можно перейти к целым.

[Rak so dna]

dgwuqtj если мы умеем быстро решать уравнения с большими коэффициентами с любой точностью, то согласен.

[dgwuqtj]

Если нужна полиномиальная сложность при фиксированной степени $n$, то обычный двоичный поиск работает. Только сначала надо найти корни производной, чтобы отделить корни исходного многочлена, и заодно избавиться от кратных корней.

[pppppppo_98]

Rak so dna в сообщении #1613582 писал(а):

pppppppo_98 в сообщении #1613580 писал(а):

И тогда из этого необходимого условия вытекает , если псевдонорма меньше нуля - решений в этом поле нет, если таки положительно, но тоже не квадрат рационального числа , то решений в этом поле нет. Ну вот на счет достаточности я пока вообще не уверен.

$\left\{ \begin{array}{lcl} x^2+6yz=a \\ y^2+2xz=b \\ 3z^2+2xy=c \end{array}\right\ \Rightarrow a^3+3c^3+9b^3-9abc=(x^3+3y^3+9z^3-9xyz)^2\geq0$

Совершенно понятно, что ваших условий недостаточно.

А я говорил о необходимых условиях существования корня , а не о достсточных, и простейшая проверка на входе ту же убьет куча рутинной работе по решению диофантовых уравнений

-- Ср окт 25, 2023 17:23:00 --

Null в сообщении #1613567 писал(а):

dgwuqtj в сообщении #1613564 писал(а):

решение (точнее, каждое $a_i$) может быть неким многочленом от $\sqrt{c_0 + c_1 \sqrt[3] 3 + c_2 \sqrt[3] 9}$, $\sqrt[3]3$ и $i \sqrt 3$. У него рациональность проверить как-то тяжело.

При чем здесь это? Берем по очереди рациональные корни
$(x^2-a)\left(729x^8-972ax^6+54(12bc+5a^2)x^4-4(48c^3-36abc+144b^3+7a^3)x^2+(12bc-a^2)^2\right)=0$
Подставляем их в систему, ищем $y$ и $z$. Если нашли рациональное $x,y,z$ - вот он корень. Ничего не нашли - в $Q\left(\sqrt[3]{3}\right)$ корней нет. Я так понял задачу.

у вас похоже ошибка. Вот что дает GroebnerBasis[{u^2 + 2 r v w - a, r w^2 + 2 u v - b, v^2 + 2 u w - c}, {u, v, w}][[1]] // FullSimplify // TeXFormиз пакета Mathematica

$$-4 w^2 \left(16 a^3-12 a b c r+r \left(7 b^3+16 c^3 r\right)\right)+54 r^2 w^4 \left(4 a c+5 b^2\right)+\left(b^2-4 a c\right)^2-972 b r^3 w^6+729 r^4 w^8$$

, r - у меня подкоренное выражения в корне поля (r=3)

[Rak so dna]

dgwuqtj вроде да (там ещё оценки на границы корней нужны — но, по-моему, где-то я их видел).

Ну, собственно, произошло ровно то, что я и пытался донести:

Rak so dna в сообщении #1614636 писал(а):

непонятно как доказать, что на самом деле уязвимости нет (и это ещё вопрос — нет ли её на самом деле)

pppppppo_98 в сообщении #1614648 писал(а):

А я говорил о необходимых условиях существования корня , а не о достсточных,

сами с собой спорить будете:

pppppppo_98 в сообщении #1613580 писал(а):

Ну вот на счет достаточности я пока вообще не уверен. (что-то режет выражение нормы)

Собственно, ответ и был на это ваше "не уверен".

pppppppo_98 в сообщении #1614648 писал(а):

у вас похоже ошибка.

Ошибки нет. Вы переобозначили неизвестные и параметры, и запутались в собственных обозначениях.

[pppppppo_98]

Rak so dna в сообщении #1614652 писал(а):

Ошибки нет. Вы переобозначили неизвестные и параметры, и запутались в собственных обозначениях.

(Оффтоп)

согласен...

[mihiv]

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

$$z=1+\frac 49(t+\frac 1{3t^2})\sqrt [3]{3}+\frac 49(t^2+\frac 1{3t})\sqrt [3]{3^2}$$ $$\sqrt {z}=\pm(\frac 13+\frac 23t\sqrt [3]{3}+\frac 2{9t}\sqrt [3]{3^2})$$

$t$-рациональное. Это, естественно, не все такие числа.

[StepV]

mihiv в сообщении #1624320 писал(а):

Это, естественно, не все такие числа.

Спасибо, что заинтересовались задачей.

[Without Name]

Это как-то делается. В книге Белрекэмпа про корректирующие коды я даже видел линейные переключательные схемы вычисления корня в поле Галуа.

[dgwuqtj]

Without Name в сообщении #1624359 писал(а):

Это как-то делается. В книге Белрекэмпа про корректирующие коды я даже видел линейные переключательные схемы вычисления корня в поле Галуа.

Для конечных полей всё сильно проще, у них часто извлечение корня сводится к возведению в степень. И всегда легко посчитать количество решений уравнения $x^n = a$.