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

Откуда:
Сообщений: 2360
 		Эпиграф:
Barlone↑
Эратосфен - это скучно. Разобрали бы лучше решето числового поля ну или хотя бы квадратичное решето
До «решета» ещё далеко, пока изучаю методы попроще. https://old.kpfu.ru/f9/bibl/Monograph_ishm.pdf
Кстати, неплохая книга для изучения факторизации.

Очень интересный метод (р – 1)-метод Полларда:
перемножаем несколько степеней минимальных простых чисел (по модулю n) и
с помощью н.о.д. сразу определяется минимальный множитель.
Данный метод годится только для чисел, у которых один из множителей мал. А другой сколь угодно большой.

Пробные расчеты показали, что можно проводить следующие исследования:
- зависимость количества базовых простых чисел от величины малого множителя;
- зависимость предела степеней каждого базового простого числа от величины малого множителя.
Получается, что можно построить некоторую функцию по двум переменным,
отражающую предел по определению множителей.

Пример:
n = 1427*23456234562345623461
Кстати, второй множитель может быть сколь угодно большим.
Первый множитель определяется, если имеем более 10 первых простых чисел, и
если предел степеней больше 30 (добавляется простое число 31).

Далее, из перечня базовых простых чисел от 2 до 31 нельзя убирать числа 2, 23, 31,
а все остальные можно: останутся только числа 2, 23, 31.
И так далее…

Получается, что этот метод может соперничать с методом предварительного деления исследуемого числа
(до определённого простого числа):
для проверки делимости на 225 простых чисел (до 1427 - простое число) достаточно от 3 до 11 простых чисел
20 дек 19, 06:39    [22044865]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Barlone
Member

Откуда:
Сообщений: 1451
 		Не перемножаем несколько степеней простых чисел по модулю n, а возводим некоторое начальное число в степень, равную этому самому произведению степеней маленьких простых.
20 дек 19, 09:05    [22044925]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Barlone
Member

Откуда:
Сообщений: 1451
 		И метод годится не только для чисел, у которых один из множителей мал, но и для чисел, у которых функция Эйлера для одного из множителей раскладывается на маленькие сомножители. Например, множитель - число Прота с маленьким k (но сам по себе большой) можно найти.
20 дек 19, 09:49    [22044948]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
Barlone↑
Не перемножаем несколько степеней простых чисел по модулю n,
а возводим некоторое начальное число в степень, равную этому самому произведению степеней маленьких простых.
Согласен, немного поторопился.

В результате:

"перемножаем несколько степеней минимальных простых чисел,
возводим некоторое начальное число (например, 2) в степень, равную полученному произведению (по модулю n) и
с помощью н.о.д. сразу определяется минимальный множитель."

Кстати, ещё можно "поиграть" этими основаниями степеней.
(в предыдущий раз это помогло)
20 дек 19, 11:35    [22045055]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		В продолжение рассмотрения темы (р – 1)-метода Полларда попробовал составить программу:
перебор всех простых чисел, начиная с 3, до некоторого числа,
и для каждого из этих чисел увеличивал В - предел Полларда.
И при этом данные числа умножал на очень большое простое число.

Оказалось, что для того, чтобы определить множители большого числа,
равные от 3 до 101 (простые числа), достаточно применить В = 27.
Для определения множителей, равных от 3 до 1000, достаточно применить В = 882.
Для определения множителей, равных от 3 до 2000, достаточно применить В = 1902.
Для определения множителей, равных от 3 до 5000, достаточно применить В = 8732.

Причем, для определения множителя 4931 достаточно В = 27,
а для определения множителя 4919 достаточно В = 2453.
21 дек 19, 13:53    [22045874]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		При этом, если (р-1)-метод определяет число, это не значит, что получен окончательный ответ.
Этот метод может "зацепить" сразу несколько малых простых чисел.
Причём, некоторые числа могут быть и достаточно большими.

Поэтому необходимо ещё одно применение (р-1)-метода к полученному числу
(при этом число В будет намного меньше).
21 дек 19, 19:37    [22045985]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		А самый плохой вариант для (р-1)-метода:
проверяемое число есть произведение очень большого числа простых небольших чисел.

Тогда (р-1)-метод выдаст это самое число
(если в проверяемом числе есть степень простого числа, то в "ответе" будет это число, но без степени).
..., начинай с начала.
21 дек 19, 21:12    [22046040]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

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

Математики приблизились к решению проблемы простых чисел-близнецов
24 дек 19, 08:38    [22047491]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		Barlone,

в задачах факторизации числа n применяется mod(n).

А если применять mod (а), где а = целое(n^1/2)?

И было ли такое применение?

При этом существенно уменьшается база квадратов чисел.
25 дек 19, 11:08    [22048273]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

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

если ты найдёшь как, зная факторизацию n+1, найти факторизацию n, то ты решишь эту задачу
25 дек 19, 12:31    [22048365]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

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

вот интересный вопрос, есть такое опредление

Первообразные корни
автор
Первообразным корнем по модулю n (primitive root modulo n) называется такое число g, что все его степени по модулю n пробегают по всем числам, взаимно простым с n.

вот интересно, а как пробежаться по этим же числам в модуле n^2
28 дек 19, 23:30    [22050901]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
kealon(Ruslan)↑
Gennadiy Usov,
вот интересный вопрос, есть такое опредление
Первообразные корни
автор
Первообразным корнем по модулю n (primitive root modulo n) называется такое число g,
что все его степени по модулю n пробегают по всем числам, взаимно простым с n.

вот интересно, а как пробежаться по этим же числам в модуле n^2
В статье дано некоректное определение числа а:

"то для любого целого a такого, что ..."

Надо добавить:

а < n.
29 дек 19, 07:51    [22050969]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Barlone
Member

Откуда:
Сообщений: 1451
Gennadiy Usov↑
В статье дано некоректное определение числа а:

