| Добро пожаловать в форум, Guest >> Войти | Регистрация | Поиск | Правила | | В избранное | Подписаться | ||
| Все форумы / Программирование |
  |
||
| Топик располагается на нескольких страницах: [1] 2 3 4 5 6 вперед Ctrl→ все |
 Немного о факторизации
|
|||||
|
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Эпиграф:
Кстати, неплохая книга для изучения факторизации. Очень интересный метод (р – 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: Немного о факторизации
|
|
|
Barlone Member Откуда: Сообщений: 1451 |
Не перемножаем несколько степеней простых чисел по модулю n, а возводим некоторое начальное число в степень, равную этому самому произведению степеней маленьких простых. |
| 20 дек 19, 09:05 [22044925] Ответить | Цитировать Сообщить модератору | |
| Re: Немного о факторизации
|
|
|
Barlone Member Откуда: Сообщений: 1451 |
И метод годится не только для чисел, у которых один из множителей мал, но и для чисел, у которых функция Эйлера для одного из множителей раскладывается на маленькие сомножители. Например, множитель - число Прота с маленьким k (но сам по себе большой) можно найти. |
| 20 дек 19, 09:49 [22044948] Ответить | Цитировать Сообщить модератору | |
| Re: Немного о факторизации
|
|||||
|
Gennadiy Usov Member Откуда: Сообщений: 2360 |
В результате: "перемножаем несколько степеней минимальных простых чисел, возводим некоторое начальное число (например, 2) в степень, равную полученному произведению (по модулю n) и с помощью н.о.д. сразу определяется минимальный множитель." Кстати, ещё можно "поиграть" этими основаниями степеней. (в предыдущий раз это помогло) |
||||
| 20 дек 19, 11:35 [22045055] Ответить | Цитировать Сообщить модератору | |||||
| Re: Немного о факторизации
|
|
|
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: Немного о факторизации
|
|
|
Gennadiy Usov Member Откуда: Сообщений: 2360 |
При этом, если (р-1)-метод определяет число, это не значит, что получен окончательный ответ. Этот метод может "зацепить" сразу несколько малых простых чисел. Причём, некоторые числа могут быть и достаточно большими. Поэтому необходимо ещё одно применение (р-1)-метода к полученному числу (при этом число В будет намного меньше). |
| 21 дек 19, 19:37 [22045985] Ответить | Цитировать Сообщить модератору | |
| Re: Немного о факторизации
|
|
|
Gennadiy Usov Member Откуда: Сообщений: 2360 |
А самый плохой вариант для (р-1)-метода: проверяемое число есть произведение очень большого числа простых небольших чисел. Тогда (р-1)-метод выдаст это самое число (если в проверяемом числе есть степень простого числа, то в "ответе" будет это число, но без степени). ..., начинай с начала. |
| 21 дек 19, 21:12 [22046040] Ответить | Цитировать Сообщить модератору | |
| Re: Немного о факторизации
|
|
|
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Gennadiy Usov, Математики приблизились к решению проблемы простых чисел-близнецов |
| 24 дек 19, 08:38 [22047491] Ответить | Цитировать Сообщить модератору | |
| Re: Немного о факторизации
|
|
|
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Barlone, в задачах факторизации числа n применяется mod(n). А если применять mod (а), где а = целое(n^1/2)? И было ли такое применение? При этом существенно уменьшается база квадратов чисел. |
| 25 дек 19, 11:08 [22048273] Ответить | Цитировать Сообщить модератору | |
| Re: Немного о факторизации
|
|
|
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Gennadiy Usov, если ты найдёшь как, зная факторизацию n+1, найти факторизацию n, то ты решишь эту задачу |
| 25 дек 19, 12:31 [22048365] Ответить | Цитировать Сообщить модератору | |
| Re: Немного о факторизации
|
|||
|
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Gennadiy Usov, вот интересный вопрос, есть такое опредление Первообразные корни
вот интересно, а как пробежаться по этим же числам в модуле n^2 |
||
| 28 дек 19, 23:30 [22050901] Ответить | Цитировать Сообщить модератору | |||
| Re: Немного о факторизации
|
|||||||
|
Gennadiy Usov Member Откуда: Сообщений: 2360 |
"то для любого целого a такого, что ..." Надо добавить: а < n. |
||||||
| 29 дек 19, 07:51 [22050969] Ответить | Цитировать Сообщить модератору | |||||||
| Re: Немного о факторизации
|
|||||
|
Barlone Member Откуда: Сообщений: 1451 |
|
||||
| 29 дек 19, 09:02 [22050973] Ответить | Цитировать Сообщить модератору | |||||
| Re: Немного о факторизации
|
|
|
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Главное - это соотношение чисел n и g. Число а - это "проверочный материал". Проверяется от 0 до n - 1. А далее - просто: (а + v*n) (mod n) = a. Зачем усложнять условие? |
| 29 дек 19, 09:19 [22050975] Ответить | Цитировать Сообщить модератору | |
| Re: Немного о факторизации
|
|
|
Gennadiy Usov Member Откуда: Сообщений: 2360 |
А в вики https://ru.wikipedia.org/wiki/Первообразный_корень_(теория_чисел) по другому определяются эти корни. И без всяких "для всех а". |
| 29 дек 19, 09:37 [22050977] Ответить | Цитировать Сообщить модератору | |
| Re: Немного о факторизации
|
|||||
|
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Gennadiy Usov, пофиг а вот
уже интересный вопрос Сообщение было отредактировано: 29 дек 19, 11:53 |
||||
| 29 дек 19, 11:53 [22051013] Ответить | Цитировать Сообщить модератору | |||||
| Re: Немного о факторизации
|
|||||
|
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Если n = 11, то получаются числа от 1 до 10, причем 1 - два раза. Если n = 11^2, то нет чисел, кратных 11. |
||||
| 29 дек 19, 13:38 [22051040] Ответить | Цитировать Сообщить модератору | |||||
| Re: Немного о факторизации
|
|
|
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Gennadiy Usov, просто хочу записать ((g^k) mod n^2) mod n более простым способом, без mod n причём если порядок будет другой - это некритично |
| 29 дек 19, 16:17 [22051105] Ответить | Цитировать Сообщить модератору | |
| Re: Немного о факторизации
|
|||||
|
Gennadiy Usov Member Откуда: Сообщений: 2360 |
((g^k) mod n^2) mod n "превращается" в уравнение ((g^k) mod n ) |
||||
| 30 дек 19, 09:18 [22051314] Ответить | Цитировать Сообщить модератору | |||||
| Re: Немного о факторизации
|
|
|
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Gennadiy Usov, думаешь я о таком не догадался? а вот вообще без mod n? только через степени g по модулю n^2 |
| 30 дек 19, 23:36 [22052029] Ответить | Цитировать Сообщить модератору | |
| Re: Немного о факторизации
|
|||||
|
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Ранее я говорил, что по модулю n^2 имеем в остатке все числа до n^2, кроме кратных n. |
||||
| 31 дек 19, 07:17 [22052098] Ответить | Цитировать Сообщить модератору | |||||
| Re: Немного о факторизации
|
|
|
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Gennadiy Usov, что непонятного то? нужно получить все числа от 1 до n-1 в кольце n^2 операциями степени |
| 1 янв 20, 15:44 [22052583] Ответить | Цитировать Сообщить модератору | |
| Re: Немного о факторизации
|
|||||
|
Gennadiy Usov Member Откуда: Сообщений: 2360 |
что непонятно в моих ответах? В кольце n^2 (по mod n^2) получаются все числа от 1 до n^2, кроме чисел, кратных n. Если для этого кольца применить (mod n), то данное кольцо "разбивается" на n колец (mod n), в каждом из которых все числа от 1 до n-1. |
||||
| 3 янв 20, 07:54 [22053016] Ответить | Цитировать Сообщить модератору | |||||
| Re: Немного о факторизации
|
|
|
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Gennadiy Usov, а вот теперь без (mod n) - 22052029 |
| 3 янв 20, 09:07 [22053020] Ответить | Цитировать Сообщить модератору | |
| Re: Немного о факторизации
|
|||||
|
Gennadiy Usov Member Откуда: Сообщений: 2360 |
По остальным g (2, 5,7) получается очень много чисел в кольце. Кстати, проверил, другие варианты (небольшие). И везде много чисел. Вариант 3 и 11 - пока единственный, где мало чисел! И что? |
||||
| 3 янв 20, 13:12 [22053067] Ответить | Цитировать Сообщить модератору | |||||
| Топик располагается на нескольких страницах: [1] 2 3 4 5 6 вперед Ctrl→ все |
| Все форумы / Программирование | |
|
x