Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3 4 5   вперед  Ctrl      все
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Чтобы такой результат получился (всего 5 или очень немного чисел на большое кольцо),
необходимо решить следующее уравнение:

найти g, n, b для

g^b =1 mod (n^2)
3 янв 20, 13:31    [22053077]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6017
Gennadiy Usov,

всё довольно просто
посмотри как перемножаются числа вида vp+1 в кольце p^2

[(v1 p+1) * (v2 p+1)]|p^2 = [v1* v2 p^2+(v1 + v2) p +1]|p^2 = [(v1 + v2) p +1]|p^2

находим n' : n*n' - v1 * p = 1

берём члены нашего кольца g(1) и g(-1)
находим v2 : g(1) * g(-1) = v2 p + 1

исходя из правила умножения получаем:

x = [[v2-1]|p * v1] | p + i*p


все делители n будут лежать в множестве [g(1) ^ x] | p^2

для отсечки лишних нужно выполнение условия [g(1) ^ x] < n и [g(-1) ^ x] < n

т.е. если мы имеем такой p для которого можно вывести "итератор" по числам <p в кольце p^2, то мы можем разложить на множители любое число n < p
3 янв 20, 17:49    [22053148]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
kealon(Ruslan)
находим n' : n*n' - v1 * p = 1
Пока это всё тяжело для меня.

Есть n' и n. Или это одно число?

И из какого уравнения они (оно) определяются?
Ведь известны (?) пока v1, v2, р.
3 янв 20, 18:20    [22053161]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6017
Gennadiy Usov,

находим n' и v1 с помощью расширенного алгоритма Евклида, n' обычно обозначают n-1|p, он равен n^(fi(p)-1)|p = n^(p-2)|p если p простое

