Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 [5]      все
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
А что мы знаем о числе N = x * y, которое необходимо факторизировать?

1. Корень из N - для начала поиска чисел А и В.

2. Длина в битах - можно использовать для поиска окрестностей единиц.

3. Последние цифры - для определения последних цифр чисел x и y, и для определения шага (x + y) или А.

А что ещё?

Сообщение было отредактировано: 3 июн 20, 09:05
3 июн 20, 09:05    [22144685]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Barlone
Member

Откуда:
Сообщений: 1402
Gennadiy Usov
А что мы знаем о числе N = x * y, которое необходимо факторизировать?

1. Корень из N - для начала поиска чисел А и В.

2. Длина в битах - можно использовать для поиска окрестностей единиц.

3. Последние цифры - для определения последних цифр чисел x и y, и для определения шага (x + y) или А.

А что ещё?
Остатки по любым простым модулям. Каждый остаток по простому модулю сокращает количество возможных значений x+y примерно в два раза: (x+y)2/4 - N mod p должно быть квадратичным вычетом.

Сообщение было отредактировано: 3 июн 20, 09:14
3 июн 20, 09:13    [22144688]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Barlone
Gennadiy Usov
А что мы знаем о числе N = x * y, которое необходимо факторизировать?
1. Корень из N - для начала поиска чисел А и В.
2. Длина в битах - можно использовать для поиска окрестностей единиц.
3. Последние цифры - для определения последних цифр чисел x и y, и для определения шага (x + y) или А.
А что ещё?
Остатки по любым простым модулям. Каждый остаток по простому модулю сокращает количество возможных значений x+y примерно в два раза: (x+y)2/4 - N mod p должно быть квадратичным вычетом.
Есть одно но:
мы не можем найти все такие остатки для больших чисел.

А если пользуясь термином "сокращает количество ... примерно в два раза",
то, зная остатки по 140 простым числам, уменьшаем в 2^140 раз?

Сообщение было отредактировано: 3 июн 20, 09:23
3 июн 20, 09:21    [22144690]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Barlone
Member

Откуда:
Сообщений: 1402
Gennadiy Usov

А если пользуясь термином "сокращает количество ... примерно в два раза",
то, зная остатки по 140 простым числам, уменьшаем в 2^140 раз?
Ага. Только это сложно использовать. Мы знаем, что остаток по каждому модулю - один из нескольких возможных. Если выбрать по одному произвольному из допустимых остатку, и по китайской теореме собрать остаток по модулю произведения этих 140 простых - получим огромное число, гораздо больше N.
Можно попробовать использовать что-то типа решета: вычеркивать недопустимые остатки. Только нужен кусок памяти размером порядка квадратного корня из N. Если придумаете, как построить число, которое лежит в нужном диапазоне, и одновременно имеет остатки по простым модулям из числа допустимых - сможете сломать RSA :)
3 июн 20, 11:19    [22144750]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Barlone
Gennadiy Usov
А если пользуясь термином "сокращает количество ... примерно в два раза",
то, зная остатки по 140 простым числам, уменьшаем в 2^140 раз?
Ага. Только это сложно использовать.
Мы знаем, что остаток по каждому модулю - один из нескольких возможных.
Если выбрать по одному произвольному из допустимых остатку, и по китайской теореме собрать остаток по модулю произведения этих 140 простых -
получим огромное число, гораздо больше N.

Можно попробовать использовать что-то типа решета: вычеркивать недопустимые остатки.
Только нужен кусок памяти размером порядка квадратного корня из N.
Если придумаете, как построить число, которое лежит в нужном диапазоне,
и одновременно имеет остатки по простым модулям из числа допустимых - сможете сломать RSA :)
Я тут попробовал по китайской теореме смотрел остатки степеней 2 по модулю N, чтобы определить единицу.

Где-то после 2^20 идёт серьёзное увеличение по времени расчёта.
3 июн 20, 11:29    [22144761]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Barlone
Остатки по любым простым модулям. Каждый остаток по простому модулю сокращает количество возможных значений x+y примерно в два раза: (x+y)2/4 - N mod p должно быть квадратичным вычетом.
Видел публикации, где говорилось о более удобном модуле - 20.

Меньше выборок по остаткам.

А по разным простым модулям будут сложные построения.

Или все остатки собирать в одном массиве, чтобы число в массиве было равно количеству модулей.

Сообщение было отредактировано: 3 июн 20, 16:43
3 июн 20, 16:42    [22145093]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6017
Barlone,

было бы идеально если бы можно было свести задачу к другому модулю
3 июн 20, 21:01    [22145305]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Barlone
Каждый остаток по простому модулю сокращает количество возможных значений x+y примерно в два раза:
(x+y)2/4 - N mod p должно быть квадратичным вычетом.
То есть, должно выполняться уравнение по квадратичным вычетам:
(x+y)2/4 - N = (x-y)2/4 mod p
7 июн 20, 19:47    [22147145]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Обычно, в тесте Ферма при определения остатков перебираются показатели степени для определённого основания степени.

А есть ли работы по перебору оснований степени?
13 июн 20, 11:15    [22150080]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6017
Barlone
Gennadiy Usov