"то для любого целого a такого, что ..."

Надо добавить:

а < n.
Не надо. Там математическое определение. Грубо говоря, надо брать остатки с обоих сторон от знака эквивалентности (три черточки). А если совсем точно, два числа принадлежат одному классу вычетов
29 дек 19, 09:02    [22050973]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		Главное - это соотношение чисел n и g.

Число а - это "проверочный материал".
Проверяется от 0 до n - 1.
А далее - просто:
(а + v*n) (mod n) = a.

Зачем усложнять условие?
29 дек 19, 09:19    [22050975]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		А в вики
https://ru.wikipedia.org/wiki/Первообразный_корень_(теория_чисел)
по другому определяются эти корни.

И без всяких "для всех а".
29 дек 19, 09:37    [22050977]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

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

пофиг

а вот

kealon(Ruslan)↑
а как пробежаться по этим же числам в модуле n^2

уже интересный вопрос

Сообщение было отредактировано: 29 дек 19, 11:53
29 дек 19, 11:53    [22051013]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
kealon(Ruslan)↑
вот интересно, а как пробежаться по этим же числам в модуле n^2
Если я правильно понял, то имеем 2^k, 1=<k=<n. (mod n)

Если n = 11, то получаются числа от 1 до 10, причем 1 - два раза.

Если n = 11^2, то нет чисел, кратных 11.
29 дек 19, 13:38    [22051040]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

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

просто хочу записать
((g^k) mod n^2) mod n

более простым способом, без mod n

причём если порядок будет другой - это некритично
29 дек 19, 16:17    [22051105]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
kealon(Ruslan)↑
Gennadiy Usov,
просто хочу записать
((g^k) mod n^2) mod n
более простым способом, без mod n
причём если порядок будет другой - это некритично
Уравнение
((g^k) mod n^2) mod n
"превращается" в уравнение
((g^k) mod n )
30 дек 19, 09:18    [22051314]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

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

думаешь я о таком не догадался? а вот вообще без mod n? только через степени g по модулю n^2
30 дек 19, 23:36    [22052029]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
kealon(Ruslan)↑
Gennadiy Usov,
думаешь я о таком не догадался? а вот вообще без mod n? только через степени g по модулю n^2
Непонятно, что нужно.

Ранее я говорил, что по модулю n^2 имеем в остатке все числа до n^2, кроме кратных n.
31 дек 19, 07:17    [22052098]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

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

что непонятного то?
нужно получить все числа от 1 до n-1 в кольце n^2 операциями степени
1 янв 20, 15:44    [22052583]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
kealon(Ruslan)↑
Gennadiy Usov,

