Проверка остатков множителей по модулю простого числа

[flacs]

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

Подход к факторизации целых чисел, может быть гипотетически основан на подборе остатков по модулю множителей число $N$.
Подобрав остатки по модулям простых чисел и применив Китайскую теорему об остатках, можно получить нужные множители $p, q$

Причем количество простых чисел будет ограничено произведением этим простых чисел, результат которых превышает $N$.

т.е. $p_1 \cdot p_2 \cdot ... \cdot p_n \geqslant N$

Получить остаток по модулю, нет проблем: $N\mod p = r$

Сам подбор пар для $r$ относительно прост и может быть сгенерирован сервисом wolfram alpha.

https://www.wolframalpha.com/input/?i=pq+mod+3+%3D+1 // пример для модуля 3, при произведении дающий остаток 1

Главная вопрос состоит в том, чтобы подобрать верные пары, да так чтобы проверка представляла собой алгоритм с полиномиальной сложностью.

Я начал с первого нечетного простого числа (3) , так как для простого число 2 результат тривиален.

Рассмотрим пример выше:

Мы можем получить остаток 1 по модулю 3, только в двух случаях:

$(3x+1)(3y+1) = 3z+1;$

$(3x+2)(3y+2) = 3z+1;$

И мне удалось найти метод, позволяющий быстро проверить, какие остатки по модулю 3 содержат два множителя.

Для этого я нахожу решения для уравнения $x^2+3y^2=N$
Чтобы найти решения быстро, я применяю алгоритм Корначи: https://en.wikipedia.org/wiki/Cornacchia%27s_algorithm

Если решения в целых числах есть, то число образовано - $(3x+1)(3y+1) = 3z+1;$, если нет то $(3x+2)(3y+2) = 3z+1;$

А теперь интересующие вопросы:

1) Можно ли доказать что при случае $(3x+1)(3y+1) = 3z+1;$, всегда имеются решения? Не нашел контрпримера.
2) Какая существует квадратичная форма для второй пары $(3x+2)(3y+2) = 3z+1;$. Мне не удалось найти (возможно их несколько).

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

Заранее, спасибо!

[Sonic86]

Ответа Вы скорее всего не дождетесь, потому Ваш текст малосвязный:

flacs в сообщении #1419418 писал(а):

нужные множители $p, q$

Как $N$ связано с $p,q$? $p,q$ - произвольные? $N$ - произвольное?

flacs в сообщении #1419418 писал(а):

Получить остаток по модулю, нет проблем: $N\mod p = r$

Конечно нет проблем: $p$ по условию делитель $N$, значит $N \bmod p = 0$.

flacs в сообщении #1419418 писал(а):

Причем количество простых чисел будет ограничено произведением этим простых чисел, результат которых превышает $N$.

т.е. $p_1 \cdot p_2 \cdot ... \cdot p_n \geqslant N$

Как вообще эти $p_j$ связаны с $N$? Само утверждение тоже понять я не могу.

flacs в сообщении #1419418 писал(а):

Сам подбор пар для $r$

Откуда уже пары взялись?

flacs в сообщении #1419418 писал(а):

Рассмотрим пример выше:

И где этот пример?

flacs в сообщении #1419418 писал(а):

Мы можем получить остаток 1 по модулю 3, только в двух случаях:
$(3x+1)(3y+1) = 3z+1;$
$(3x+2)(3y+2) = 3z+1;$

У кого мы можем получить остаток 1? Откуда вылезли $x,y,z$, как они связаны с $N$?

И т.п., непонятно практически ничего. Попробуйте сформулировать все заново, перепроверьте связность текста.

[iifat]

flacs в сообщении #1419418 писал(а):

Сам подбор пар для $r$ относительно прост и может быть сгенерирован сервисом wolfram alpha

Если я правильно понял, подбор пар прост не относительно, а вполне себе абсолютно: поскольку в группе остатков по модулю простого $p$ все делятся на всех (кроме нуля), получатся ровно $p-1$ пар $(i,\frac ri)$. И как это нам поможет?

[Cash]

flacs, чтобы понять ваш метод - разберите на примере одного числа. Возьмите, например, 5069 и покажите пошагово

[Andrey A]

flacs в сообщении #1419418 писал(а):

Для этого я нахожу решения для уравнения $x^2+3y^2=N$

Тут ключевая буква "я" в слове решения. Если найдено хотя бы два решения $(x_1,y_1);(x_2,y_2)$, то $N$ составное, но совершенно не обязательно делится именно на $3$, это знал еще Ферма. Остатки тут причем, конечно, но перебирать их необходимости нет: $\left\{\begin{matrix} x_1^2 \equiv -3y_1^2\\ x_2^2 \equiv -3y_2^2 \end{matrix}\right.$ откуда $(x_1x_2)^2 \equiv (3y_1y_2)^2$ и $(x_1y_2)^2 \equiv (x_2y_1)^2\ \mod N$. Для простого $N$ такое невозможно (если бы вместо $3$ стояло $-3$, то сколько угодно). Кроме тройки любое простое $N$ вида $6k+1$ удовлетворяет Вашему уравнению, но только один раз) А вот их произведения больше: $(a^2+3b^2)(c^2+3d^2)=(ac\pm 3bd)^2+3(ad\mp bc)^2.$

