2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 8, 9, 10, 11, 12  След.
 
 Re: √m≈√x+√y
Сообщение09.01.2023, 11:54 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
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.$

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение10.01.2023, 01:39 
Заслуженный участник
Аватара пользователя


07/03/06
1898
Москва
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$ выражаются одинаковой формой.

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение10.01.2023, 05:11 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
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.$

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение11.01.2023, 00:26 
Заслуженный участник
Аватара пользователя


07/03/06
1898
Москва
Andrey A в сообщении #1576655 писал(а):
Вы треугольники еще не смотрели?

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

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение11.01.2023, 03:13 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
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)$$ и сравниваем погрешности.

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение11.01.2023, 12:33 
Заслуженный участник
Аватара пользователя


07/03/06
1898
Москва
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}.$

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение11.01.2023, 13:47 
Заслуженный участник
Аватара пользователя


07/03/06
1898
Москва
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}$$


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

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение11.01.2023, 14:31 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
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.$$
Дальше Вы что-то сильное написали, но боюсь, на практике погрешности придется вычислять точные. Мало ли...

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение11.01.2023, 15:29 
Заслуженный участник
Аватара пользователя


07/03/06
1898
Москва
Andrey A в сообщении #1576762 писал(а):
Уверяю Вас, проще непрерывных дробей ничего нет.

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

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение11.01.2023, 15:57 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение11.01.2023, 16:09 
Заслуженный участник
Аватара пользователя


07/03/06
1898
Москва
Andrey A в сообщении #1576774 писал(а):
Против этого лома нет приема.

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

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

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

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение11.01.2023, 16:41 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение11.01.2023, 16:44 
Заслуженный участник
Аватара пользователя


07/03/06
1898
Москва
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 и далее.

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение11.01.2023, 17:42 
Заслуженный участник
Аватара пользователя


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

Andrey A в сообщении #1576792 писал(а):
Хорошее обозрение современных методов факторизации...
Это мне Герман-Нестеренко дорогу переехали. Маховенко скачал, тут больше к теории чисел отношения, но о дискр. логарифмировании глава тоже есть. Спасибо!

 Профиль  
                  
 
 Re: √m≈√x+√y
Сообщение11.01.2023, 18:22 
Заслуженный участник
Аватара пользователя


15/10/08
11536

(Оффтоп)

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 180 ]  На страницу Пред.  1 ... 8, 9, 10, 11, 12  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group