что непонятного то?
нужно получить все числа от 1 до n-1 в кольце n^2 операциями степени
kealon(Ruslan,

что непонятно в моих ответах?

В кольце n^2 (по mod n^2) получаются все числа от 1 до n^2, кроме чисел, кратных n.

Если для этого кольца применить (mod n), то данное кольцо "разбивается" на n колец (mod n),
в каждом из которых все числа от 1 до n-1.
3 янв 20, 07:54    [22053016]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

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

а вот теперь без (mod n) - 22052029
3 янв 20, 09:07    [22053020]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
kealon(Ruslan)↑
Gennadiy Usov,
а вот теперь без (mod n) - 22052029
g = 3, n = 11, цикл чисел, 1, 3, 9, 27, 81.
По остальным g (2, 5,7) получается очень много чисел в кольце.
Кстати, проверил, другие варианты (небольшие). И везде много чисел.

Вариант 3 и 11 - пока единственный, где мало чисел!

И что?
3 янв 20, 13:12    [22053067]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

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

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

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

Откуда: Нижневартовск
Сообщений: 6256
 		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

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

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

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

Откуда: Нижневартовск
Сообщений: 6256
 		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

Откуда:
Сообщений: 2360
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

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

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

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

Откуда: Нижневартовск
Сообщений: 6256
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

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

n = 45, p = 61

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

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

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

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

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

Откуда: Нижневартовск
Сообщений: 6256
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

Откуда:
Сообщений: 2360
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

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

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

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

Откуда:
Сообщений: 2360
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

Откуда: Нижневартовск
Сообщений: 6256
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

Откуда:
Сообщений: 2360
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

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

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

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

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

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

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

Откуда: Нижневартовск
Сообщений: 6256
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

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

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

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

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

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

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

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

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

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

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

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

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

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

Откуда: Нижневартовск
Сообщений: 6256
 		Gennadiy Usov,
неправильно понимаешь
я то проверил, всё что написал, всё верно.

согласен?
6 янв 20, 13:16    [22053999]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
kealon(Ruslan)↑
Gennadiy Usov,
неправильно понимаешь
я то проверил, всё что написал, всё верно.
согласен?
Всё проверил, только одно забыл:
как завершается наш пример - число 45 и р = 61.

Где последние расчёты, где получаемые множители?
6 янв 20, 13:41    [22054006]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

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

а я обещал их найти?
6 янв 20, 20:42    [22054201]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
kealon(Ruslan)↑
Gennadiy Usov,
а я обещал их найти?
А проверка своего метода 22053148?

Как известно:
мужик сказал, ...

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

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

у меня всё сходится


2^14 | p2 = 1500
31^14 | p2 = 3089


[1500 * 3089] | p2 = 855


75	1109	1514			855
136	2157	1672			855
197	471	3154			855
258	698	2736			855
....

насчёт слева: "дай итератор степенной, гуляющий по числам < p" ..., есть ????
6 янв 20, 22:32    [22054255]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		Составил программу факторизации с помощью метода с использованием непрерывных дробей.
https://old.kpfu.ru/f9/bibl/Monograph_ishm.pdf
Исходное 11111 = 41*271.

Перебираю разные простые числа вместо 41 и всё получается.
А на числе 13 - не получается. Интересно!

И на числах 23, 53, 73,...

Что-то мне подсказывает,
что не "проходят" числа, у которых последняя цифра 3.

Хотя прошло 11 * 283.
7 янв 20, 07:58    [22054351]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		Нашел у себя ошибку: не до конца прочитал условие алгоритма.

Если не получилось, то надо продолжать (следующий прогон). И всё.

Взял за основу перебор нечётных числ от 3 до 100 (первое число) и число 257 (второе число).

Обычно множители находятся за 1 - 2 прогона.

Множитель 13 найден за 14 прогонов, 71 - за 40 прогонов, 73 - за 14 прогонов, 83 - за 48 прогонов, 97 - за 53 прогона.
А на 89 - программа зависла - очень много прогонов... (в результате не хватает места для одного из массивов)
7 янв 20, 20:02    [22054618]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		Продолжаю исследования метода с использованием непрерывных дробей.

Взял за основу перебор нечётных числ от 3 до 255 (первое число) и число 257 (второе число).

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

Если количество прогонов ограничить числом 100000 (!), то получается,
что невозможно найти множителей (кроме 1 и произведения двух чисел) для произведения двух чисел,
когда первое число:
89, 139, 151, 181, 197, 211, 229, 239, 251
8 янв 20, 09:45    [22054746]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		Немного подумал и "проскочил" 89.

Например, для числа 167 необходимо 36 прогонов и здесь "фигурируют" числа в районе Е+200.
8 янв 20, 19:19    [22055111]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		Составил программу факторизации с помощью метода с использованием квадратичных форм.
https://old.kpfu.ru/f9/bibl/Monograph_ishm.pdf

Формулы похожие на формулы непрерывных дробей.

Было бы интересно объединить эти два метода,
однако при применении этих методов повторяются числа, по которым нельзя найти множители.

Например, при переборе нечётных чисел от 3 до 1000 (первое число) и для числа 257 (второе число)
не находятся множители по двум методам для чисел:
113, 191, 193, 313, ... и т.д.

Сообщение было отредактировано: 9 янв 20, 09:22
9 янв 20, 09:21    [22055318]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6256
Gennadiy Usov↑
Составил программу факторизации с помощью метода с использованием квадратичных форм.
https://old.kpfu.ru/f9/bibl/Monograph_ishm.pdf

Формулы похожие на формулы непрерывных дробей.

Было бы интересно объединить эти два метода,
однако при применении этих методов повторяются числа, по которым нельзя найти множители.

Например, при переборе нечётных чисел от 3 до 1000 (первое число) и для числа 257 (второе число)
не находятся множители по двум методам для чисел:
113, 191, 193, 313, ... и т.д.

  • это равноценные методы
  • что имеется ввиду?
9 янв 20, 09:42    [22055333]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
kealon(Ruslan)↑
Gennadiy Usov↑
Составил программу факторизации с помощью метода с использованием квадратичных форм.
Было бы интересно объединить эти два метода,
однако при применении этих методов повторяются числа, по которым нельзя найти множители.

Например, при переборе нечётных чисел от 3 до 1000 (первое число) и для числа 257 (второе число)
не находятся множители по двум методам для чисел:
113, 191, 193, 313, ... и т.д.

  • это равноценные методы
  • что имеется ввиду?
Методы не равноценны, потому что у каждого из них свой перечень "неопределяемых множителей".
Эти два перечня имеют некоторое пересечение.

Поэтому объединение этих методов позволит несколько уменьшить количество чисел,
для которых нельзя найти множителей при использовании одного из методов.
9 янв 20, 11:41    [22055439]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		Если взять число 113 х 271 = 30623,
то имеем бесконечный цикл из только 5-6 чисел.
11 янв 20, 07:39    [22057027]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Barlone
Member

Откуда:
Сообщений: 1451
Gennadiy Usov↑
Если взять число 113 х 271 = 30623,
то имеем бесконечный цикл из только 5-6 чисел.
Насколько я помню, в таких случаях умножают число на маленькие простые: 30623*2, 30623*3, ... И при этом может найтись множитель, не равный этому маленькому простому - то есть множитель исходного числа.

Сообщение было отредактировано: 11 янв 20, 10:50
11 янв 20, 10:49    [22057052]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
Barlone↑
Gennadiy Usov↑
Если взять число 113 х 271 = 30623,
то имеем бесконечный цикл из только 5-6 чисел.
Насколько я помню, в таких случаях умножают число на маленькие простые: 30623*2, 30623*3, ... И при этом может найтись множитель, не равный этому маленькому простому - то есть множитель исходного числа.
Спасибо!

Помогло 2 и 23, дальше из простых не смотрел.
11 янв 20, 11:26    [22057064]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		Проверка показала,
что для каждого простого числа, на которое умножается искомое число,
существует свой перечень не определяемых чисел.

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

Откуда:
Сообщений: 2360
 		При составлении алгоритмов всегда было интересно:
какие операции на ПК выполняются быстрее?
А если вместо одного возведения в квадрат выполнять несколько сложений?
и т.д.

Сделал тест на питоне в виде цикла от 1 до 10000000.

Сам цикл (чистый) занимает 0,59 сек.
Если в цикле одно сложение (2**100-1) + (2**101-1), то время работы 1,23 сек.
Если в цикле одно умножение (2**100-1) * (2**101-1), то время работы 1,56 сек.
Если в цикле одно действие по остатку (2**100-1) % (3**20), то время работы 3,17 сек.

Сообщение было отредактировано: 15 янв 20, 19:21
15 янв 20, 19:12    [22060146]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
mayton
Member

Откуда: loopback
Сообщений: 51166
 		Усов. Бросай свои числа. Go-go решать задачи.

https://www.sql.ru/forum/1321195/zadacha-s-korobkami-iz-vetki-pro-terver
15 янв 20, 19:58    [22060189]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Barlone
Member

Откуда:
Сообщений: 1451
Gennadiy Usov↑
Составил программу факторизации с помощью метода с использованием квадратичных форм.
https://old.kpfu.ru/f9/bibl/Monograph_ishm.pdf

Формулы похожие на формулы непрерывных дробей.
Программа это хорошо. Но еще неплохо бы понимать теорию, почему он вообще работает. Почему в первом цикле должна встретится квадратная форма? Почему во втором цикле должна встретиться неоднозначная форма, и почему из ее коэффициентов можно найти делитель?
16 янв 20, 15:30    [22060725]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
Barlone↑
Gennadiy Usov↑
Составил программу факторизации с помощью метода с использованием квадратичных форм.
https://old.kpfu.ru/f9/bibl/Monograph_ishm.pdf
Формулы похожие на формулы непрерывных дробей.
Программа это хорошо.
Но еще неплохо бы понимать теорию, почему он вообще работает.
Почему в первом цикле должна встретится квадратная форма?
Почему во втором цикле должна встретиться неоднозначная форма, и
почему из ее коэффициентов можно найти делитель?
Каждый из методов кто-то разработал и составил перечень операций.
Методы работают не для всех чисел, но для многих чисел работают, и то хорошо.
Влезать в теорию алгоритма пока нецелесообразно, поскольку не понятно: а зачем?

Осталось понять: а как эти методы применить, если применять.
Если применять, то можно влезать в алгоритмы.

Или это остаётся экзотикой.

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

Откуда:
Сообщений: 2360
 		Решил продолжить исследования 22060146 времени работы операций на ПК (Питон):

Получились коэффициенты:
сложение - 12
умножение - 12
остаток по модулю - 24
корень квадратный - 55
по-битовое определение единичек в числе - 8
7 фев 20, 19:13    [22075768]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		Работаю в Питоне.

Заметил, что программа "ошибается" при делении на 2 для чисел около 10^18.

398222426974351438
199111213487175712

Что посоветуете?
11 фев 20, 20:27    [22077871]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
exp98
Member

Откуда:
Сообщений: 2856
Gennadiy Usov↑
Заметил, что программа "ошибается" при делении на 2 для чисел около 10^18. 398222426974351438 199111213487175712 Что посоветуете?
Это разве не эффект double? 15-16 точных цифр ...
12 фев 20, 00:12    [22077935]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
mayton
Member

Откуда: loopback
Сообщений: 51166
Gennadiy Usov↑
Работаю в Питоне.

Заметил, что программа "ошибается" при делении на 2 для чисел около 10^18.

398222426974351438
199111213487175712

Что посоветуете?

Python пытается вывести тип данных из текста который ты лупишь.
Смотри. Ввожу просто разные числа. Разной длины. И с десятичной точкой и без.

Python 2.7.17 (default, Nov  7 2019, 10:07:09) 
[GCC 7.4.0] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> type(1.1)
<type 'float'>
>>> type(1)
<type 'int'>
>>> type(100000)
<type 'int'>
>>> type(100000000000000000000)
<type 'long'>
>>> type(10000000000000000000000000000000000000000000000000)
<type 'long'>
>>> 
>>> type(long(1))
<type 'long'>


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

Как только ты объявляешь переменную - ты должен знать какие числа в ней будут лежать.
Целые или вещественные. И если целые то какой максимальный диспазон надо обеспечить.

В последней строке я попытался Питону объявить что единичка имеет тип long.
12 фев 20, 00:58    [22077941]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		У меня Python 3.7.4.
И в нём нет "long".

Пробую дальше.

Вместо / поставил // и получилось.
И результат становится int (как положено).

То есть:
не int (a/2),
a a // 2

Хотя // должен отбрасывать дробные части, ещё уменьшая целое число.
В справочниках: "Получение целой части от деления"

Сообщение было отредактировано: 12 фев 20, 06:45
12 фев 20, 06:44    [22077962]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		Изучаю китайскую ттеорему об остатках. Нашел:
http://vuz.exponenta.ru/PDF/book/ChinaT.html
посмотрел на поиск yi...

mayton,

поиск yi ничего не напоминает?
13 мар 20, 11:42    [22098283]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
mayton
Member

Откуда: loopback
Сообщений: 51166
 		Нет ничего не напоминает. Я давно уже не слежу за твоими числовыми исследованиями.
Мне они пока неинтересны. Я целиком в графовых задачах и в изучении ФП.
13 мар 20, 12:04    [22098320]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Имя пользователя1
Member

Откуда:
Сообщений: 727
mayton↑
Я целиком в графовых задачах
если что интересное и небанальное встретится, выкладывай на форум )
13 мар 20, 12:24    [22098357]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
mayton↑
Нет ничего не напоминает. Я давно уже не слежу за твоими числовыми исследованиями.
Мне они пока неинтересны. Я целиком в графовых задачах и в изучении ФП.
А это расстановка ферзей на доске с одинаковым шагом.

