Добро пожаловать в форум, Guest >> Войти | Регистрация | Поиск | Правила | | В избранное | Подписаться | ||
Все форумы / Программирование |
![]() ![]() |
Топик располагается на нескольких страницах: 1 2 3 4 5 6 [все] |
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] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1451 |
Не перемножаем несколько степеней простых чисел по модулю n, а возводим некоторое начальное число в степень, равную этому самому произведению степеней маленьких простых. |
20 дек 19, 09:05 [22044925] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1451 |
И метод годится не только для чисел, у которых один из множителей мал, но и для чисел, у которых функция Эйлера для одного из множителей раскладывается на маленькие сомножители. Например, множитель - число Прота с маленьким k (но сам по себе большой) можно найти. |
20 дек 19, 09:49 [22044948] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
В результате: "перемножаем несколько степеней минимальных простых чисел, возводим некоторое начальное число (например, 2) в степень, равную полученному произведению (по модулю n) и с помощью н.о.д. сразу определяется минимальный множитель." Кстати, ещё можно "поиграть" этими основаниями степеней. (в предыдущий раз это помогло) |
||||
20 дек 19, 11:35 [22045055] Ответить | Цитировать Сообщить модератору |
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] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
При этом, если (р-1)-метод определяет число, это не значит, что получен окончательный ответ. Этот метод может "зацепить" сразу несколько малых простых чисел. Причём, некоторые числа могут быть и достаточно большими. Поэтому необходимо ещё одно применение (р-1)-метода к полученному числу (при этом число В будет намного меньше). |
21 дек 19, 19:37 [22045985] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
А самый плохой вариант для (р-1)-метода: проверяемое число есть произведение очень большого числа простых небольших чисел. Тогда (р-1)-метод выдаст это самое число (если в проверяемом числе есть степень простого числа, то в "ответе" будет это число, но без степени). ..., начинай с начала. |
21 дек 19, 21:12 [22046040] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Gennadiy Usov, Математики приблизились к решению проблемы простых чисел-близнецов |
24 дек 19, 08:38 [22047491] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Barlone, в задачах факторизации числа n применяется mod(n). А если применять mod (а), где а = целое(n^1/2)? И было ли такое применение? При этом существенно уменьшается база квадратов чисел. |
25 дек 19, 11:08 [22048273] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Gennadiy Usov, если ты найдёшь как, зная факторизацию n+1, найти факторизацию n, то ты решишь эту задачу |
25 дек 19, 12:31 [22048365] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Gennadiy Usov, вот интересный вопрос, есть такое опредление Первообразные корни
вот интересно, а как пробежаться по этим же числам в модуле n^2 |
||
28 дек 19, 23:30 [22050901] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
"то для любого целого a такого, что ..." Надо добавить: а < n. |
||||||
29 дек 19, 07:51 [22050969] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1451 |
|
||||
29 дек 19, 09:02 [22050973] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Главное - это соотношение чисел n и g. Число а - это "проверочный материал". Проверяется от 0 до n - 1. А далее - просто: (а + v*n) (mod n) = a. Зачем усложнять условие? |
29 дек 19, 09:19 [22050975] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
А в вики https://ru.wikipedia.org/wiki/Первообразный_корень_(теория_чисел) по другому определяются эти корни. И без всяких "для всех а". |
29 дек 19, 09:37 [22050977] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Gennadiy Usov, пофиг а вот
уже интересный вопрос Сообщение было отредактировано: 29 дек 19, 11:53 |
||||
29 дек 19, 11:53 [22051013] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Если n = 11, то получаются числа от 1 до 10, причем 1 - два раза. Если n = 11^2, то нет чисел, кратных 11. |
||||
29 дек 19, 13:38 [22051040] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Gennadiy Usov, просто хочу записать ((g^k) mod n^2) mod n более простым способом, без mod n причём если порядок будет другой - это некритично |
29 дек 19, 16:17 [22051105] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
((g^k) mod n^2) mod n "превращается" в уравнение ((g^k) mod n ) |
||||
30 дек 19, 09:18 [22051314] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Gennadiy Usov, думаешь я о таком не догадался? а вот вообще без mod n? только через степени g по модулю n^2 |
30 дек 19, 23:36 [22052029] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Ранее я говорил, что по модулю n^2 имеем в остатке все числа до n^2, кроме кратных n. |
||||
31 дек 19, 07:17 [22052098] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Gennadiy Usov, что непонятного то? нужно получить все числа от 1 до n-1 в кольце n^2 операциями степени |
1 янв 20, 15:44 [22052583] Ответить | Цитировать Сообщить модератору |
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] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Gennadiy Usov, а вот теперь без (mod n) - 22052029 |
3 янв 20, 09:07 [22053020] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
По остальным g (2, 5,7) получается очень много чисел в кольце. Кстати, проверил, другие варианты (небольшие). И везде много чисел. Вариант 3 и 11 - пока единственный, где мало чисел! И что? |
||||
3 янв 20, 13:12 [22053067] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Чтобы такой результат получился (всего 5 или очень немного чисел на большое кольцо), необходимо решить следующее уравнение: найти g, n, b для g^b =1 mod (n^2) |
3 янв 20, 13:31 [22053077] Ответить | Цитировать Сообщить модератору |
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] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Есть n' и n. Или это одно число? И из какого уравнения они (оно) определяются? Ведь известны (?) пока v1, v2, р. |
||||
3 янв 20, 18:20 [22053161] Ответить | Цитировать Сообщить модератору |
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] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Но р - число простое, а n < р. Следовательно, у n и р не может быть общих делителей. Или я что-то не так понял... |
||||
3 янв 20, 20:41 [22053218] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Хотя, есть общий делитель - 1. И поэтому можно найти коэффициенты. Хорошо. А что у нас известно: n и p. А что ещё? Тогда можно получить некоторые числа а и b. Почему эти числа будут v1 и n', которые определены по формулам? |
3 янв 20, 20:50 [22053224] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
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] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Попробую "перевести" на циферки. Так проще. n = 45, p = 61 Тогда n' = 45, v1 = 14. g(1) = 2 и g(-1) = 2197... Пока всё верно? |
4 янв 20, 09:19 [22053320] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
тороплюсь: Тогда n' = 19, v1 = 14. |
4 янв 20, 09:21 [22053321] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
для теста пока пойдёт и он "итератора" то, про который я говорил - 22052583, у нас пока так и нет соответственно x=14 + i*p Сообщение было отредактировано: 4 янв 20, 09:39 |
||||||||
4 янв 20, 09:34 [22053322] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Но если следовать этой логике: для p = 11 быстро найдем (что-то), хотя n должно быть меньше р. а для р = 2^3217-1 будем искать очень долго. |
||||||||
4 янв 20, 16:50 [22053417] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Gennadiy Usov, ну так у нас и итератора аналитического нет. Что проще? умножать постоянно непонятно сколько или вычислить несколько вариантов пусть даже в очень большой степени? |
4 янв 20, 18:37 [22053445] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
т.е. если бы мы, например, знали что все числа <p пробегаются с помощью формулы gk*a|p2 решение системы было бы тривиально |
4 янв 20, 18:51 [22053453] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
У меня получилось, что достаточно проверить i от 1 до 23, далее повтор. Какие числа "выберем" из этих 23-х чисел? Как известно, делители (множители) числа 45 - числа 5 и 9. |
||||
4 янв 20, 20:33 [22053468] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
нет ????, значит наш заход неверен |
||||||||
4 янв 20, 21:50 [22053480] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
А ошибка в главном: в начальной постановке вопроса
Эта формула определяет числа, намного большие р. |
||||||||||||
5 янв 20, 06:40 [22053595] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Кстати, а как можно отредактировать сообщение? Чтобы не делать повторные сообщения. На этом топике было несколько таких редактирований. |
5 янв 20, 07:11 [22053596] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51166 |
У тебя кнопка внизу есть. Но она доступна сразу после публикации. |
5 янв 20, 10:36 [22053637] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Нашел кнопку! Сообщение было отредактировано: 5 янв 20, 11:18 |
||||
5 янв 20, 11:17 [22053649] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
ты спросил "зачем?" я привёл это выражение, которое дополняет систему а по поводу того, что числа > p, так это произведение двух чисел мы же пытаемся получить n'*n через произведение двух чисел - если итератор пробегаетcя по всем числам, то он обязательно одним из чисел зацепит делитель либо n либо n' |
||||||||
5 янв 20, 19:51 [22053824] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
|
||||
5 янв 20, 20:49 [22053836] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Gennadiy Usov, так у тебя есть итератор? так что вполне ожидаемый результат Сообщение было отредактировано: 5 янв 20, 21:02 |
5 янв 20, 21:01 [22053837] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
1. Что он ищет 2. Как он ищет (формула поиска). Так что из этого есть в задаче 22053148? |
||||
6 янв 20, 09:20 [22053942] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Gennadiy Usov, эта формула даёт n'*n, даёт? даёт ... а то что подаёшь на входе фигню, и получаешь фигню - вполне закономерно |
6 янв 20, 11:11 [22053963] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Так ты проверял свои умозаключения или просто выплеснул мысли вслух? На форуме мне всегда говорили: сначала проверь на своём ПК, а потом сообщай остальным. Сообщение было отредактировано: 6 янв 20, 11:28 |
||||
6 янв 20, 11:26 [22053966] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Gennadiy Usov, неправильно понимаешь я то проверил, всё что написал, всё верно. согласен? |
6 янв 20, 13:16 [22053999] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
как завершается наш пример - число 45 и р = 61. Где последние расчёты, где получаемые множители? |
||||
6 янв 20, 13:41 [22054006] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Gennadiy Usov, а я обещал их найти? |
6 янв 20, 20:42 [22054201] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Как известно: мужик сказал, ... Или метод 22053148 никуда не годится? |
||||
6 янв 20, 21:30 [22054215] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Gennadiy Usov, у меня всё сходится 2^14 | p2 = 1500 31^14 | p2 = 3089 [1500 * 3089] | p2 = 855 75 1109 1514 855.... насчёт слева: "дай итератор степенной, гуляющий по числам < p" ..., есть ???? |
6 янв 20, 22:32 [22054255] Ответить | Цитировать Сообщить модератору |
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] Ответить | Цитировать Сообщить модератору |
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] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Продолжаю исследования метода с использованием непрерывных дробей. Взял за основу перебор нечётных числ от 3 до 255 (первое число) и число 257 (второе число). Наблюдаю за количеством прогонов для каждой пары чисел при определении множителей произведения этих чисел. Если количество прогонов ограничить числом 100000 (!), то получается, что невозможно найти множителей (кроме 1 и произведения двух чисел) для произведения двух чисел, когда первое число: 89, 139, 151, 181, 197, 211, 229, 239, 251 |
8 янв 20, 09:45 [22054746] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Немного подумал и "проскочил" 89. Например, для числа 167 необходимо 36 прогонов и здесь "фигурируют" числа в районе Е+200. |
8 янв 20, 19:19 [22055111] Ответить | Цитировать Сообщить модератору |
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] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
|
||||
9 янв 20, 09:42 [22055333] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Эти два перечня имеют некоторое пересечение. Поэтому объединение этих методов позволит несколько уменьшить количество чисел, для которых нельзя найти множителей при использовании одного из методов. |
||||||||
9 янв 20, 11:41 [22055439] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Если взять число 113 х 271 = 30623, то имеем бесконечный цикл из только 5-6 чисел. |
11 янв 20, 07:39 [22057027] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1451 |
Сообщение было отредактировано: 11 янв 20, 10:50 |
||||
11 янв 20, 10:49 [22057052] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Помогло 2 и 23, дальше из простых не смотрел. |
||||||||
11 янв 20, 11:26 [22057064] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Проверка показала, что для каждого простого числа, на которое умножается искомое число, существует свой перечень не определяемых чисел. Эти перечни могут пересекаться, а могут и не пересекаться. |
11 янв 20, 12:35 [22057089] Ответить | Цитировать Сообщить модератору |
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] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51166 |
Усов. Бросай свои числа. Go-go решать задачи. https://www.sql.ru/forum/1321195/zadacha-s-korobkami-iz-vetki-pro-terver |
15 янв 20, 19:58 [22060189] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1451 |
|
||||
16 янв 20, 15:30 [22060725] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Методы работают не для всех чисел, но для многих чисел работают, и то хорошо. Влезать в теорию алгоритма пока нецелесообразно, поскольку не понятно: а зачем? Осталось понять: а как эти методы применить, если применять. Если применять, то можно влезать в алгоритмы. Или это остаётся экзотикой. Сообщение было отредактировано: 16 янв 20, 16:04 |
||||||||
16 янв 20, 16:02 [22060778] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Решил продолжить исследования 22060146 времени работы операций на ПК (Питон): Получились коэффициенты: сложение - 12 умножение - 12 остаток по модулю - 24 корень квадратный - 55 по-битовое определение единичек в числе - 8 |
7 фев 20, 19:13 [22075768] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Работаю в Питоне. Заметил, что программа "ошибается" при делении на 2 для чисел около 10^18. 398222426974351438 199111213487175712 Что посоветуете? |
11 фев 20, 20:27 [22077871] Ответить | Цитировать Сообщить модератору |
exp98 Member Откуда: Сообщений: 2856 |
|
||||
12 фев 20, 00:12 [22077935] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51166 |
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] Ответить | Цитировать Сообщить модератору |
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] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Изучаю китайскую ттеорему об остатках. Нашел: http://vuz.exponenta.ru/PDF/book/ChinaT.html посмотрел на поиск yi... mayton, поиск yi ничего не напоминает? |
13 мар 20, 11:42 [22098283] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51166 |
Нет ничего не напоминает. Я давно уже не слежу за твоими числовыми исследованиями. Мне они пока неинтересны. Я целиком в графовых задачах и в изучении ФП. |
13 мар 20, 12:04 [22098320] Ответить | Цитировать Сообщить модератору |
Имя пользователя1 Member Откуда: Сообщений: 727 |
|
||||
13 мар 20, 12:24 [22098357] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Поворачиваем доску на 90 градусов и находим решение с одного шага. |
||||
13 мар 20, 12:28 [22098366] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51166 |
Я-бы был рад в это поверить если не другой факт. Этой задачей занимались много лет и никто не доказал существование полиномиального решения для остаточной расстановки. Зачем мы тревожим труп? Пускай себе лежит. |
||||||||
13 мар 20, 13:15 [22098412] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
mayton, ты столько потревожил ...., этих, на форуме "Программирование", что одним больше, одним меньше... |
13 мар 20, 14:57 [22098537] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51166 |
Вот я раскаялся в этих действиях и ушел в графы решать графовые задачи на ФП. |
13 мар 20, 15:21 [22098568] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1451 |
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] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Barlone, спасибо за программу! А при прогоне идут ошибки компиляции... Сообщение было отредактировано: 14 мар 20, 07:26 |
14 мар 20, 07:23 [22098966] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1451 |
|
||||
14 мар 20, 07:38 [22098968] Ответить | Цитировать Сообщить модератору |
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] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Получилась интересная ситуация с китайской теоремой. С первого раза находится число, если оно меньше произведения всех модулей. Далее надо прибавлять это произведение модулей до нахождения нужного. Сообщение было отредактировано: 15 мар 20, 07:39 |
15 мар 20, 07:30 [22099251] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Gennadiy Usov, Гугли "система остаточных классов" |
15 мар 20, 21:43 [22099531] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Кстати, а какое соотношение между площадью и периметром прямоугольника? |
8 май 20, 07:58 [22129129] Ответить | Цитировать Сообщить модератору |
Dima T Member Откуда: Сообщений: 15596 |
Никакого |
||||
8 май 20, 08:05 [22129132] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
|
||||
8 май 20, 09:00 [22129142] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51166 |
Если z = f(x,y) = x * y/[2(x + y)] то это поверхность близкая к плоскости, и вдоль прямой x = y эта поверхность рвётся и улетает либо в минус бесконечность либо в плюс. |
8 май 20, 10:23 [22129177] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
А потому что это отношение похоже на задачу факторизации. N = A**2 - B**2, N = x*y, A = (x + y)/2 |
||||
8 май 20, 10:44 [22129189] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Gennadiy Usov, оно даже больше, чем похоже fi(p1*p2) = (p1 - 1) (p2 - 1) = p1 * p2 + 1 - (p1 + p2) но я уже где-то показывал, что размеры нашей вселенной ничто в сравнении цифрами, используемыми даже в текущей криптографии |
8 май 20, 21:30 [22129679] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
2^N = 2^(x + y - 1) mod(N), где N = x * y - только два множителя. |
||||
10 май 20, 09:03 [22130061] Ответить | Цитировать Сообщить модератору |
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] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
а числа от 1 до (x + y)/2 при переборе 2^. А если N +1 можно делить ещё раз на 2 (и не один раз), то ещё меньше чисел придётся перебирать. |
||||
12 май 20, 14:49 [22131251] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
|
||||||||
12 май 20, 17:16 [22131402] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
|
||||||||
12 май 20, 17:58 [22131435] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Будет верно для (N +1)/4, если (N +1)/8 - чётное. И так далее. Сообщение было отредактировано: 12 май 20, 20:28 |
||||||||
12 май 20, 20:28 [22131535] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
А что мы знаем о числе N = x * y, которое необходимо факторизировать? 1. Корень из N - для начала поиска чисел А и В. 2. Длина в битах - можно использовать для поиска окрестностей единиц. 3. Последние цифры - для определения последних цифр чисел x и y, и для определения шага (x + y) или А. А что ещё? Сообщение было отредактировано: 3 июн 20, 09:05 |
3 июн 20, 09:05 [22144685] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1451 |
Сообщение было отредактировано: 3 июн 20, 09:14 |
||||
3 июн 20, 09:13 [22144688] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
мы не можем найти все такие остатки для больших чисел. А если пользуясь термином "сокращает количество ... примерно в два раза", то, зная остатки по 140 простым числам, уменьшаем в 2^140 раз? Сообщение было отредактировано: 3 июн 20, 09:23 |
||||||||
3 июн 20, 09:21 [22144690] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1451 |
Можно попробовать использовать что-то типа решета: вычеркивать недопустимые остатки. Только нужен кусок памяти размером порядка квадратного корня из N. Если придумаете, как построить число, которое лежит в нужном диапазоне, и одновременно имеет остатки по простым модулям из числа допустимых - сможете сломать RSA :) |
||||
3 июн 20, 11:19 [22144750] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Где-то после 2^20 идёт серьёзное увеличение по времени расчёта. |
||||||||
3 июн 20, 11:29 [22144761] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Меньше выборок по остаткам. А по разным простым модулям будут сложные построения. Или все остатки собирать в одном массиве, чтобы число в массиве было равно количеству модулей. Сообщение было отредактировано: 3 июн 20, 16:43 |
||||
3 июн 20, 16:42 [22145093] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Barlone, было бы идеально если бы можно было свести задачу к другому модулю |
3 июн 20, 21:01 [22145305] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
(x+y)2/4 - N = (x-y)2/4 mod p |
||||
7 июн 20, 19:47 [22147145] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Обычно, в тесте Ферма при определения остатков перебираются показатели степени для определённого основания степени. А есть ли работы по перебору оснований степени? |
13 июн 20, 11:15 [22150080] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
группа остатков по простым модулям это собственно "система остаточных классов", там как бы проблем то нет если этим можно представить q^2|n=1 и q < n, то остатков то не так много нужно за счёт чего "(x+y)2/4 - N mod p должно быть квадратичным вычетом" уменьшает количество значений вдвое? |
||||||||
22 июн 20, 09:47 [22154940] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1451 |
Мы пытаемся представить нечетное составное 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] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Необходимо рассматривать комбинацию разностей остатков для s и d. |
||||||||
22 июн 20, 13:11 [22155104] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Barlone, но так выходит дофига комбинаций, которые надо проверять т.е. уменьшения в два раза то и нету т.е. допустим для представления N нам достаточно СОК из K простых чисел у нас выходит П(Pi/2, i = 1..k) вариантов для перебора, что приблизительно равно N/ 2^K - и это очень дофига |
22 июн 20, 16:31 [22155263] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
В продолжение 22144685: 4. Величину s = (х + y) mod 6 |
29 июн 20, 15:02 [22159106] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Решил поработать с р-методом логарифмирования. Много разных публикаций с разными алгоритмами. Скачал на Питоне программу, которая не всегда работает https://ru.wikibooks.org/wiki/Реализации_алгоритмов/P-метод_Полларда_дискретного_логарифмирования Было бы интересно обсудить данный метод. |
6 июл 20, 05:21 [22162503] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Потерял сообщение (не помню топик), в котором говорилось о максимальном количестве простых чисел, чтобы была реше сетка для факторизации. А у меня вопрос: на настоящий момент какое количество простых чисел удалось применить в одной сетке и какой размер ячеи такой сетки? |
30 июл 20, 16:58 [22175802] Ответить | Цитировать Сообщить модератору |
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] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
У алгоритма Гельфонда -Шенкса есть одно неудобство: необходимо сравнивать каждое число второй сетки с каждым числом первой сетки. А если на первую сетку "наложить" третью сетку? Некоторая сортировка. Тогда в несколько раз можно уменьшить количество сравнений между первой и второй сетками. |
4 авг 20, 20:38 [22177625] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51166 |
Gennadiy Usov, какую цель ты преследуешь? Мы, программисты добиваемся того чтобы ответ от программы был получен за разумное время. |
4 авг 20, 21:45 [22177647] Ответить | Цитировать Сообщить модератору |
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] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1451 |
Для поиска x используется то, что если ax=1 mod p то и ax*y=1 mod p при любом y Метод эллиптических кривых работает так же, только вместо вычетов по модулю N использует точки на эллиптической кривой. |
||||
5 авг 20, 06:42 [22177719] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Gennadiy Usov, не во всех, есть ещё Метод разложения Эйлера Сообщение было отредактировано: 5 авг 20, 09:12 |
5 авг 20, 09:11 [22177751] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Я это имел в виду, а есть там + или - , то это уже вторично. Сообщение было отредактировано: 5 авг 20, 11:41 |
||||
5 авг 20, 11:34 [22177839] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Заинтересовал метод факторизации (p-1) - метод Полларда. И появилась задачка для выходных: найти с помощью этого метода делители числа 3277. То есть, выбрать с помощью этого метода набор простых делителей со степенями для определения делителей числа 3277 |
14 авг 20, 09:21 [22182338] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
https://ru.wikipedia.org/wiki/P?1-метод_Полларда В этой статье спутаны 2 понятия. Сначала - "сильные простые числа" А потом - "Пусть N B-гладкостепенное" Разница есть? |
7 сен 20, 18:55 [22193182] Ответить | Цитировать Сообщить модератору |
exp98 Member Откуда: Сообщений: 2856 |
И это прекрасно. Очередное доказательство того, "какая гадость - эта ваша"(цэ) смердепедия. Сколько уже можно наталкиваться на некомпетентность? Кто-то продолжает думать, что статьи не заказные, что их пишут не по заданию, не штатные писатели, к-рым одинаково равно что Гегель, что Гоголь, что пишут их компетентные специалисты? Жду желающих исправить статью)) |
7 сен 20, 22:31 [22193249] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
а так же и появившимся в криптографии, после открытия этого метода критерием НЕ "сильного простого числа" |
||||||||
8 сен 20, 00:13 [22193273] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51166 |
Прочитал - "гладкоствольное". Воистину могуч... |
8 сен 20, 12:46 [22193508] Ответить | Цитировать Сообщить модератору |
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] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6256 |
Gennadiy Usov,
что-то мне говорит, что не обязательно число с мелкими делителями для p-1 будет хорошо факторизовываться этим методом вот в замечании более сильное условие есть тынц
|
||||
9 сен 20, 20:20 [22194441] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Самое важное: сомножители "определяют" не делители числа, а те (2^М - 1), которые в дальнейшем "определят" делителей. Видите разницу! Вот что забыли в методе! |
||||||
9 сен 20, 21:30 [22194461] Ответить | Цитировать Сообщить модератору |
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] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2360 |
Пример 22195171, в котором повторяется число 97 в делителях, может быть только с простыми числами. Здесь - 97. |
11 сен 20, 12:56 [22195340] Ответить | Цитировать Сообщить модератору |
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 [все] |
Все форумы / Программирование | ![]() |