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

Откуда:
Сообщений: 2204
Решил анализировать формулу Ферма 2^(n – 1) (mod n) на все значения показателя степени от 0 до (n – 1).
Оказалось, что из этой информации можно получить сомножители числа n.

Результаты предварительного анализа представлены в статье
http://sci-article.ru/stat.php?i=1582386219
Пока упор в статье делается на произведение двух простых сомножителей.

Всё дело в порядковом номере единиц, которые получаются при вычислении по формуле Ферма .
Дальнейшая задача – определение порядкового номера этих единиц для конкретного числа n.
Однако, пока определение порядкового номера единиц – трудоёмкая задача.

mayton
Усов. Бросай свои числа. Go-go решать задачи.
А что, mayton, будем Go-go искать единицы?
24 фев 20, 14:08    [22085829]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Нет. Я пока не go-go. Тема - весьма специфичная.
24 фев 20, 18:20    [22085963]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
Barlone
Member

Откуда:
Сообщений: 1402
Gennadiy Usov, совсем неинтересно. Очевидно, что если число - псевдопростое по Ферма по некоторому основанию, а Миллер-Рабин по этому же основанию говорит, что число составное - то это автоматически дает нам факторизацию. Только трудоемкость подбора какого такого основания превышает перебор делителей.

Сообщение было отредактировано: 25 фев 20, 07:45
25 фев 20, 07:46    [22086117]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
Barlone
Member

Откуда:
Сообщений: 1402
Или тут имелся ввиду p-1 - метод Полларда?
25 фев 20, 07:59    [22086119]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
Barlone
Member

Откуда:
Сообщений: 1402
Разных алгоритмов напридумывать можно. Будут ли они эффективными - вот вопрос.
Например, такой вариант: допустим, мы предполагаем что известное нам составное N - произведение ровно двух простых неизвестных сомножителей p и q (пытаемся факторизовать rsa-модуль).
Тогда pq = N = ((p+q)/2)2 - ((p-q)/2)2 и это дает нам ограничения на возможные остатки (p+q)/2 по простым модулям: ((p+q)/2)2 - N должно быть квадратичным вычетом.

С другой стороны, для произвольного a должно выполняться a(p-1)(q-1)/2 ≡ 1 mod N
Преобразуем это равенство: a(pq+1)/2 ≡ a(p+q)/2 mod N
Левую часть мы знаем. И нам нужно найти дискретный логарифм в правой части.
Тут можно использовать вариацию на тему метода больших и малых шагов. Большой шаг будет произведением некоторого набора маленьких простых чисел, а на возможные значения малых шагов у нас уже есть ограничение: ((p+q)/2)2 - N должно быть квадратичным вычетом по модулю каждого из этих маленьких простых.

Такой алгоритм должен неплохо работать до значений N порядка 2128.

Сообщение было отредактировано: 25 фев 20, 09:02
25 фев 20, 08:58    [22086142]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Barlone
Или тут имелся ввиду p-1 - метод Полларда?
p-1 - метод Полларда хорошо "отсекает" малые делители.

Метод определения единиц хорошо "отсекает" большие делители, близкие к "корню".
25 фев 20, 09:14    [22086147]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
Barlone
Member

Откуда:
Сообщений: 1402
Или вариация на тему квадратичных форм Шенкса - цепочка редукций фактически дает нам набор равенств:
b12 - a0a1 = N
b22 - a1a2 = N
b32 - a2a3 = N
.....
bn2 - an-1an = N
При этом a0 = 1, а из первого цикла мы выходим, когда an оказывается квадратом.
И зачем нам нужен второй цикл, если в этот момент (b1*b2*...*bn)2 ≡ a0*(a1*a2*...*an-1)2*an mod N
Если a0 и an квадраты, имеем классическое равенство для факторизации x2 ≡ y2 mod N
Ну и соответственно начинать можно не только с a0 = 1, но и например с любого квадрата простого числа, найдя b1 как квадратный корень из N по модулю квадрата этого простого (тут есть алгоритм Тонелли — Шенкса).

Сообщение было отредактировано: 25 фев 20, 09:34
25 фев 20, 09:27    [22086152]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Barlone
Разных алгоритмов напридумывать можно. Будут ли они эффективными - вот вопрос.
Например, такой вариант: допустим, мы предполагаем что известное нам составное N - произведение ровно двух простых неизвестных сомножителей p и q (пытаемся факторизовать rsa-модуль).
Тогда pq = N = ((p+q)/2)2 - ((p-q)/2)2 и это дает нам ограничения на возможные остатки (p+q)/2 по простым модулям: ((p+q)/2)2 - N должно быть квадратичным вычетом.