Поворачиваем доску на 90 градусов и находим решение с одного шага.
13 мар 20, 12:28    [22098366]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
mayton
Member

Откуда: loopback
Сообщений: 51166
Gennadiy Usov↑
mayton↑
Нет ничего не напоминает. Я давно уже не слежу за твоими числовыми исследованиями.
Мне они пока неинтересны. Я целиком в графовых задачах и в изучении ФП.
А это расстановка ферзей на доске с одинаковым шагом.

Поворачиваем доску на 90 градусов и находим решение с одного шага.

Я-бы был рад в это поверить если не другой факт. Этой задачей занимались много лет
и никто не доказал существование полиномиального решения для остаточной расстановки.

Зачем мы тревожим труп? Пускай себе лежит.
13 мар 20, 13:15    [22098412]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		mayton,

ты столько потревожил ...., этих, на форуме "Программирование", что одним больше, одним меньше...
13 мар 20, 14:57    [22098537]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
mayton
Member

Откуда: loopback
Сообщений: 51166
 		Вот я раскаялся в этих действиях и ушел в Тибет читать молитвы
графы решать графовые задачи на ФП.
13 мар 20, 15:21    [22098568]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Barlone
Member

Откуда:
Сообщений: 1451
Gennadiy Usov↑
Изучаю китайскую ттеорему об остатках. Нашел:
http://vuz.exponenta.ru/PDF/book/ChinaT.html

