Как вычислить правильно в скрипте python?

Question

[haqz]

N порядка 2^256!!!

#формула :

# dd = ((x / a) * b1) / c) * d1

Как сделать что бы из любого x диапазона 2^119-2^120, получиь dd размером не больше 2^60 - 2^70 ??? Тех кто поможет я символически отблагодарю.

#формула :

# dd = ((x / a) * b1) / c) * d1


from random import randint

import random

N =    115792089237316195423570985008687907852837564279074904382605163141518161494337

def inv(v): return pow(v, N-2, N)
def divnum(a, b): return ( (a * inv(b) ) % N )


#x= random.randint(2**119,2**120)

x = 0xb05ef9299a4d346351f33dd336395d
print("x",hex(x))



a = 0x961#

aa = divnum(x,a)

print("aa",hex(aa))


#aa = 0x337fa0776aba96c38b918a1367be52191ed660152236566e06f66da4d43fb700

b1 = 49 #35

bb = aa * b1 % N

# bb = 0xdb6db6db6db6db6db6db6db6db6db6da56e29fef62d8e8f596c5a9994e49bbb7
print("bb", hex(bb))

c1 = 35 

c = divnum(1, c1) 

# c = 0xea0ea0ea0ea0ea0ea0ea0ea0ea0ea0e8e532290d6d0f3369d3f389a550a6a21

print("c",hex(c))

d1 = 1

dd = (divnum(bb,c) * d1)%N

#dd =0x7dfab1f9251293225f1b754db90467


print("dd",hex(dd))

print(hex(x-dd))

Comments

[Anonymous]

С таким на Хабр Фриланс.

[haqz]

Никита Савченко, почему ? тут никого нет кто сможет ? Или убрать инфу о вознаграждении ?

[Anonymous]

haqz, во первых, вы написали это как задание.
Во вторых, отформатируйте код.

[haqz]

Никита Савченко, исправил. Прошу помочь.

[Anonymous]

haqz, я не эксперт по Питону, программирую на JS.
Просто заметил вопрос и дал вам советы.

[RINCODE]

Можете написать мне в ТГ, указан у меня в профиле

[Wattouch]

А для чисел в диапазоне 2^2 - 2^70 у вас уже есть готовая таблица? ;)
Я обдумал уже множество подходов к этой задачке и к сожалению она скорее всего не решаемая.
Вам не интересно обсудить лично? Боитесь что украду решение?

[Wattouch]

А может получится как-то избавиться от дробной части числа после деления на 7?
А то вон как красиво:
1/7=0,142857142857143
2/7=0,285714285714286
3/7=0,428571428571429

Answer 1

[Wataru]

Я так понял, надо подобрать константы a,b,c,d?
Вообще, можно a, b1, c считать равными 1 и менять только d.

Но у вас там умножение и деление по модулю. Так что все очень сложно.

Вообще, ваша задача не имеет решения.

Модуль у вас в вопросе порядка 10^78. А X может быть 10^119-10^120. Если x взять по модулю N, то там может получится вообще любой остаток (потому что 10^120-10^119 = 9*10^119 > N)

А дальше, умножая эти числа на константу, если N простое (а оно должно быть простым, иначе деление по модулю не определено), то можно получить любой остаток до N. Не только до 2^60 - 2^70.

Comments

[haqz]

модуль у меня в вопросе порядкс 2^256 !

менять можно все, по поводу остатков, формула дает не столь печальные результаты. можете заменить x на ранжоминт и увидмте что там часто результат мегьше делимого будет. Вообще, если результат будет напоимер 1 из 7 напоимер, это тоже неплохой результат. Почему 1 из 7, по тому что залача может решится не относительно 1 / 7 , а 2/7,3/7...6/7.

[Wataru]

haqz,
2^256 ~= 10^78

Какие бы вы константы a/b/c/d не взяли результат будет меньше k ровно для k/N входных данных.
Потому что это умножение на константу по модулю N и оно обратимо.

Поэтому что ни делай, какие константы не подбирай, результат будет меньше 10^70 d 10^70/10^78 = 10^-8 случаев. Никакой 1/7 и даже 1/1000 тут и не пахнет.

