решить уравнение в целых числах

[Руст]

dmd писал(а):

Вы, конечно, во всем правы, увы мне:(

Вот это уравнение:
$24rx + 1 = y^2$, где $r$ - произведение искомых простых.
Если ${x_m,y_m}$ - минимальное решение этого уравнения, то
$i=IntegerPart[(y_m-1)/4]$, либо $i=IntegerPart[(y_m-1)/4]\pm 1$ гарантировано содержит один из искомых простых множителей: $GCD[i,r]$.

Не понял, что хотите сказать (i содержит один из простых делителей gcd(i,r) - это всегда ).
Если число y не делится на два и на 3, то его квадрат всегда дает остаток 1 при делении на 24. Наверно поэтому из D выделили 24.

[dmd]

Дело в том, что я не подбирал искусственно способ представления D, а вывел это уравнение естественным образом, просто рассматривая задачу в ее динамике.

Вот примеры:

$r=17*31=527$
наименьшее решение уравнения $24rx+1=y^2$ будет {11,373}, т.е. $y_m=373$
тогда $i=IntegerPart[(y_m-1)/4]=93=3*31$ - т.е. $i$ содержит один из простых делителей $r$, равный 31
или можно $GCD[i,r]=GCD[93,527]=31$

$r=23*53=1219$
минимальное решение нашего диофантова уравнения будет {65,1379}, т.е. $y_m=1379$
тогда $i=IntegerPart[(1379-1)/4]+1=345=3*5*23$ - т.е. $i$ содержит 23 - делитель $r$, или $GCD[345,1219]=23$

$r=112303*898423=100895598169$
наименьшее решение {16815633555,201789399491}
$i=IntegerPart[(201789399491-1)/4]+1=50447349873=3*3*17*367*898423$ $GCD[50447349873,100895598169]=898423$

Если попробовать таким образом разложить числа $r=2^{261}+3$ и $r=2^{262}+3$, то для первого Mathematica решает это диофантово уранение за несколько секунд, а для второго - около 14мин на моем P3. При этом первое число содержит только один достаточно большой простой множитель и несколько достаточно малых множителей, а второе число - два больших множителя и несколько малых. Из этого сделался вывод, что скорее всего Mathematica решает такие диофантовы уравнения неким подбором, раз второй случай был много дольше. До этого я понятия не имел, решаются такие уравнения аналитически или нет и проще ли их решать, чем факторизовать, по ходу все выяснилось - мы дилетанты как всегда ходим кругами:). Кучу литературы переназакачал по теории чисел - нигде толком такие уравнения не рассматриваются. Прискорбно то, что ни одна из свободных систем математики не умеет решать нелинейные диофантовые уравнения, хотя бы тем же перебором. В Mathematica их можно решать командой Reduce вот так:
Reduce[f(x,y)==0 && Element[x|y, Integers]]

[Руст]

Во первых 373 не является минимальным, например 527-373<373. Во вторых, для любого решения кроме 1, y=1(mod d) для некоторого d и равно -1(mod D/d), т.е. (y-1,D)=d даст некоторый делитель d и позволит факторизовать.
Что касается литературы по факторизации, то следует смотреть книжки не по теории чисел, а книжки по криптографии, например: Смарт. Криптография, О,Н. Василенко "Теоритико-числовые алгоритмы в криптографии.

[dmd]

Руст писал(а):

Во первых 373 не является минимальным, например 527-373<373.

Если $y=527-373=154$, то $x$ не будет целым для уравнения $24*527*x+1=y^2$, мы же ищем целочисленные решения. Для этого уравнения минимальным нетривиальным решением является только $x_m=11,y_m=373$.

[dmd]

Пусть $d=ab$

$a,b$ - простые числа.

Все нетривиальные решения уравнения $x^2-1=dy$ выражаются формулами:

$x=x_{1,2}+dk$

$y=y_{1,2}+2x_{1,2}k+dk^2$

