√m≈√x+√y

[Andrey A]

Andrey A в сообщении #1576524 писал(а):

Хорошо бы тогда проверить и единицу.

Одно составное $\sqrt{1}+\sqrt{2}\approx\sqrt{6}$

и пять простых: $\sqrt{1}+\sqrt{1}\approx\sqrt{5},\sqrt{1}+\sqrt{5}\approx\sqrt{11},\sqrt{1}+\sqrt{11}\approx\sqrt{19},$ $\sqrt{1}+\sqrt{19}\approx\sqrt{29},\sqrt{1}+\sqrt{55}\approx\sqrt{71}$ из секвенции $n^2+n-1.$ Всё.

Шесть вхождений при $(y/x)_{\max}=71.$

[juna]

Andrey A в сообщении #1576560 писал(а):

Они все факторизуются (оземь) и оборачиваются знакомыми треугольниками.

Ну да, эти формы дают только треугольные числа $\frac{k(k+1)}{2}$, при $k=8p+r,r=0,1,2,3,4,5,6,7$, т.е. просто все треугольные числа.

Andrey A в сообщении #1576560 писал(а):

$2+7=17,2+17=31,2+31=49,2+49=71,2+71=97,...$ и т.д., что образует ряд $2n^2-1.$

Цитата:

Раз, два… Меркурий во втором доме… луна ушла… шесть

Таких секвенций можно, конечно, выписать много:

$$R=12, \sqrt{2}+\sqrt{2n(n+1)+1}\approx\sqrt{2(n+1)(n+2)+1}$$

$$R=17, \sqrt{2}+\sqrt{n(2n-1)-2}\approx\sqrt{(n+1)(2(n+1)-1)-2}$$

Здесь мы видим, что при фиксированном $x=2$, $m,y$ выражаются одинаковой формой.

[Andrey A]

juna в сообщении #1576650 писал(а):

Таких секвенций можно, конечно, выписать много...

Она описывает все решения для простых $m$ со вхождением двойки, коих всего три: $\sqrt{2}+\sqrt{1}\approx\sqrt{7};\ \sqrt{2}+\sqrt{7}\approx\sqrt{17};\ \sqrt{2}+\sqrt{71}\approx\sqrt{97}.$ Так-то много. В явном виде общий член такой квазипрогрессии с разностью $\sqrt{p}$ описывается формулой $u_n=\sqrt{\dfrac{(v+2pn)^2-R}{4p}},$ где $p$ — простое, $v$ — основание малого квадрата нужной четности $\equiv R \mod 4p,$ $n=0,1,2,...$ Для $R=1$, в частности, получаем четные числа, и решений со вхождением простого других не получим, кроме как $\sqrt{p}+\sqrt{p+1}\approx\sqrt{4p+2}.$ А с пятеркой уже интересно. По идее, решения в них должны быстро заканчиваться, как в случае с двойкой, и надо смотреть отношение $y/x.$

Вы треугольники еще не смотрели? Я там ошибся (погрешность не ту считал), последний не квазипростой вроде бы $t_{226}=25651.$

[juna]

Andrey A в сообщении #1576655 писал(а):

Вы треугольники еще не смотрели?

Нет еще. Времени не хватает. С погрешностью нужно решить, что делать. Склоняюсь к простой $\delta\sim \frac{R}{m^2-v^2}$, поскольку там на проверочное сравнение сразу выходим $v^2\equiv R\mod m$, но нужно еще вспомнить, что делать с составными модулями (решение из коробки для maxima что-то не нашел). Факторизация этих треугольных чисел вроде быстро идет (проверил для нескольких больших).

[Andrey A]

juna в сообщении #1576726 писал(а):

Склоняюсь к простой $\delta\sim \frac{R}{m^2-v^2}$, поскольку...

Она годится для сортировки, поскольку практически пропорциональна величине $\sqrt{m}-\sqrt{x}-\sqrt{y}$, но и про коэффициент не надо забывать. А от $m'$ напрямую зависит погрешность целого параметра $m.$ Пусть так и остается $\Delta=\dfrac{R}{2m'}.$ Смешивать их не следует (уже обжегся на этом), но разложение $\sqrt{m-\Delta}$, к примеру, возвращает нужное количество знаков дроби для вычисления $v_n$ или $s_n$ и неплохо подходит в качестве объекта двоичного поиска. Каждому свое.