flacs в сообщении #1419418 писал(а):

2) Какая существует квадратичная форма для второй пары...

Универсальная форма вряд ли есть, во всяком случае для положительных коэффициентов. На всякий случай посмотрите здесь (не сочтите за саморекламу).

[flacs]

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

Подход к факторизации целых чисел, может быть гипотетически основан на подборе остатков $r, m$ по модулю простых чисел $P_i$ для множителей $p, q$, составляющих число $N$.

Попытаюсь тезисами и на примере, описать суть метода:

1) Любое число может быть представлено произведением: $p \cdot q = N$;
2) Числа $p, q$, имеют остатки по модулям простых чисел $P_i$;
3) Причем количество простых чисел $P_i$, взятых в качестве базиса будет ограничено произведением этих простых чисел $P_i$, результат, которых превышает $N$.

т.е. $p_1 \cdot p_2 \cdot ... \cdot p_n \geqslant N$

Далее объясню на примере: $13 \cdot 37 = 481$

Базис простых чисел $P_i$ ограничен: $3, 5, 7, 11$,

так как:

$3 \cdot 5 \cdot 7 \cdot 11\geqslant 481$

Далее для $p$:

$13 \mod 3 = 1$

$13 \mod 5 = 3$

$13 \mod 7 = 6$

$13 \mod 11 = 2$


$q$:

$37 \mod 3 = 1$

$37 \mod 5 = 2$

$37 \mod 7 = 2$

$37 \mod 11 = 4$

$N$:

$481 \mod 3 = 1$

$481 \mod 5 = 1$

$481 \mod 7 = 5$

$481 \mod 11 = 8$

Т.е. получится:

$1 \cdot 1 = 1 // \mod 3$

$3 \cdot 2 = 1 // \mod 5$

$6 \cdot 2 = 5 // \mod 7$

$2 \cdot 4 = 8 // \mod 11$

Грубо говоря для каждой строчки выполняется уравнение:

$(P \cdot x + r)(P \cdot y + m)= P \cdot z + k$

где,

$P$ - модуль простого числа
$r,m,k$ - остатки по модулю простого числа
$x,y,z$ - "База" по модулю простого числа

Имея верные $r, m$ для каждого $P_i$ - можно "вычислить" множители $p, q$, решая систему уравнений по модулю, используя Китайскую теорему об остатках.

https://ru.wikipedia.org/wiki/%D0%9A%D0 ... 0%B0%D1%85

Сам подбор пар для $k$ относительно прост и может быть сгенерирован сервисом wolfram alpha.

Пример для: $p \cdot q \mod 3 = 1$

https://www.wolframalpha.com/input/?i=pq+mod+3+%3D+1

Аналогично, можно вписать другие модули $P_i$ и остатки $k$.

Главная проблема состоит в том, чтобы подобрать верные $r, m$ для каждого $P_i$, да так чтобы проверка представляла собой алгоритм с полиномиальной сложностью.

Итак, рассмотрим пример для $P = 3; k = 1$

$p \cdot q \mod 3 = 1$

Мы можем получить остаток 1 по модулю 3, только в двух случаях:

1) $(3x+1)(3y+1) = 3z+1;$

2) $(3x+2)(3y+2) = 3z+1;$

Именно для $P=3$ и $k=1$ мне удалось найти способ, как быстро проверить, какая пара $r, m$ используется для данного соотношения:

$(3 \cdot x + r)(3 \cdot y + m)= 3 \cdot z + 1$

Для этого я нахожу решения для уравнения: $x^2+3y^2=N$

Чтобы найти решения быстро, я применяю алгоритм Корначи: https://en.wikipedia.org/wiki/Cornacchia%27s_algorithm

Если решения в целых числах есть, то $r=1; m=1;$, если нет, то $r=2; m=2;$

А теперь интересующие вопросы:

1) Можно ли доказать что при случае $r = 1; m = 1; k = 1; $, всегда имеются решения? Не нашел контрпримера.
2) Какая существует квадратичная форма для второй пары $r = 2; m = 2; k = 1$. Мне не удалось найти (возможно их несколько).

Интуитивно понимаю, что разобравшись в данных вопросах можно перейти к другим остаткам $k$ и модулям $P_i$

Заранее, спасибо!

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Дискуссионные темы (М)»
Причина переноса: в соответствующий раздел

[Andrey A]

flacs в сообщении #1419418 писал(а):

... затронуть тему факторизации целых чисел

Если имеется всего одно представление $M=ac^2+bd^2$, то в целях факторизации легче всего на мой взгляд проверять $\gcd (M,ab+k^2)$, $k=0,1,2,...\ ,$ так как $-ab$ есть квадратичный вычет по $\mod M$, а значит и по простым делителям $M.$