Найти решение системы сравнений
x=2(mod 5),
x=15(mod 17),
x=5(mod 12).

import math


def invmod(a, b):
  if b == 0:
    return 0
  x2 = 1
  x1 = 0
  y2 = 0
  y1 = 1
  d = b
  while b > 0:
    q = a // b
    r = a - q * b
    x = x2 - q * x1
    y = y2 - q * y1
    a = b
    b = r
    x2 = x1
    x1 = x
    y2 = y1
    y1 = y
  if a == 1:
    if x2 > 0:
      return x2
    else:
      return d + x2
  else:
    return 0

def chinese_rems(mods):
    mod_mults = []
    p_mods = 1
    
    def rem_restore(rems):
        nonlocal mod_mults, p_mods 
        sm = 0
        for i in range(len(rems)):
            sm += rems[i] * mod_mults[i] % p_mods
        return sm % p_mods

    for i in mods:
        p_mods *= i
    for i in mods:
        mod_mults.append(invmod(p_mods//i, i) * (p_mods//i) % p_mods)
    return rem_restore

f = chinese_rems([5,17,12])
print (f([2,15,5]))
14 мар 20, 07:01    [22098965]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		Barlone,

спасибо за программу!

А при прогоне идут ошибки компиляции...

Сообщение было отредактировано: 14 мар 20, 07:26
14 мар 20, 07:23    [22098966]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Barlone
Member

Откуда:
Сообщений: 1451
Gennadiy Usov↑

А при прогоне идут ошибки компиляции...
Старая версия питона?
14 мар 20, 07:38    [22098968]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		Traceback (most recent call last):
File "<string>", line 1, in <module>
File "/usr/lib/python2.7/py_compile.py", line 117, in compile
raise py_exc
py_compile.PyCompileError: File "prog.py", line 36
nonlocal mod_mults, p_mods
^
SyntaxError: invalid syntax


При копировании прошла сдвижка влево на 6 позиций. Стрелка под s.

А в Python 3.7.4 прошло!
797
>>>

Сообщение было отредактировано: 14 мар 20, 07:46
14 мар 20, 07:44    [22098969]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		Получилась интересная ситуация с китайской теоремой.

С первого раза находится число,
если оно меньше произведения всех модулей.

Далее надо прибавлять это произведение модулей до нахождения нужного.

Сообщение было отредактировано: 15 мар 20, 07:39
15 мар 20, 07:30    [22099251]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

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

Гугли "система остаточных классов"
15 мар 20, 21:43    [22099531]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		Кстати, а какое соотношение между площадью и периметром прямоугольника?
8 май 20, 07:58    [22129129]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Dima T
Member

Откуда:
Сообщений: 15596
Gennadiy Usov↑
Кстати, а какое соотношение между площадью и периметром прямоугольника?

Никакого
8 май 20, 08:05    [22129132]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6256
Gennadiy Usov↑
Кстати, а какое соотношение между площадью и периметром прямоугольника?
ab/[2(a + b)]
8 май 20, 09:00    [22129142]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
mayton
Member

Откуда: loopback
Сообщений: 51166
 		Если z = f(x,y) = x * y/[2(x + y)]

то это поверхность близкая к плоскости, и вдоль прямой x = y эта поверхность рвётся
и улетает либо в минус бесконечность либо в плюс.
8 май 20, 10:23    [22129177]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
Gennadiy Usov↑
Кстати, а какое соотношение между площадью и периметром прямоугольника?
Почему я задал этот вопрос?

А потому что это отношение похоже на задачу факторизации.

N = A**2 - B**2, N = x*y, A = (x + y)/2
8 май 20, 10:44    [22129189]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

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

оно даже больше, чем похоже
fi(p1*p2) = (p1 - 1) (p2 - 1) = p1 * p2 + 1 - (p1 + p2)

но я уже где-то показывал, что размеры нашей вселенной ничто в сравнении цифрами, используемыми даже в текущей криптографии
8 май 20, 21:30    [22129679]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
kealon(Ruslan)↑
Gennadiy Usov,
оно даже больше, чем похоже
fi(p1*p2) = (p1 - 1) (p2 - 1) = p1 * p2 + 1 - (p1 + p2)
но я уже где-то показывал, что размеры нашей вселенной ничто в сравнении цифрами,
используемыми даже в текущей криптографии
А далее ещё интереснее:

2^N = 2^(x + y - 1) mod(N),
где N = x * y - только два множителя.
10 май 20, 09:03    [22130061]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

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

я могу ещё более весомое утверждение дать, в силу отсутствия собственного корня при x<>y

2^[(N + 1)/2] mod N = 2^[(x + y)/2] mod N

только толку от этого мало
12 май 20, 13:50    [22131176]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
kealon(Ruslan)↑
Gennadiy Usov,
я могу ещё более весомое утверждение дать, в силу отсутствия собственного корня при x<>y
2^[(N + 1)/2] mod N = 2^[(x + y)/2] mod N
только толку от этого мало
Чем хорошо это уравнение, так это в том, что перебираются не числа от 1 до x + y,
а числа от 1 до (x + y)/2
при переборе 2^.

А если N +1 можно делить ещё раз на 2 (и не один раз), то ещё меньше чисел придётся перебирать.
12 май 20, 14:49    [22131251]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6256
Gennadiy Usov↑
kealon(Ruslan)↑
Gennadiy Usov,
я могу ещё более весомое утверждение дать, в силу отсутствия собственного корня при x<>y
2^[(N + 1)/2] mod N = 2^[(x + y)/2] mod N
только толку от этого мало
Чем хорошо это уравнение, так это в том, что перебираются не числа от 1 до x + y,
а числа от 1 до (x + y)/2
при переборе 2^.

А если N +1 можно делить ещё раз на 2 (и не один раз), то ещё меньше чисел придётся перебирать.
неверно
12 май 20, 17:16    [22131402]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
kealon(Ruslan)↑
Gennadiy Usov↑
А если N +1 можно делить ещё раз на 2 (и не один раз), то ещё меньше чисел придётся перебирать.
неверно
Почему?
12 май 20, 17:58    [22131435]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
kealon(Ruslan)↑
Gennadiy Usov↑
Чем хорошо это уравнение, так это в том, что перебираются не числа от 1 до x + y,
а числа от 1 до (x + y)/2
при переборе 2^.
А если N +1 можно делить ещё раз на 2 (и не один раз), то ещё меньше чисел придётся перебирать.
неверно
Проверил.
Будет верно для (N +1)/4, если (N +1)/8 - чётное.
И так далее.

Сообщение было отредактировано: 12 май 20, 20:28
12 май 20, 20:28    [22131535]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		А что мы знаем о числе N = x * y, которое необходимо факторизировать?

1. Корень из N - для начала поиска чисел А и В.

2. Длина в битах - можно использовать для поиска окрестностей единиц.

3. Последние цифры - для определения последних цифр чисел x и y, и для определения шага (x + y) или А.

А что ещё?

Сообщение было отредактировано: 3 июн 20, 09:05
3 июн 20, 09:05    [22144685]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Barlone
Member

Откуда:
Сообщений: 1451
Gennadiy Usov↑
А что мы знаем о числе N = x * y, которое необходимо факторизировать?

1. Корень из N - для начала поиска чисел А и В.

2. Длина в битах - можно использовать для поиска окрестностей единиц.

3. Последние цифры - для определения последних цифр чисел x и y, и для определения шага (x + y) или А.

А что ещё?
Остатки по любым простым модулям. Каждый остаток по простому модулю сокращает количество возможных значений x+y примерно в два раза: (x+y)2/4 - N mod p должно быть квадратичным вычетом.

Сообщение было отредактировано: 3 июн 20, 09:14
3 июн 20, 09:13    [22144688]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
Barlone↑
Gennadiy Usov↑
А что мы знаем о числе N = x * y, которое необходимо факторизировать?
1. Корень из N - для начала поиска чисел А и В.
2. Длина в битах - можно использовать для поиска окрестностей единиц.
3. Последние цифры - для определения последних цифр чисел x и y, и для определения шага (x + y) или А.
А что ещё?
Остатки по любым простым модулям. Каждый остаток по простому модулю сокращает количество возможных значений x+y примерно в два раза: (x+y)2/4 - N mod p должно быть квадратичным вычетом.
Есть одно но:
мы не можем найти все такие остатки для больших чисел.

А если пользуясь термином "сокращает количество ... примерно в два раза",
то, зная остатки по 140 простым числам, уменьшаем в 2^140 раз?

Сообщение было отредактировано: 3 июн 20, 09:23
3 июн 20, 09:21    [22144690]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Barlone
Member

Откуда:
Сообщений: 1451
Gennadiy Usov↑

А если пользуясь термином "сокращает количество ... примерно в два раза",
то, зная остатки по 140 простым числам, уменьшаем в 2^140 раз?
Ага. Только это сложно использовать. Мы знаем, что остаток по каждому модулю - один из нескольких возможных. Если выбрать по одному произвольному из допустимых остатку, и по китайской теореме собрать остаток по модулю произведения этих 140 простых - получим огромное число, гораздо больше N.
Можно попробовать использовать что-то типа решета: вычеркивать недопустимые остатки. Только нужен кусок памяти размером порядка квадратного корня из N. Если придумаете, как построить число, которое лежит в нужном диапазоне, и одновременно имеет остатки по простым модулям из числа допустимых - сможете сломать RSA :)
3 июн 20, 11:19    [22144750]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
Barlone↑
Gennadiy Usov↑
А если пользуясь термином "сокращает количество ... примерно в два раза",
то, зная остатки по 140 простым числам, уменьшаем в 2^140 раз?
Ага. Только это сложно использовать.
Мы знаем, что остаток по каждому модулю - один из нескольких возможных.
Если выбрать по одному произвольному из допустимых остатку, и по китайской теореме собрать остаток по модулю произведения этих 140 простых -
получим огромное число, гораздо больше N.

Можно попробовать использовать что-то типа решета: вычеркивать недопустимые остатки.
Только нужен кусок памяти размером порядка квадратного корня из N.
Если придумаете, как построить число, которое лежит в нужном диапазоне,
и одновременно имеет остатки по простым модулям из числа допустимых - сможете сломать RSA :)
Я тут попробовал по китайской теореме смотрел остатки степеней 2 по модулю N, чтобы определить единицу.