Насчет составных модулей не понял в чем затруднение. Если у нас несколько $(i) $ квадратов $\equiv 1 \mod m$, решение определяет наименьший. Это строго. Если же подозрение на квазипростое, тут интересней. Сравнимых с $R$ их $i+1$, но от кого родится наименьший — наперед никогда не знаешь. Возьмем $m=2737=7\cdot 17\cdot 23.$ Три квадрата $\equiv 1 \mod 2737:\ 645,783,1310,$ последний — наименьший из четных. Имеем также $930^2 \equiv 8.$ Вычисляем остальные: $645\cdot 930 \mod 2737=447;\ 783\cdot 930 \mod 2737=148;$ $1310\cdot 930 \mod 2737=335.$ Из четырех нечетных $1807,447,2589,335$ наименьший $335.$ Если бы он был $>1310,\ R=8$ можно бы и не проверять. А так вычисляем

$$\dfrac{(2737\pm1310)^2-1}{4\cdot 2737}=186,1496\ (R=1)$$

$$\dfrac{(2737\pm335)^2-8}{4\cdot 2737}=527,862\ (R=8)$$

и сравниваем погрешности.

[juna]

Andrey A в сообщении #1576727 писал(а):

Три квадрата $\equiv 1 \mod 2737:\ 645,783,1310,$ последний — наименьший из четных.

Так в этом и проблема, что нужно находить решение квадратичных сравнений по большому модулю. Не перебором же. Для составных $m$ еще нужно факторизацию проводить и китайской теоремой об остатках воспользоваться. В PARI/GP наверное это все с коробки есть, но я уж привык к maxima. Поэтому запрограммирую.

-- Ср янв 11, 2023 13:22:44 --

Andrey A в сообщении #1576727 писал(а):

Она годится для сортировки, поскольку практически пропорциональна величине $\sqrt{m}-\sqrt{x}-\sqrt{y}$, но и про коэффициент не надо забывать.

Там множитель $m$ в числителе, но он незначащий:

Andrey A в сообщении #1570137 писал(а):

Вернем всё-таки обратное соответствие $\dfrac{R}{2}\cdot \left(\dfrac{1}{m+v}+\dfrac{1}{m-v}\right)=\dfrac{R}{2}\cdot \dfrac{2m}{m^2-v^2}=\dfrac{Rm}{m^2-v^2}.$

[juna]

juna в сообщении #1570045 писал(а):

Поэтому мы хотим:

$$\frac{R}{2}\cdot \left(\frac{1}{u}+\frac{1}{v}\right)\rightarrow\min$$

Иногда встречаются интересные вещи:

$$\sqrt{457}\approx\sqrt{46}+\sqrt{213}$$

$$a=290^2-4\cdot 457\cdot 46=12$$

$$b=624^2-4\cdot 457\cdot 213=12$$

$$\frac{R}{2}\cdot \left(\frac{1}{u}+\frac{1}{v}\right)=\frac{12}{2}\left(\frac{1}{290}+\frac{1}{624}\right)\approx 0.03030503978779841$$

$$\frac{2uR}{4u^2-R}+\frac{2vR}{4v^2-R}=\frac{2\cdot 290\cdot 12}{4\cdot 290^2-12}+\frac{2\cdot 624\cdot 12}{4\cdot 624^2-12}\approx 0.03030585193536709$$

Но для данного числа $m$ существуют и меньшие числа $a,b$:

$$\sqrt{457}\approx\sqrt{14}+\sqrt{311}$$

$$a=160^2-4\cdot 457\cdot 14 = 8$$

$$b=754^2-4\cdot 457\cdot 311 = 8$$

$$\frac{R}{2}\cdot \left(\frac{1}{u}+\frac{1}{v}\right)=\frac{8}{2}\left(\frac{1}{160}+\frac{1}{754}\right)\approx 0.03030503978779841$$

$$\frac{2uR}{4u^2-R}+\frac{2vR}{4v^2-R}=\frac{2\cdot 160\cdot 8}{4\cdot 160^2-8}+\frac{2\cdot 754\cdot 8}{4\cdot 754^2-8}\approx 0.03030701172822724$$

Т.е. различия получаем только во второй дроби. Причем:

$$\sqrt{46}+\sqrt{213}-\sqrt{14}-\sqrt{311}\approx 2.7\cdot 10^{-8}$$

А вот здесь я кстати приводил, когда такая оценка погрешности может и не сработать. Забыл уже...

[Andrey A]

juna в сообщении #1576743 писал(а):

нужно факторизацию проводить...

Факторизацию нужно, а остальное зачем? Уверяю Вас, проще непрерывных дробей ничего нет.

$7\cdot 17/23=5,5,1,3$
$7\cdot 23/17=9,2,8$
$17\cdot 23/7=55,1,6$

Проверять в общем виде придется, конечно, но тут уже на глаз видно (по последнему знаку), что решение в первой строке. Чем меньше последний знак, тем меньше расстояние между $x$ и $y,$ т.е. $v.$

