powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Факторизация чисел - ещё один метод (про единицы)
25 сообщений из 31, страница 1 из 2
Факторизация чисел - ещё один метод (про единицы)
    #39930192
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Решил анализировать формулу Ферма 2^(n – 1) (mod n) на все значения показателя степени от 0 до (n – 1).
Оказалось, что из этой информации можно получить сомножители числа n.

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

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

mayton
Усов. Бросай свои числа. Go-go решать задачи.
А что, mayton, будем Go-go искать единицы?
...
Рейтинг: 0 / 0
Факторизация чисел - ещё один метод (про единицы)
    #39930285
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Нет. Я пока не go-go. Тема - весьма специфичная.
...
Рейтинг: 0 / 0
Факторизация чисел - ещё один метод (про единицы)
    #39930382
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usov, совсем неинтересно. Очевидно, что если число - псевдопростое по Ферма по некоторому основанию, а Миллер-Рабин по этому же основанию говорит, что число составное - то это автоматически дает нам факторизацию. Только трудоемкость подбора какого такого основания превышает перебор делителей.
...
Рейтинг: 0 / 0
Факторизация чисел - ещё один метод (про единицы)
    #39930384
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Или тут имелся ввиду p-1 - метод Полларда ?
...
Рейтинг: 0 / 0
Факторизация чисел - ещё один метод (про единицы)
    #39930397
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 порядка 2 128 .
...
Рейтинг: 0 / 0
Факторизация чисел - ещё один метод (про единицы)
    #39930401
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Barlone
Или тут имелся ввиду p-1 - метод Полларда ?
p-1 - метод Полларда хорошо "отсекает" малые делители.

Метод определения единиц хорошо "отсекает" большие делители, близкие к "корню".
...
Рейтинг: 0 / 0
Факторизация чисел - ещё один метод (про единицы)
    #39930406
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Или вариация на тему квадратичных форм Шенкса - цепочка редукций фактически дает нам набор равенств:
b 1 2 - a 0 a 1 = N
b 2 2 - a 1 a 2 = N
b 3 2 - a 2 a 3 = N
.....
b n 2 - a n-1 a n = N
При этом a 0 = 1, а из первого цикла мы выходим, когда a n оказывается квадратом.
И зачем нам нужен второй цикл, если в этот момент (b 1 *b 2 *...*b n ) 2 ≡ a 0 *(a 1 *a 2 *...*a n-1 ) 2 *a n mod N
Если a 0 и a n квадраты, имеем классическое равенство для факторизации x 2 ≡ y 2 mod N
Ну и соответственно начинать можно не только с a 0 = 1, но и например с любого квадрата простого числа, найдя b 1 как квадратный корень из N по модулю квадрата этого простого (тут есть алгоритм Тонелли — Шенкса ).
...
Рейтинг: 0 / 0
Факторизация чисел - ещё один метод (про единицы)
    #39930558
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
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 порядка 2 128 .
Спасибо за формулу для "= 1 mod N"!

Да, у меня получается дискретное логарифмирование для h=1.
Только имеются не одна, а несколько групп (параметр n).
...
Рейтинг: 0 / 0
Факторизация чисел - ещё один метод (про единицы)
    #39930753
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Barlone
для произвольного a должно выполняться a (p-1)(q-1)/2 = 1 mod N
Преобразуем это равенство: a (pq+1)/2 = a (p+q)/2 mod N
Левую часть мы знаем. И нам нужно найти дискретный логарифм в правой части.
Здесь определяется некоторое число из группы значений. А нужно искать единицу.

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

Если решение не подходит, так как число В = p-q не целое число (а именно так проверяется единица),
то надо искать следующее решение.
...
Рейтинг: 0 / 0
Факторизация чисел - ещё один метод (про единицы)
    #39930865
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
вот тут ваша единица

теория
...
Рейтинг: 0 / 0
Факторизация чисел - ещё один метод (про единицы)
    #39930877
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Barlone
вот тут ваша единица
теория
Странно, в статье по таблице наименьший показатель для 7 есть 6 ,
а в реальности 3:
2^3 = 1 (mod 7)
...
Рейтинг: 0 / 0
Факторизация чисел - ещё один метод (про единицы)
    #39930903
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usov
Barlone
вот тут ваша единица
теория
Странно, в статье по таблице наименьший показатель для 7 есть 6 ,
а в реальности 3:
2^3 = 1 (mod 7)