Где-то после 2^20 идёт серьёзное увеличение по времени расчёта.
3 июн 20, 11:29    [22144761]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
Barlone↑
Остатки по любым простым модулям. Каждый остаток по простому модулю сокращает количество возможных значений x+y примерно в два раза: (x+y)2/4 - N mod p должно быть квадратичным вычетом.
Видел публикации, где говорилось о более удобном модуле - 20.

Меньше выборок по остаткам.

А по разным простым модулям будут сложные построения.

Или все остатки собирать в одном массиве, чтобы число в массиве было равно количеству модулей.

Сообщение было отредактировано: 3 июн 20, 16:43
3 июн 20, 16:42    [22145093]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

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

было бы идеально если бы можно было свести задачу к другому модулю
3 июн 20, 21:01    [22145305]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
Barlone↑
Каждый остаток по простому модулю сокращает количество возможных значений x+y примерно в два раза:
(x+y)2/4 - N mod p должно быть квадратичным вычетом.
То есть, должно выполняться уравнение по квадратичным вычетам:
(x+y)2/4 - N = (x-y)2/4 mod p
7 июн 20, 19:47    [22147145]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		Обычно, в тесте Ферма при определения остатков перебираются показатели степени для определённого основания степени.

А есть ли работы по перебору оснований степени?
13 июн 20, 11:15    [22150080]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

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