С другой стороны, для произвольного a должно выполняться a(p-1)(q-1)/2 = 1 mod N
Преобразуем это равенство: a(pq+1)/2 ≡ a(p+q)/2 mod N
Левую часть мы знаем. И нам нужно найти дискретный логарифм в правой части.
Тут можно использовать вариацию на тему метода больших и малых шагов. Большой шаг будет произведением некоторого набора маленьких простых чисел, а на возможные значения малых шагов у нас уже есть ограничение: ((p+q)/2)2 - N должно быть квадратичным вычетом по модулю каждого из этих маленьких простых.

Такой алгоритм должен неплохо работать до значений N порядка 2128.
Спасибо за формулу для "= 1 mod N"!

Да, у меня получается дискретное логарифмирование для h=1.
Только имеются не одна, а несколько групп (параметр n).

Сообщение было отредактировано: 25 фев 20, 13:15
25 фев 20, 13:08    [22086454]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Barlone
для произвольного a должно выполняться a(p-1)(q-1)/2 = 1 mod N
Преобразуем это равенство: a(pq+1)/2 = a(p+q)/2 mod N
Левую часть мы знаем. И нам нужно найти дискретный логарифм в правой части.
Здесь определяется некоторое число из группы значений. А нужно искать единицу.

Есть одна тонкость: допустим найдено решение по единице, однако таких решений несколько (несколько единиц).
Нужно - ближайшее к "корню".

Если решение не подходит, так как число В = p-q не целое число (а именно так проверяется единица),
то надо искать следующее решение.
25 фев 20, 19:44    [22086789]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
Barlone
Member

Откуда:
Сообщений: 1402
Gennadiy Usov
Barlone
для произвольного a должно выполняться a(p-1)(q-1)/2 = 1 mod N
Преобразуем это равенство: a(pq+1)/2 = a(p+q)/2 mod N
Левую часть мы знаем. И нам нужно найти дискретный логарифм в правой части.
Здесь определяется некоторое число из группы значений. А нужно искать единицу.
Так тут две эквивалентные формулы
a(pq+1)/2 - (p+q)/2 ≡ 1 mod N
вот тут ваша единица

теория

Сообщение было отредактировано: 26 фев 20, 06:13
26 фев 20, 06:11    [22086968]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Barlone
вот тут ваша единица
теория
Странно, в статье по таблице наименьший показатель для 7 есть 6 ,
а в реальности 3:
2^3 = 1 (mod 7)
26 фев 20, 07:45    [22086984]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
Barlone
Member

Откуда:
Сообщений: 1402
Gennadiy Usov
Barlone
вот тут ваша единица
теория
Странно, в статье по таблице наименьший показатель для 7 есть 6 ,
а в реальности 3:
2^3 = 1 (mod 7)

Ну а 3^3 = 6 (mod 7)
Надо "для всех целых, взаимно простых с модулем".
26 фев 20, 09:32    [22087022]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
Gennadiy Usov
Member

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

Например, число 625 (5*127)...
28 фев 20, 16:25    [22089301]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
exp98
Member

Откуда:
Сообщений: 2446
Gennadiy Usov, 127 вольт остались в далёком прошлом, сейчас всюду 220 вольт.
28 фев 20, 17:11    [22089366]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Barlone
Тут можно использовать вариацию на тему метода больших и малых шагов. Большой шаг будет произведением некоторого набора маленьких простых чисел, а на возможные значения малых шагов у нас уже есть ограничение: ((p+q)/2)2 - N должно быть квадратичным вычетом по модулю каждого из этих маленьких простых.
Такой алгоритм должен неплохо работать до значений N порядка 2128.
Спасибо за подсказку!

Немного поправил статью:
http://sci-article.ru/stat.php?i=1583822766
Добавил средний шаг
11 мар 20, 20:33    [22097181]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Согласно МТФ: если число p - простое, то 2^(p-1) = 1 (mod p).

Если рассматривать для показателя степени 2 все k (1< k< p),
то получается некоторая повторяющаяся последовательность чисел.
Например, для р = 35 таких чисел будет только 12.

Спрашивается:
а какая «судьба» остальных чисел в количестве (34-12) между 1 и 34?
27 июн 20, 16:14    [22158263]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
Barlone
Member

Откуда:
Сообщений: 1402
https://ru.wikipedia.org/wiki/Квадратичный_вычет
27 июн 20, 17:14    [22158278]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Barlone
https://ru.wikipedia.org/wiki/Квадратичный_вычет
Есть некоторое отличие квадратичных вычетов от остатков по модулю для 2^.