[haqz]

Wataru, мой пример опускает диапазон на много тоже и никаких к/n комбинаций, слава богу !

[Wataru]

haqz, Что? Ничего не понял.

[RINCODE]

Wataru, Что это вообще такое и зачем оно нужно?
Мод код уже прогнал 300.000 возможных вариантов, ни одного ответа

[haqz]

Wataru, мой код запусиите вот в таком виде

x= random.randint(2**119,2**120)

#x = 0xb05ef9299a4d346351f33dd336395d

и минимус каждая 7я итерация будет без остатка.

моя идея в том что разделит X на aa(кратеый 7), потрм множить на кратное 7 49 и потрм разделить на кратеое 7 35. поэтому у меня и результатов с остатками меньше.

????

Нужно подеделить х на 2^58 и найти решение которое будет в районк 2^62.

???

[RINCODE]

haqz, тот код который у вас я прокрутил

Попытка №3149376
Попытка №3149377
Попытка №3149378

Ни одного решения если я правильно записал конечно, я так и не понял в чем смысл программы и что происходит в коде и для чего, по этому я пойду по дальше от математики

[Wataru]

haqz, В смысле - без остатка?

Вообще сформулируйте задачу четче.

Надо подобрать a,b,c,d так, что любое/как можно больше x= random.randint(2**119,2**120) после домножения на 1/a*b/c*d было меньше 10^70?

[Wataru]

RINCODE, Ах, или я читал жопой, или вы отредактировали вопрос. Теперь там надо до 2^70. Что понижает шансы на успех с одной 10-ти-миллионной до 2^-50, что совсем печально.

[RINCODE]

Wataru, Зачем вообще это надо?

[haqz]

RINCODE,

разделите 2^58 на 7 и поделите x на (int(2^58/7) * 7 число потом умеожте полученный результат на int(2^24/7,)*7 и потом поделите полученно на ,int(2^14/7). как то так

[haqz]

В смысле - без остатка?

Вообще сформулируйте задачу четче.

Надо подобрать a,b,c,d так, что любое/как можно больше x= random.randint(2**119,2**120) после домножения на 1/a*b/c*d было меньше 10^70?

Wataru, да, именно так милейший ! Как это сделать ?

[haqz]

Wataru, нужно что бы в результате было любое не больше 2^75

[RINCODE]

haqz, Ну вот у меня получилось пару чисел
2.192456894852611e+23
1.9902523110067383e+23
И дальше рандомит, вроде правильно написал
И не игнорируйте ТГ, раз написали)
Но это без условия third > 2**60 and third < 2**70:

[Wataru]

haqz,

Надо подобрать a,b,c,d так, что любое/как можно больше x= random.randint(2**119,2**120) после домножения на 1/a*b/c*d было меньше 10^70?

Ответ - НИКАК!
(если не считать тривальный случай a=b=c=1, d = 0, но вряд ли вам это подходит).

Могу вам математически доказать, что какие бы вы a/b/c/d не выбрали, результат всегда будет меньше T ровно для каждого T/N (В вашем случае T~2^70, N~2^256 T/N~= 2^-180). Это очень маленький шанс.

Если бы T = 1 А N=239, то какие бы вы a/b/c/d не выбрали, ответ будет хорошим ровно в 1/239 случаев.

[Wattouch]

haqz, можете показать пример, где из 7 подряд идущих чисел, после совершения над ними всех операций, более 1 числа дадут результат без дробной части? Надеюсь что я понятно сформулировал.

[haqz]

Wattouch, модульные вычисления, тут дробной части нет, в классическом ее смысле. Я сам не знаю настолько что бы обьяснять. сорян

[Wattouch]

haqz, чтобы переместить любое число из диапазона 2^119-2^120 в диапазон 2^60 - 2^70, достаточно например многократно поделить его на 2.
Но проблема в том, что у него образуется неизвестная дробная часть.

[Wattouch]

haqz, боюсь ошибиться в формулировке, но вы можете разделить по модулю точку на эллиптической кривой?