А если пользуясь термином "сокращает количество ... примерно в два раза",
то, зная остатки по 140 простым числам, уменьшаем в 2^140 раз?
Ага. Только это сложно использовать. Мы знаем, что остаток по каждому модулю - один из нескольких возможных. Если выбрать по одному произвольному из допустимых остатку, и по китайской теореме собрать остаток по модулю произведения этих 140 простых - получим огромное число, гораздо больше N.
Можно попробовать использовать что-то типа решета: вычеркивать недопустимые остатки. Только нужен кусок памяти размером порядка квадратного корня из N. Если придумаете, как построить число, которое лежит в нужном диапазоне, и одновременно имеет остатки по простым модулям из числа допустимых - сможете сломать RSA :)
не совсем понял
группа остатков по простым модулям это собственно "система остаточных классов", там как бы проблем то нет

если этим можно представить q^2|n=1 и q < n, то остатков то не так много нужно

за счёт чего "(x+y)2/4 - N mod p должно быть квадратичным вычетом" уменьшает количество значений вдвое?
22 июн 20, 09:47    [22154940]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Barlone
Member

Откуда:
Сообщений: 1451
kealon(Ruslan)↑

за счёт чего "(x+y)2/4 - N mod p должно быть квадратичным вычетом" уменьшает количество значений вдвое?

Мы пытаемся представить нечетное составное N в виде N = s² - d² и, рассматривая это равенство по модулям маленьких простых чисел, получаем ограничения на возможные значения s или d. Ну например, допустим N mod 5 == 1. Тогда s mod 5 не может быть 2 или 3, потому что 3 - квадратичный невычет по модулю 5. А если N mod 5 == 3, то s mod 5 не может быть 0, 1 и 4.
22 июн 20, 12:40    [22155081]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
Barlone↑
kealon(Ruslan)↑
за счёт чего "(x+y)2/4 - N mod p должно быть квадратичным вычетом" уменьшает количество значений вдвое?
Мы пытаемся представить нечетное составное N в виде N = s² - d² и, рассматривая это равенство по модулям маленьких простых чисел, получаем ограничения на возможные значения s или d. Ну например, допустим N mod 5 == 1. Тогда s mod 5 не может быть 2 или 3, потому что 3 - квадратичный невычет по модулю 5. А если N mod 5 == 3, то s mod 5 не может быть 0, 1 и 4.
А почему рассматривается только s или d?

Необходимо рассматривать комбинацию разностей остатков для s и d.
22 июн 20, 13:11    [22155104]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

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

но так выходит дофига комбинаций, которые надо проверять
т.е. уменьшения в два раза то и нету

т.е. допустим для представления N нам достаточно СОК из K простых чисел

у нас выходит П(Pi/2, i = 1..k) вариантов для перебора, что приблизительно равно N/ 2^K - и это очень дофига
22 июн 20, 16:31    [22155263]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		В продолжение 22144685:

4. Величину s = (х + y) mod 6
29 июн 20, 15:02    [22159106]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		Решил поработать с р-методом логарифмирования.

Много разных публикаций с разными алгоритмами.
Скачал на Питоне программу, которая не всегда работает
https://ru.wikibooks.org/wiki/Реализации_алгоритмов/P-метод_Полларда_дискретного_логарифмирования

Было бы интересно обсудить данный метод.
6 июл 20, 05:21    [22162503]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

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

А у меня вопрос:
на настоящий момент какое количество простых чисел удалось применить в одной сетке и какой размер ячеи такой сетки?
30 июл 20, 16:58    [22175802]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		Допустим, есть число n = x * y, где x и y – два простых числа.
Над числом n есть кольцо вычетов Zn.