x находим из полученного ранее соотношения [(vp+1)^x]|p^2 = [vx p +1] |p^2
подменив
v*x -> (n'*n - 1)/p
v -> (G(1)*G(-1) - 1)/p
собственно опять же с помощью расширенного алгоритма Евклида
3 янв 20, 19:29    [22053191]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
kealon(Ruslan)
находим n' : n*n' - v1 * p = 1

находим n' и v1 с помощью расширенного алгоритма Евклида, n' обычно обозначают n-1|p, он равен n^(fi(p)-1)|p = n^(p-2)|p если p простое
Как я понял, расширенный алгоритм Евклида находит коэффициенты для двух чисел, у которых есть общий делитель.

Но р - число простое, а n < р.
Следовательно, у n и р не может быть общих делителей.

Или я что-то не так понял...
3 янв 20, 20:41    [22053218]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Хотя, есть общий делитель - 1. И поэтому можно найти коэффициенты.
Хорошо.

А что у нас известно: n и p. А что ещё?

Тогда можно получить некоторые числа а и b.
Почему эти числа будут v1 и n', которые определены по формулам?
3 янв 20, 20:50    [22053224]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6017
Gennadiy Usov
Хотя, есть общий делитель - 1. И поэтому можно найти коэффициенты.
Хорошо.

А что у нас известно: n и p. А что ещё?

Тогда можно получить некоторые числа а и b.
Почему эти числа будут v1 и n', которые определены по формулам?

1. ничего
2. в общем-то не будут
алгоритм даёт a,b,d: an + bp = d
где d будет =1, так как n и b взаимнопростые - это НОД(n,p)
и либо a, либо b будет меньше нуля, но об этом обычно не пишут, так как довольно очевидно, что знак можно поменять, добавив np или -np
[an + np] + [bp - np] = d

приводишь результаты к виду
n*n' - v1 * p = 1
и всё
4 янв 20, 08:12    [22053313]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Попробую "перевести" на циферки. Так проще.

n = 45, p = 61

Тогда n' = 45, v1 = 14.

g(1) = 2 и g(-1) = 2197...

Пока всё верно?
4 янв 20, 09:19    [22053320]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
тороплюсь:

Тогда n' = 19, v1 = 14.
4 янв 20, 09:21    [22053321]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6017
Gennadiy Usov
тороплюсь:

Тогда n' = 19, v1 = 14.
верно: 14 * 61 = 856 = 855 + 1 = 19*45 + 1

Gennadiy Usov

g(1) = 2 и g(-1) = 2197...

Пока всё верно?
g должен быть от p, а не от p^2, т.е. 31: 2 * 31 = 1 * 61 + 1
для теста пока пойдёт и он
"итератора" то, про который я говорил - 22052583, у нас пока так и нет

соответственно x=14 + i*p

Сообщение было отредактировано: 4 янв 20, 09:39
4 янв 20, 09:34    [22053322]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
kealon(Ruslan)
исходя из правила умножения получаем:

x = [[v2-1]|p * v1] | p + i*p
Здесь необходимо уточнение насчёт исходного уравнения, для которого справедливо правило
kealon(Ruslan)
все делители n будут лежать в множестве [g(1) ^ x] | p^2
Допустим.

Но если следовать этой логике:
для p = 11 быстро найдем (что-то), хотя n должно быть меньше р.
а для р = 2^3217-1 будем искать очень долго.
4 янв 20, 16:50    [22053417]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6017
Gennadiy Usov,

ну так у нас и итератора аналитического нет.
Что проще? умножать постоянно непонятно сколько или вычислить несколько вариантов пусть даже в очень большой степени?
4 янв 20, 18:37    [22053445]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6017
т.е. если бы мы, например, знали что все числа <p пробегаются с помощью формулы gk*a|p2 решение системы было бы тривиально
4 янв 20, 18:51    [22053453]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
kealon(Ruslan)
соответственно x=14 + i*p
А что должно получиться, если применить mod p для этой формулы?
У меня получилось, что достаточно проверить i от 1 до 23, далее повтор.
Какие числа "выберем" из этих 23-х чисел?

Как известно, делители (множители) числа 45 - числа 5 и 9.
4 янв 20, 20:33    [22053468]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6017
Gennadiy Usov
kealon(Ruslan)
соответственно x=14 + i*p
А что должно получиться, если применить mod p для этой формулы?
У меня получилось, что достаточно проверить i от 1 до 23, далее повтор.
Какие числа "выберем" из этих 23-х чисел?

Как известно, делители (множители) числа 45 - числа 5 и 9.
а там есть пары с обоими значениями меньше 61?
нет ????, значит наш заход неверен
4 янв 20, 21:50    [22053480]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
kealon(Ruslan)
Gennadiy Usov
А что должно получиться, если применить mod p для этой формулы?
У меня получилось, что достаточно проверить i от 1 до 23, далее повтор.
Какие числа "выберем" из этих 23-х чисел?

Как известно, делители (множители) числа 45 - числа 5 и 9.
а там есть пары с обоими значениями меньше 61?
нет ????, значит наш заход неверен
Повторно вопрос: какие числа должны получиться (конкретно)?

А ошибка в главном: в начальной постановке вопроса
kealon(Ruslan)
посмотри как перемножаются числа вида vp+1 в кольце p^2

[(v1 p+1) * (v2 p+1)]|p^2 = [v1* v2 p^2+(v1 + v2) p +1]|p^2 = [(v1 + v2) p +1]|p^2

Какое может иметь отношение данная формула к ситуации, когда n < p?

Эта формула определяет числа, намного большие р.
5 янв 20, 06:40    [22053595]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Кстати, а как можно отредактировать сообщение?
Чтобы не делать повторные сообщения.

На этом топике было несколько таких редактирований.
5 янв 20, 07:11    [22053596]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
У тебя кнопка внизу есть.
Но она доступна сразу после публикации.
5 янв 20, 10:36    [22053637]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
mayton
У тебя кнопка внизу есть.
Но она доступна сразу после публикации.
Спасибо!

Нашел кнопку!

Сообщение было отредактировано: 5 янв 20, 11:18
5 янв 20, 11:17    [22053649]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6017
Gennadiy Usov
А ошибка в главном: в начальной постановке вопроса
kealon(Ruslan)
посмотри как перемножаются числа вида vp+1 в кольце p^2

[(v1 p+1) * (v2 p+1)]|p^2 = [v1* v2 p^2+(v1 + v2) p +1]|p^2 = [(v1 + v2) p +1]|p^2

Какое может иметь отношение данная формула к ситуации, когда n < p?

Эта формула определяет числа, намного большие р.
начальная постановка моего вопроса была: "как пробежать по всем числам меньше p в кольце p^2?"
ты спросил "зачем?"
я привёл это выражение, которое дополняет систему

а по поводу того, что числа > p, так это произведение двух чисел
мы же пытаемся получить n'*n через произведение двух чисел - если итератор пробегаетcя по всем числам, то он обязательно одним из чисел зацепит делитель либо n либо n'
5 янв 20, 19:51    [22053824]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
kealon(Ruslan)
мы же пытаемся получить n'*n через произведение двух чисел -
если итератор пробегаетcя по всем числам,
то он обязательно одним из чисел зацепит делитель либо n либо n'
И как, "зацепило" в рассматриваемом примере?
5 янв 20, 20:49    [22053836]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6017
Gennadiy Usov,

так у тебя есть итератор? так что вполне ожидаемый результат

Сообщение было отредактировано: 5 янв 20, 21:02
5 янв 20, 21:01    [22053837]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
kealon(Ruslan)
Gennadiy Usov,
так у тебя есть итератор? так что вполне ожидаемый результат
Итератор должен иметь два момента:

1. Что он ищет
2. Как он ищет (формула поиска).

Так что из этого есть в задаче 22053148?
6 янв 20, 09:20    [22053942]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6017
Gennadiy Usov,

эта формула даёт n'*n,
даёт?
даёт ...
а то что подаёшь на входе фигню, и получаешь фигню - вполне закономерно
6 янв 20, 11:11    [22053963]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
kealon(Ruslan)
Gennadiy Usov,
эта формула даёт n'*n,
даёт?
даёт ...
а то что подаёшь на входе фигню, и получаешь фигню - вполне закономерно
Я так понимаю, последняя фраза - это самокритика.

Так ты проверял свои умозаключения или просто выплеснул мысли вслух?

На форуме мне всегда говорили: сначала проверь на своём ПК, а потом сообщай остальным.

Сообщение было отредактировано: 6 янв 20, 11:28
6 янв 20, 11:26    [22053966]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3 4 5   вперед  Ctrl      все
Все форумы / Программирование Ответить