Например. для 35
если 2^, то есть 22, 23, которых нет в х**2
если х**2, то есть 15, 14, 21, 25, 30, которых нет в 2^
27 июн 20, 19:12    [22158315]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Решил сравнить операции
c = c *2
и
c = c << 1

Оказалось, что 2-я операция работает на 10 % дольше.
13 июл 20, 06:42    [22166197]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
А если сравнивать операции
c = c /2
и
c = c >> 1

то казалось, что и здесь 2-я операция работает на 10 % дольше.

Однако, 1-я операция будет не int,
и чтобы перевести число в int необходимо потратить ещё в 3 раза больше времени, чем было потрачено на c = c /2
13 июл 20, 07:06    [22166201]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1982
Gennadiy Usov
Решил сравнить операции
c = c *2
и
c = c << 1

Оказалось, что 2-я операция работает на 10 % дольше.


c = c + c
13 июл 20, 09:40    [22166248]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
Dima T
Member

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

Почему сдвиг медленнее в конкретном ЯП - скорее всего связано с внутренним устройством это ЯП, т.е. с тем какие еще инструкции выполняет процессор кроме самого сдвига.
13 июл 20, 09:55    [22166262]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Aleksandr Sharahov
Gennadiy Usov
Решил сравнить операции
c = c *2
и
c = c << 1
Оказалось, что 2-я операция работает на 10 % дольше.
c = c + c
Сравнил.
c = c *2 быстрее c = c + c на 20 %.
13 июл 20, 13:50    [22166489]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
Dima T
Member

Откуда:
Сообщений: 14886
потести
c <<= 1
c *= 2
c += c
13 июл 20, 13:53    [22166495]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Мы еще несколько лет назад ковыряли перформанс для Питона и пришли к выводу что надо использовать
библиотеку NumPy.

https://numpy.org/doc/stable/user/quickstart.html
13 июл 20, 14:13    [22166518]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Dima T
потести
c <<= 1
c *= 2
c += c
Если взять за основу с = с * 2, то:
c <<= 1 - медленнее на 10 %
c *= 2 - медленнее на 15 %
c += c - медленнее на 4 %
13 июл 20, 14:20    [22166530]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
mayton
Мы еще несколько лет назад ковыряли перформанс для Питона и пришли к выводу что надо использовать
библиотеку NumPy.
https://numpy.org/doc/stable/user/quickstart.html
Здесь только работа с массивами,
здесь нет информации об лучшем представлении с = с * 2
13 июл 20, 14:27    [22166539]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
Dima T
Member

Откуда:
Сообщений: 14886
mayton
Мы еще несколько лет назад ковыряли перформанс для Питона и пришли к выводу что надо использовать
библиотеку NumPy.

https://numpy.org/doc/stable/user/quickstart.html

Может PyPy ?
13 июл 20, 14:34    [22166544]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Dima T
mayton
Мы еще несколько лет назад ковыряли перформанс для Питона и пришли к выводу что надо использовать
библиотеку NumPy.
https://numpy.org/doc/stable/user/quickstart.html

Может PyPy ?
Я не говорю о самом быстром языке.
Ведь ПИТОН не самый быстрый язык.

Мне важно понять:
какой оператор работает быстрее на ПИТОНе при умножении на 2?
Пока с = с * 2
13 июл 20, 14:57    [22166568]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
Dima T
Member

Откуда:
Сообщений: 14886
Gennadiy Usov
Dima T
пропущено...

Может PyPy ?
Я не говорю о самом быстром языке.
Ведь ПИТОН не самый быстрый язык.

Мне важно понять:
какой оператор работает быстрее на ПИТОНе при умножении на 2?
Пока с = с * 2

Если интересует скорость, то думаю есть смысл разобраться с PyPy. Это тоже питон, т.е. менять код не потребуется, но он гораздо быстрее работает.
13 июл 20, 15:03    [22166576]     Ответить | Цитировать Сообщить модератору
 Re: Факторизация чисел - ещё один метод (про единицы)  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Gennadiy Usov
Dima T
пропущено...

Может PyPy ?
Я не говорю о самом быстром языке.
Ведь ПИТОН не самый быстрый язык.

Мне важно понять:
какой оператор работает быстрее на ПИТОНе при умножении на 2?
Пока с = с * 2

Если сомневаешся - то бери просто корректный вариант. Этот вариант

с = с * 2


100% корректный.

Попытка использовать сдвиг вместо умножения - порождает новые проблемы такие
как предстваление отрицательных и вещесвтенных чисел. Для них сдвиг не работает.
13 июл 20, 15:44    [22166641]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2      [все]
Все форумы / Программирование Ответить