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

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

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

| Сообщение посчитали полезным:

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

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

| Сообщение посчитали полезным:

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

| Сообщение посчитали полезным:

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

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

| Сообщение посчитали полезным:

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

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

| Сообщение посчитали полезным:

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

да что ты говоришь?


Добавлено спустя 20 минут
BlackCode пишет:
Но это долго. ~15 минут.
x = 219692880
от x=1, прямым перебором, ~2-3 сек.

| Сообщение посчитали полезным:

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

| Сообщение посчитали полезным:

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

-----
2 оттенка серого

| Сообщение посчитали полезным:

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

| Сообщение посчитали полезным:

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

Добавлено спустя 2 минуты
SReg пишет:
А если ты утверждаешь что "Х как-раз один", значит ты не дал всю инфу, а тут не форум гадалок.
Каюсь
Ну вот теперь полная картина.
P.S. Я брутил на 32 битах, переписал на х64... действительно 2-3 секунды при всех условиях
Это уже приемлемо

Посему топик закрываю.
Спасибо всем откликнувшимся

| Сообщение посчитали полезным: