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

Откуда:
Сообщений: 2204
Эпиграф:
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

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

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

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

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

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

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

Откуда:
Сообщений: 2204
В продолжение рассмотрения темы (р – 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

пофиг

а вот

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Откуда:
Сообщений: 2204
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]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3 4 5   вперед  Ctrl      все
Все форумы / Программирование Ответить