А если пользуясь термином "сокращает количество ... примерно в два раза",
то, зная остатки по 140 простым числам, уменьшаем в 2^140 раз?
Ага. Только это сложно использовать. Мы знаем, что остаток по каждому модулю - один из нескольких возможных. Если выбрать по одному произвольному из допустимых остатку, и по китайской теореме собрать остаток по модулю произведения этих 140 простых - получим огромное число, гораздо больше N.
Можно попробовать использовать что-то типа решета: вычеркивать недопустимые остатки. Только нужен кусок памяти размером порядка квадратного корня из N. Если придумаете, как построить число, которое лежит в нужном диапазоне, и одновременно имеет остатки по простым модулям из числа допустимых - сможете сломать RSA :)
не совсем понял
группа остатков по простым модулям это собственно "система остаточных классов", там как бы проблем то нет

если этим можно представить q^2|n=1 и q < n, то остатков то не так много нужно

за счёт чего "(x+y)2/4 - N mod p должно быть квадратичным вычетом" уменьшает количество значений вдвое?
22 июн 20, 09:47    [22154940]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Barlone
Member

Откуда:
Сообщений: 1402
kealon(Ruslan)

за счёт чего "(x+y)2/4 - N mod p должно быть квадратичным вычетом" уменьшает количество значений вдвое?

Мы пытаемся представить нечетное составное 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]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Barlone
kealon(Ruslan)
за счёт чего "(x+y)2/4 - N mod p должно быть квадратичным вычетом" уменьшает количество значений вдвое?
Мы пытаемся представить нечетное составное 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.
А почему рассматривается только s или d?

Необходимо рассматривать комбинацию разностей остатков для s и d.
22 июн 20, 13:11    [22155104]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6017
Barlone,

но так выходит дофига комбинаций, которые надо проверять
т.е. уменьшения в два раза то и нету

т.е. допустим для представления N нам достаточно СОК из K простых чисел

у нас выходит П(Pi/2, i = 1..k) вариантов для перебора, что приблизительно равно N/ 2^K - и это очень дофига
22 июн 20, 16:31    [22155263]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
В продолжение 22144685:

4. Величину s = (х + y) mod 6
29 июн 20, 15:02    [22159106]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Решил поработать с р-методом логарифмирования.

Много разных публикаций с разными алгоритмами.
Скачал на Питоне программу, которая не всегда работает
https://ru.wikibooks.org/wiki/Реализации_алгоритмов/P-метод_Полларда_дискретного_логарифмирования

Было бы интересно обсудить данный метод.
6 июл 20, 05:21    [22162503]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

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

А у меня вопрос:
на настоящий момент какое количество простых чисел удалось применить в одной сетке и какой размер ячеи такой сетки?
30 июл 20, 16:58    [22175802]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Допустим, есть число 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]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
У алгоритма Гельфонда -Шенкса есть одно неудобство:
необходимо сравнивать каждое число второй сетки с каждым числом первой сетки.

А если на первую сетку "наложить" третью сетку?
Некоторая сортировка.

Тогда в несколько раз можно уменьшить количество сравнений между первой и второй сетками.
4 авг 20, 20:38    [22177625]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Gennadiy Usov, какую цель ты преследуешь?

Мы, программисты добиваемся того чтобы ответ от программы был получен за разумное время.
4 авг 20, 21:45    [22177647]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
mayton,

почти во всех известных методах факторизации за основу берется уравнение n = A^2 - B^2.
(или во всех ?)

А если за основу методов факторизации взять 2^(x + y) = 2^(n + 1) mod n?

Или за основу взять лучшее от этих двух уравнений.

Второе уравнение применяется только про дискретном логарифмировании.(?)

Сообщение было отредактировано: 5 авг 20, 06:05
5 авг 20, 06:06    [22177715]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Barlone
Member

Откуда:
Сообщений: 1402
Gennadiy Usov
mayton,

почти во всех известных методах факторизации за основу берется уравнение n = A^2 - B^2.
(или во всех ?)
Не во всех. Есть же p-1 метод Полларда. Там как раз предполагая, что N=p*q, ищем такое x, что ax=1 mod p и ax≠1 mod q. Тогда gcd(ax%N-1,N)=p
Для поиска x используется то, что если ax=1 mod p то и ax*y=1 mod p при любом y
Метод эллиптических кривых работает так же, только вместо вычетов по модулю N использует точки на эллиптической кривой.
5 авг 20, 06:42    [22177719]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6017
Gennadiy Usov,

не во всех, есть ещё Метод разложения Эйлера

Сообщение было отредактировано: 5 авг 20, 09:12
5 авг 20, 09:11    [22177751]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
kealon(Ruslan)
Gennadiy Usov,
не во всех, есть ещё Метод разложения Эйлера
Интересный метод, но в нём нет 2^.
Я это имел в виду, а есть там + или - , то это уже вторично.

Сообщение было отредактировано: 5 авг 20, 11:41
5 авг 20, 11:34    [22177839]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 [5]      все
Все форумы / Программирование Ответить