Согласно алгоритму Гельфонда –Шенкса можно построить в кольце вычетов Zn две сетки чисел,
с помощью которых можно найти все вычеты для определённого некоторого числа q,
которых будет несколько в Zn.
Получается сетка чисел размером m = (n^(1/2) x (n^(1/2),
тогда, количество элементов сетки будет m.
И для определения числа q (или нескольких q) будет «шаг» на отрезке (1, n-1),
равный n/m .

Согласно 22097181 ищется число q = 1, и не каждое число, а только определённое число q =1,
на «расстоянии» (x + y) - 1 от последнего элемента кольца вычетов Zn.

Для этого вычета q = 1 достаточно ограничить отрезок (2*(n^(1/2), k*(n^(1/2)),
где k надо посчитать после учёта малых делителей.
Получается новая сетка чисел размером m1 = (((k-2)*(n^(1/2))^(1/2)) x (((k-2)*(n^(1/2))^(1/2)).

И «шаг» для определения числа A = (х + y)/2 будет равен 2*m / m1.

А какой «шаг» даст нам метод Ферма с перебором простых чисел?
2 авг 20, 06:53    [22176636]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		У алгоритма Гельфонда -Шенкса есть одно неудобство:
необходимо сравнивать каждое число второй сетки с каждым числом первой сетки.

А если на первую сетку "наложить" третью сетку?
Некоторая сортировка.

Тогда в несколько раз можно уменьшить количество сравнений между первой и второй сетками.
4 авг 20, 20:38    [22177625]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
mayton
Member

Откуда: loopback
Сообщений: 51166
 		Gennadiy Usov, какую цель ты преследуешь?

Мы, программисты добиваемся того чтобы ответ от программы был получен за разумное время.
4 авг 20, 21:45    [22177647]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		mayton,

почти во всех известных методах факторизации за основу берется уравнение n = A^2 - B^2.
(или во всех ?)

А если за основу методов факторизации взять 2^(x + y) = 2^(n + 1) mod n?

Или за основу взять лучшее от этих двух уравнений.

Второе уравнение применяется только про дискретном логарифмировании.(?)

Сообщение было отредактировано: 5 авг 20, 06:05
5 авг 20, 06:06    [22177715]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Barlone
Member

Откуда:
Сообщений: 1451
Gennadiy Usov↑
mayton,

почти во всех известных методах факторизации за основу берется уравнение n = A^2 - B^2.
(или во всех ?)
Не во всех. Есть же p-1 метод Полларда. Там как раз предполагая, что N=p*q, ищем такое x, что ax=1 mod p и ax≠1 mod q. Тогда gcd(ax%N-1,N)=p
Для поиска x используется то, что если ax=1 mod p то и ax*y=1 mod p при любом y
Метод эллиптических кривых работает так же, только вместо вычетов по модулю N использует точки на эллиптической кривой.
5 авг 20, 06:42    [22177719]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

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

не во всех, есть ещё Метод разложения Эйлера

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

Откуда:
Сообщений: 2360
kealon(Ruslan)↑
Gennadiy Usov,
не во всех, есть ещё Метод разложения Эйлера
Интересный метод, но в нём нет 2^.
Я это имел в виду, а есть там + или - , то это уже вторично.

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

Откуда:
Сообщений: 2360
 		Заинтересовал метод факторизации (p-1) - метод Полларда.

И появилась задачка для выходных:

найти с помощью этого метода делители числа 3277.
То есть, выбрать с помощью этого метода набор простых делителей со степенями
для определения делителей числа 3277
14 авг 20, 09:21    [22182338]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		https://ru.wikipedia.org/wiki/P?1-метод_Полларда

В этой статье спутаны 2 понятия.

Сначала - "сильные простые числа"

А потом - "Пусть N B-гладкостепенное"

Разница есть?
7 сен 20, 18:55    [22193182]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
exp98
Member

Откуда:
Сообщений: 2856
 		И это прекрасно. Очередное доказательство того, "какая гадость - эта ваша"(цэ) смердепедия. Сколько уже можно наталкиваться на некомпетентность? Кто-то продолжает думать, что статьи не заказные, что их пишут не по заданию, не штатные писатели, к-рым одинаково равно что Гегель, что Гоголь, что пишут их компетентные специалисты?
Жду желающих исправить статью))
7 сен 20, 22:31    [22193249]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6256
Gennadiy Usov↑
https://ru.wikipedia.org/wiki/P?1-метод_Полларда

В этой статье спутаны 2 понятия.

Сначала - "сильные простые числа"

А потом - "Пусть N B-гладкостепенное"

Разница есть?
логически там верно, просто велик, могуч и не всегда однозначен русский язык

автор
Именно появление данного алгоритма привело к изменению понятия сильного простого числа, используемого в криптографии, нестрого говоря, простого числа, для которого p-1 имеет достаточно большие делители.

автор
Пусть N B-гладкостепенное
это собственно и является условием применимости данного алгоритма
а так же и появившимся в криптографии, после открытия этого метода критерием НЕ "сильного простого числа"
8 сен 20, 00:13    [22193273]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
mayton
Member

Откуда: loopback
Сообщений: 51166
 		Прочитал - "гладкоствольное". Воистину могуч...
8 сен 20, 12:46    [22193508]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		Тут мы говорим о сильных числах,
о том, что (р – 1) - метод Полларда не способен работать с сильными числами.

А вот и нет.

Пример:
N = 668027303194148809 * 9929

Здесь сомножители делителей числа N
и (р-1), и (р+1)
[2, 2, 2, 17, 73] [2, 2, 2, 2, 2, 2, 2, 2, 5, 47, 373, 2998279]
[2, 3, 5, 331] [2, 3, 3, 109, 18401, 1863581]

Чтобы определить делитель 668027303194148809,
необходимо определить делитель 9929.
Иначе нельзя.

Однако, если задать в (р – 1) - методе Полларда
для произведения М только один сомножитель 2^8,
то (р – 1) - метод Полларда первым определяет делитель:
668027303194148809

Спрашивается:
число 668027303194148809 сильное число относительно числа 9929?
9 сен 20, 13:19    [22194170]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

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

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

вот в замечании более сильное условие есть тынц
автор
С помощью данного метода мы сможем найти только такие простые делители ...
9 сен 20, 20:20    [22194441]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
kealon(Ruslan)↑
что-то мне говорит, что не обязательно число с мелкими делителями для p-1 будет хорошо факторизовываться этим методом

вот в замечании более сильное условие есть тынц
автор
С помощью данного метода мы сможем найти только такие простые делители ...
Пример показал 22194170, что с методом и определением сильных простых чисел не всё ладно.

Самое важное: сомножители "определяют" не делители числа,
а те (2^М - 1), которые в дальнейшем "определят" делителей.

Видите разницу!

Вот что забыли в методе!
9 сен 20, 21:30    [22194461]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		Есть ещё интересный пример:

2^97 – 1 = 11447 * 13842607235828485645766393
11447 – 1 = 2 * 59 * 97
13842607235828485645766393 – 1 = 2^3 * 97 * 1297 *13753593975618284111
11 сен 20, 07:31    [22195171]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2360
 		Пример 22195171, в котором повторяется число 97 в делителях,
может быть только с простыми числами.
Здесь - 97.
11 сен 20, 12:56    [22195340]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

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

р = 12000047, (р - 1) = 2 * 6000023, 6000023 - простое число

или

р = 12000071, (р - 1) = 2 * 5 * 1200007, 1200007 - простое число

Конечно, относительно В1 = 1000000
25 сен 20, 20:24    [22204457]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2 3 4 5 6      [все]
Все форумы / Программирование Ответить