$5,5,1,2=\dfrac{5}{1},\dfrac{26}{5},\dfrac{31}{6},\dfrac{88}{17}.$ $x=31\cdot 6=186,y=88\cdot 17=1496$ (подается в четном виде), $v=1496-186=1310.$ Проверяем остальные $v$ тем более, что они нужны для для вычисления квадратов по другим $R.$

$9,2,7=\dfrac{9}{1},\dfrac{19}{2},\dfrac{142}{15}.$ $x=19\cdot2=38,y=142\cdot15=2130,v=2130-38=2092.$

$55,1,5=\dfrac{55}{1},\dfrac{56}{1},\dfrac{335}{6}.$ $x=56\cdot 1=56,y=335\cdot 6=2010,v=2010-56=1954.$

$$2092^2\equiv 1954^2\equiv 1310^2\equiv 1 \mod 2737.$$

Дальше Вы что-то сильное написали, но боюсь, на практике погрешности придется вычислять точные. Мало ли...

[juna]

Andrey A в сообщении #1576762 писал(а):

Уверяю Вас, проще непрерывных дробей ничего нет.

А как из всего этого далее найти первое решение с $R=8$: $930^2\equiv 8\mod 2737$? Перебором?

[Andrey A]

Да. Против этого лома нет приема. Можно рассматривать остатки вида $p^2-4mq^2=R$ разложения $\sqrt{m}$, но хорошим назвать такой выход что-то мешает. Так ведь поэтому и задача не выдыхается!

[juna]

Andrey A в сообщении #1576774 писал(а):

Против этого лома нет приема.

Таки вроде есть, я о нем и говорю. Задача $x^2\equiv R\mod m$ с составным модулем и заданным $R$ решается. Вот передо мной книжка лежит: Е.Б. Маховенко. / Теоретико-числовые методы в криптографии: https://vk.com/wall-101965347_70169

Вот и решатели беспереборные есть все там же: https://www.alpertron.com.ar/QUADMOD.HTM

То-то я смотрю, что там любые квадратичные диофантовые уравнения (с большими коэффицентами) в лёт решаются в сравнении с их якобы форком для maxima (а там оказывается простой перебор вместо аналитического решения).

[Andrey A]

Символы Лежандра, Якоби отвечают на вопрос вычет или невычет? Но "хорошее" решение сравнения $x^2\equiv R\mod m$ предполагает способность найти все $x$, а это равносильно факторизации или тесту на простоту. Если бы это было возможно малой кровью, думаю, я бы знал. Но спасибо, почитаю.

[juna]

Andrey A в сообщении #1576779 писал(а):

факторизации

Необходимость факторизации естественна и она не обходится малой кровью, иначе RSA приказал бы долго жить.

-- Ср янв 11, 2023 16:49:30 --

Andrey A в сообщении #1576779 писал(а):

Символы Лежандра, Якоби отвечают на вопрос вычет или невычет?

Ну да. Символ Якоби вряд ли здесь подойдет. Нужно факторизовать и для каждого простого модуля вычислять символ Лежандра, если все равны 1, то для данного $R$ есть решение.

-- Ср янв 11, 2023 16:53:57 --

Andrey A в сообщении #1576779 писал(а):

Но "хорошее" решение сравнения $x^2\equiv R\mod m$ предполагает способность найти все $x$

По ссылке, которую я привел, рассматривается пример на стр.77 и далее.

[Andrey A]

Полистал. Хорошее обозрение современных методов факторизации и тестирования, в том числе связанные с теорией эллиптических кривых, $\rho$-Полларда и т.д. Ага, она у меня есть. Но что значит "решается"? Вот 6-я глава посвящается дискретному логарифмированию. Задача нахождения наименьшего Фибоначчи кратного данному модулю совершенно аналогична, там тоже есть свои квазипростые и т.д. Она у меня тоже решена. Тупо вычисляется наименьшее число, домножающее модуль до ближайшего кратного Фибоначчи (цепной дробью, естественно). Ничего быстрее и представить не могу. И что? Один из методов, не более. Вы предлагаете употребить сложные методы для решения настоящей задачи. А я всё думаю, нельзя ли с помощью этой задачи упростить методы?

juna в сообщении #1576781 писал(а):

Необходимость факторизации естественна и она не обходится малой кровью, иначе RSA приказал бы долго жить.

Вот давайте ему и поможем ) Или Вас интересуют лёгкие задачи?

Andrey A в сообщении #1576792 писал(а):

Хорошее обозрение современных методов факторизации...

Это мне Герман-Нестеренко дорогу переехали. Маховенко скачал, тут больше к теории чисел отношения, но о дискр. логарифмировании глава тоже есть. Спасибо!

[Утундрий]

(Оффтоп)

Надо будет на досуге и себе завести птичью тему. Что-нибудь вроде разложения кубического корня свободного от кубов целого числа на сумму трёх квадратных корней свободных от квадратов целых чисел.