powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Немного о факторизации
25 сообщений из 163, страница 6 из 7
Немного о факторизации
    #39996356
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
И это прекрасно. Очередное доказательство того, "какая гадость - эта ваша"(цэ) смердепедия. Сколько уже можно наталкиваться на некомпетентность? Кто-то продолжает думать, что статьи не заказные, что их пишут не по заданию, не штатные писатели, к-рым одинаково равно что Гегель, что Гоголь, что пишут их компетентные специалисты?
Жду желающих исправить статью))
...
Рейтинг: 0 / 0
Немного о факторизации
    #39996371
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usov
https://ru.wikipedia.org/wiki/P?1-метод_Полларда

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

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

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

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

авторИменно появление данного алгоритма привело к изменению понятия сильного простого числа, используемого в криптографии, нестрого говоря, простого числа, для которого p-1 имеет достаточно большие делители.
авторПусть N B-гладкостепенное это собственно и является условием применимости данного алгоритма
а так же и появившимся в криптографии, после открытия этого метода критерием НЕ "сильного простого числа"
...
Рейтинг: 0 / 0
Немного о факторизации
    #39996508
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Прочитал - "гладкоствольное". Воистину могуч...
...
Рейтинг: 0 / 0
Немного о факторизации
    #39996901
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Тут мы говорим о сильных числах,
о том, что (р – 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?
...
Рейтинг: 0 / 0
Немного о факторизации
    #39997069
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usov,

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

вот в замечании более сильное условие есть тынц
авторС помощью данного метода мы сможем найти только такие простые делители ...
...
Рейтинг: 0 / 0
Немного о факторизации
    #39997085
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
kealon(Ruslan)
что-то мне говорит, что не обязательно число с мелкими делителями для p-1 будет хорошо факторизовываться этим методом

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

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

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

Вот что забыли в методе!
...
Рейтинг: 0 / 0
Немного о факторизации
    #39997519
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Есть ещё интересный пример:

2^ 97 – 1 = 11447 * 13842607235828485645766393
11447 – 1 = 2 * 59 * 97
13842607235828485645766393 – 1 = 2^3 * 97 * 1297 *13753593975618284111
...
Рейтинг: 0 / 0
Немного о факторизации
    #39997612
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Пример 22195171 , в котором повторяется число 97 в делителях,
может быть только с простыми числами.
Здесь - 97.
...
Рейтинг: 0 / 0
Немного о факторизации
    #40002674
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Какое простое число более сильное:

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

или

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

Конечно, относительно В1 = 1000000
...
Рейтинг: 0 / 0
Период между сообщениями больше года.
Немного о факторизации
    #40100524
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Докину сюда. Проба пера еще в одном языке.

Код: python
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
-- mayton : 28-Sep. Yet another tiny factorization

primes :: [Int]
primes = filterPrime [2..]
  where filterPrime (p:xs) =
          p : filterPrime [x | x <- xs, (mod x p) /= 0]

factorize' :: Int -> [Int] -> [Int] -> [Int]
factorize' x divisors primesVals 
  |x == 1 = reverse divisors 
  |otherwise = let d = head primesVals 
               in if (mod x d) == 0 then factorize' (div x d) (d:divisors) primesVals
               else factorize' x divisors $ tail primesVals

factorize :: Int -> [Int]
factorize x = factorize' x [] primes
...
Рейтинг: 0 / 0
Немного о факторизации
    #40100559
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

тоже докину сюда свою мысль, не могу найти

как определить есть ли ненулевые целые решения у Диафантово уравнение второй степени с двумя неизвестными, вида
(x r+ a) (y r + b) = c
...
Рейтинг: 0 / 0
Немного о факторизации
    #40100613
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я помню что для диофанта 1-й степени подходят генетические алгоритмы как наиболее быстрый способ
поиска возможного решения. Это просто ... в голове отложилось от чтения статей по ГА.
...
Рейтинг: 0 / 0
Немного о факторизации
    #40100632
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan)
mayton,

тоже докину сюда свою мысль, не могу найти

как определить есть ли ненулевые целые решения у Диафантово уравнение второй степени с двумя неизвестными, вида
(x r+ a) (y r + b) = c
Начать с факторизации c?
...
Рейтинг: 0 / 0
Немного о факторизации
    #40100660
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Barlone
Начать с факторизации c?
вот меня и интересует, есть ли метод без факторизации "c"
...
Рейтинг: 0 / 0
Немного о факторизации
    #40100759
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan)
вида
(x r+ a) (y r + b) = c
Сдвинутая равнобочная гипербола. Перебором, сэр?
...
Рейтинг: 0 / 0
Немного о факторизации
    #40100764
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98
kealon(Ruslan)
вида
(x r+ a) (y r + b) = c
Сдвинутая равнобочная гипербола. Перебором, сэр?

Напоминает криптографию.
...
Рейтинг: 0 / 0
Немного о факторизации
    #40100777
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98
kealon(Ruslan)
вида
(x r+ a) (y r + b) = c
Сдвинутая равнобочная гипербола. Перебором, сэр?
тогда уж проще разложить
да мне как бы и не решение нужно, а проверка есть ли оно
...
Рейтинг: 0 / 0
Немного о факторизации
    #40100799
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если сделать такое преобразование.

Код: sql
1.
(x r+ a) (y r + b) - с = 0



И искать минимум этой функции через симуляцио отжига.
...
Рейтинг: 0 / 0
Немного о факторизации
    #40100824
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

не-не, цифры очень большие, симуляции или разложение на множители явно не подойдут

простым проверкам типа
(a*b) mod r = c mod r
уравнение удовлетворяет

в p-адических числах решение тоже имеет, так как c - составное (состоит из произведения 3-х простых чисел)

найти нужно: существует или не существует решение
...
Рейтинг: 0 / 0
Немного о факторизации
    #40100902
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan), а что такое "очень большие"? Известно примерное соотношение количества бит в r, a, b, c?
...
Рейтинг: 0 / 0
Немного о факторизации
    #40100905
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если сделать факторизируемое число - это упростит подобный класс задач?

Код: sql
1.
2.
3.
4.
5.
6.
7.
class Number[T] with Factorizable[T] {

   def lazyFactorize() : Map[T,T] // если надо то любое число будет иметь вторую форму представления в виде 240 = 2^2 * 3 * 4 * 5

   .....

}
...
Рейтинг: 0 / 0
Немного о факторизации
    #40100930
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan)

простым проверкам типа
(a*b) mod r = c mod r
уравнение удовлетворяет
Вариант ответа "решение уравнения существует, когда существует разложение на множители c=c1*c2, такое что c1 = a mod r и c2 = b mod r" не устраивает?
...
Рейтинг: 0 / 0
Немного о факторизации
    #40101021
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Barlone,

нет конечно, если бы было легко разложить вопрос бы не возник
...
Рейтинг: 0 / 0
Немного о факторизации
    #40101022
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А про размер чисел?
Хотя, есть большое подозрение, что даже умение отвечать на вопрос, существует ли решение, не давая этого решения, может сильно помочь факторизации...
...
Рейтинг: 0 / 0
Немного о факторизации
    #40101026
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Barlone,

ну нормальные такие, бит на тысячу-две
...
Рейтинг: 0 / 0
25 сообщений из 163, страница 6 из 7
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Немного о факторизации
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]