где $k$ - произвольное целое,
$\{x_1,y_1\}$, $\{x_2,y_2\}$ - пара наименьших нетривиальных решений, таких что $0<x_1<x_2<d$.

При этом наблюдаются следующая картина:

$x_1+x_2=d$

$x_2-x_1=y_2-y_1=r$

$r^2=4\pmod d$

$r=\pm 2\pmod {a,b}$

$z=x_2 \% y_2$

$x_{1,2} y_{2,1}=-1\pmod z$


Еще иксы решений уравнения Пелля $X^2-1=dY^2$ являются подмножеством иксов решений исходного уравнения $x^2-1=dy$.
Тогда $x=X \% d$ иногда даёт нетривиальное решение.

[Руст]

dmd в сообщении #507073 писал(а):

Пусть $d=ab$

$a,b$ - простые числа.

Все нетривиальные решения уравнения $x^2-1=dy$ выражаются формулами:

$x=x_{1,2}+dk$

$y=y_{1,2}+2x_{1,2}k+dk^2$

где $k$ - произвольное целое,
$\{x_1,y_1\}$, $\{x_2,y_2\}$ - пара наименьших нетривиальных решений, таких что $0<x_1<x_2<d$.

Утверждение в таком виде не верно. Надо различать случаи $a=b$, $a\not =b$. Еще четное $d$ или нет.

[dmd]

Это да, надо было написать:

$a,b$ - различные простые >2

[Руст]

Вообще количество решений $0<x<d$ равно $2^{v(d)}$, где $v(d)$ количество различных простых делителей d. Есть одно но. Когда $8|d$ простому числу 2 соответствует сразу 4 решения и количество решений будет $2^{v(d)+1}.$

[Батороев]

(Оффтоп)

maxal в сообщении #40453 писал(а):

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

Действительно, похоже конечная цель - факторизация числа $D$.
Я ранее в своих измышлениях уже приходил к парадоксальному выводу о том, что "Чтобы упростить факторизацию числа, это число необходимо усложнить".
Но для этих целей использовать $Dx=y^2-1$ - не совсем благодарное дело.
Дело в том, что $x$ в выражении $Dx=y^2-1$ должно быть таким, что $Dx=mn$, где $|m-n|=2$. Добиться этого очень сложно.
На мой взгляд, более продуктивна факторизация по $Dx=y^2-z^2$, где $z<\sqrt {Dx}$ (факторизация по Ферма с усложнением числа $D$). При этом $x$ должен быть произведением, как можно большего числа малых простых множителей и их степеней, соответственно, возможные делители числа $Dx=mn$ будут по величине приближаться друг к другу. Тем самым, $y$ будет минимизироваться.

[Klad33]

Мне кажется такое есть решение:

$D=V^2-1$

$x=1$

$y=V$

Где V - любое целое число.

[bot]

А также $D=1, x=V^2-1, y=V$, где $V$ - любое целое число.

[Klad33]

Нет, Ваше слишком частное решение страдает тем, что принимается только одно D, а у меня - группа чисел D, при которых есть "минимальное" решение. Разница, однако-с!

[bot]

Klad33 в сообщении #507326 писал(а):

Нет, Ваше слишком частное решение страдает тем ...

Нет, не тем, а от того. Оно как и Ваше страдает от того, что не интересует ТС.

[dmd]

dmd в сообщении #507073 писал(а):

При этом наблюдаются следующая картина:

$x_1+x_2=d$

$x_2-x_1=y_2-y_1=r$

И, кстати, $x_2^2-x_1^2=dr$

или

$x_2^2\equiv x_1^2\pmod d$

[dmd]

Еще

$rx_{1,2}\equiv \mp 2\pmod d$

-- Сб ноя 26, 2011 18:37:26 --

$d^2-r^2=4x_1x_2$

$x_1x_2\equiv -1\pmod d$