Ну а 3^3 = 6 (mod 7)
Надо "для всех целых, взаимно простых с модулем".
...
Рейтинг: 0 / 0
Факторизация чисел - ещё один метод (про единицы)
    #39932281
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Как у каждого метода в факторизации, для метода определения единиц существуют проблемные числа.
Для этих чисел с помощью единиц нельзя определить сомножители.

Например, число 625 (5*127)...
...
Рейтинг: 0 / 0
Факторизация чисел - ещё один метод (про единицы)
    #39932299
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usov, 127 вольт остались в далёком прошлом, сейчас всюду 220 вольт.
...
Рейтинг: 0 / 0
Факторизация чисел - ещё один метод (про единицы)
    #39936430
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Barlone
Тут можно использовать вариацию на тему метода больших и малых шагов . Большой шаг будет произведением некоторого набора маленьких простых чисел, а на возможные значения малых шагов у нас уже есть ограничение: ((p+q)/2) 2 - N должно быть квадратичным вычетом по модулю каждого из этих маленьких простых.
Такой алгоритм должен неплохо работать до значений N порядка 2 128 .
Спасибо за подсказку!

Немного поправил статью:
http://sci-article.ru/stat.php?i=1583822766
Добавил средний шаг
...
Рейтинг: 0 / 0
Факторизация чисел - ещё один метод (про единицы)
    #39973761
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Согласно МТФ: если число p - простое, то 2^(p-1) = 1 (mod p).

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

Спрашивается:
а какая «судьба» остальных чисел в количестве (34-12) между 1 и 34?
...
Рейтинг: 0 / 0
Факторизация чисел - ещё один метод (про единицы)
    #39973769
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
...
Рейтинг: 0 / 0
Факторизация чисел - ещё один метод (про единицы)
    #39973784
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Есть некоторое отличие квадратичных вычетов от остатков по модулю для 2^.

Например. для 35
если 2^, то есть 22, 23, которых нет в х**2
если х**2, то есть 15, 14, 21, 25, 30, которых нет в 2^
...
Рейтинг: 0 / 0
Факторизация чисел - ещё один метод (про единицы)
    #39978761
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Решил сравнить операции
c = c *2
и
c = c << 1

Оказалось, что 2-я операция работает на 10 % дольше.
...
Рейтинг: 0 / 0
Факторизация чисел - ещё один метод (про единицы)
    #39978762
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
А если сравнивать операции
c = c /2
и
c = c >> 1

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

Однако, 1-я операция будет не int,
и чтобы перевести число в int необходимо потратить ещё в 3 раза больше времени, чем было потрачено на c = c /2
...
Рейтинг: 0 / 0
Факторизация чисел - ещё один метод (про единицы)
    #39978797
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usov
Решил сравнить операции
c = c *2
и
c = c << 1

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


c = c + c
...
Рейтинг: 0 / 0
Факторизация чисел - ещё один метод (про единицы)
    #39978808
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Процессор быстрее всего выполняет операцию битового сдвига, она технически проще, чем сложение или умножение, деление еще тяжелее.

Почему сдвиг медленнее в конкретном ЯП - скорее всего связано с внутренним устройством это ЯП, т.е. с тем какие еще инструкции выполняет процессор кроме самого сдвига.
...
Рейтинг: 0 / 0
Факторизация чисел - ещё один метод (про единицы)
    #39978953
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Aleksandr Sharahov
Gennadiy Usov
Решил сравнить операции
c = c *2
и
c = c << 1
Оказалось, что 2-я операция работает на 10 % дольше.
c = c + c
Сравнил.
c = c *2 быстрее c = c + c на 20 %.
...
Рейтинг: 0 / 0
Факторизация чисел - ещё один метод (про единицы)
    #39978959
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
потести
Код: javascript
1.
2.
3.
c <<= 1
c *= 2
c += c
...
Рейтинг: 0 / 0
Факторизация чисел - ещё один метод (про единицы)
    #39978975
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Мы еще несколько лет назад ковыряли перформанс для Питона и пришли к выводу что надо использовать
библиотеку NumPy.

https://numpy.org/doc/stable/user/quickstart.html
...
Рейтинг: 0 / 0
25 сообщений из 31, страница 1 из 2
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Факторизация чисел - ещё один метод (про единицы)
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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