eXeLab
eXeL@B ВИДЕОКУРС !

ВИДЕОКУРС
выпущен 4 ноября!


УЗНАТЬ БОЛЬШЕ >>
Домой | Статьи | RAR-cтатьи | FAQ | Форум | Скачать | Видеокурс
Новичку | Ссылки | Программирование | Интервью | Архив | Связь

Русский / Russian English / Английский

Сейчас на форуме: (+1 невидимый пользователь)
 · Начало · Статистика · Регистрация · Поиск · ПРАВИЛА ФОРУМА · Язык · RSS · SVN ·

 eXeL@B —› Крэки, обсуждения —› Деление с остатком
Посл.ответ Сообщение


Ранг: 54.6 (постоянный)
Статус: Участник

Создано: 10 июня 2018 23:44 New!
Цитата · Личное сообщение · #1

Привет всем
Просьба помочь в решении задачи.

X mod 19 = 3
X mod 31 = 3
X mod 61 = 38
X mod 13 = 4
X mod 11 = 0
X mod 73 = 37

Где X - это 64-битное число, в данном случае 3601766713861722813.
В распоряжении имеем шесть чисел.

764278 mod 19 = 3
632806 mod 31 = 3
579965 mod 61 = 38
549410 mod 13 = 4
3054348 mod 11 = 0
167061 mod 73 = 37

Т.е. большое число сравнимо по модулям с малыми числами.
Вопрос, возможно ли вычислить Х, используя выше приведенные данные, не прибегая к бруту?
Спасибо.

Ранг: 409.2 (мудрец)
Статус: Участник

Создано: 10 июня 2018 23:51 · Поправил: dosprog New!
Цитата · Личное сообщение · #2

BlackCode пишет:
Т.е. большое число сравнимо по модулям с малыми числами.

) А ещё большое число сравнимо с малыми по делителям?

Ранг: 141.4 (ветеран)
Статус: Участник

Создано: 11 июня 2018 00:50 New!
Цитата · Личное сообщение · #3

BlackCode пишет:
Вопрос, возможно ли вычислить Х, используя выше приведенные данные, не прибегая к бруту?

Нет. Ты его даже брутом не вычислишь, потому что множество иксов, которое удовлетворяет условиям бесконечно.

Ранг: 0.0 (гость)
Статус: Участник

Создано: 11 июня 2018 01:17 New!
Цитата · Личное сообщение · #4

BlackCode пишет: Вопрос, возможно ли вычислить Х, используя выше приведенные данные, не прибегая к бруту?

Хотелось бы криптографические алгоритмы мимоходом решать. Но нет, нельзя.


Ранг: 54.6 (постоянный)
Статус: Участник

Создано: 11 июня 2018 06:58 · Поправил: BlackCode New!
Цитата · Личное сообщение · #5

rmn пишет:
Нет. Ты его даже брутом не вычислишь, потому что множество иксов, которое удовлетворяет условиям бесконечно.

Вот брутом вопрос решается. Но это долго. ~15 минут.
rmn пишет:
Нет. Ты его даже брутом не вычислишь, потому что множество иксов, которое удовлетворяет условиям бесконечно.

Х как-раз один

3601766713861722813 mod 19 = 3
3601766713861722813 mod 31 = 3
3601766713861722813 mod 61 = 38
3601766713861722813 mod 13 = 4
3601766713861722813 mod 11 = 0
3601766713861722813 mod 73 = 37

Вот задача и состоит в том, чтобы найти хотя бы одно решение из множеств. Не используя брут.

Ранг: 299.1 (наставник)
Статус: Модератор
CrackLab

Создано: 11 июня 2018 07:18 New!
Цитата · Личное сообщение · #6

BlackCode пишет:
Х как-раз один

3601766713861722813 mod 19 = 3
3601766713861722813 mod 31 = 3
3601766713861722813 mod 61 = 38
3601766713861722813 mod 13 = 4
3601766713861722813 mod 11 = 0
3601766713861722813 mod 73 = 37


да что ты говоришь?
Code:
  1. >>> 
  2. ====================== RESTART: C:\z3py\bin\example.py ======================
  3. sat
  4. [= 1071158920617329236]
  5. >>>


Добавлено спустя 20 минут
BlackCode пишет:
Но это долго. ~15 минут.

x = 219692880
от x=1, прямым перебором, ~2-3 сек.


Ранг: 54.6 (постоянный)
Статус: Участник

Создано: 11 июня 2018 08:13 New!
Цитата · Личное сообщение · #7

SReg пишет:
да что ты говоришь?

Тот вопрос, что я привел, это только часть вычислений)

3601766713861722813 mod 3141591 = 1383840
Это плюс к выше указанному.

3601766713861722813 mod 19 = 3
3601766713861722813 mod 31 = 3
3601766713861722813 mod 61 = 38
3601766713861722813 mod 13 = 4
3601766713861722813 mod 11 = 0
3601766713861722813 mod 73 = 37

И начинается перебор от 1000000000000.
Конечная цель задачи - найти множимое значение.
т.е. Y * 3141591 + 1383840 = X


Ранг: 227.3 (наставник)
Статус: Участник

Создано: 11 июня 2018 08:24 New!
Цитата · Личное сообщение · #8

Я бы перебирал n, где n*73+37=x

Ранг: 299.1 (наставник)
Статус: Модератор
CrackLab

Создано: 11 июня 2018 08:50 New!
Цитата · Личное сообщение · #9

BlackCode пишет:
что я привел, это только часть вычислений)

Что ты выложил, от того и плясали.
А если ты утверждаешь что "Х как-раз один", значит ты не дал всю инфу, а тут не форум гадалок.


Ранг: 54.6 (постоянный)
Статус: Участник

Создано: 11 июня 2018 08:51 · Поправил: BlackCode New!
Цитата · Личное сообщение · #10

f13nd пишет:
Я бы перебирал n, где n*73+37=x

Я перебираю n*3141591 + 1383840 = х

Добавлено спустя 2 минуты
SReg пишет:
А если ты утверждаешь что "Х как-раз один", значит ты не дал всю инфу, а тут не форум гадалок.

Каюсь
Ну вот теперь полная картина.
P.S. Я брутил на 32 битах, переписал на х64... действительно 2-3 секунды при всех условиях
Это уже приемлемо

Посему топик закрываю.
Спасибо всем откликнувшимся
 eXeL@B —› Крэки, обсуждения —› Деление с остатком
Эта тема закрыта. Ответы больше не принимаются.

Оригинальный DVD-ROM: eXeL@B DVD !

Вы находитесь на форуме сайта EXELAB.RU
Проект ReactOS