Как расширить вычисление до 2^120?

Question

[haqz]

мой код с данными на входе (input)несколько тысячь работает ок. У меня есть параметры delta и gamma и они работают с инпутом в несколько тысяч, какие нужны параметры delta и gamma что бы работать с инпутом 2^120 ?

input величина не известная!!!
В результате вычислений значение result должно быть 0x1.

from random import randint

N =    115792089237316195423570985008687907852837564279074904382605163141518161494337

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

i=0
#input2^^120 = 0x9fd24b3abe244d6c443df56fa494dc

input = 0x5f87 +1

delta = 12

gamma = 2

d1= 80

while i < 2**61:
    d= (divnum(input,delta)) 
    s = divnum(i,gamma) %N
    result = divnum(d,s)
    
    if result <input and result >=0:
        print("result",hex(result),"i",hex(i),"input",hex(input))
        
    i = i +1

Comments

[mayton2019]

Задание как-то странно звучит. А что делает твой алгоритм?

Понимаешь, чтобы улучшать или вносить изменения надо понять идею.

[haqz]

mayton2019, он делит число. Число инпут неизвестное(в другому алгоритме оно в другой "форме" поэтому оно неизвестно. изаестно только что оно в диапазоне от 2^119 до 2^120) и неидентифицируемое, илентифицируемое только result = 0x1(это хекс) = 1 в десятичной.

Такие дела. четные дельта и гамма примнимы к четному инпуту, и нечетные наоборот - к нечетномв инпуту.

Дело в том, что 2^120 очень большое число поэтому понадобилась помощь матеиатиков

Такие дела

???

[Алан Гибизов]

Не надо использовать input в качестве имени переменной, так как в Python есть встроенная функция input(), и вы ее так переназначаете. Надо что-либо точно не используемое. Например my_input или что-то в этом роде.

[Wataru]

haqz, опять что-то непонятное у вас. Научитесь уже формулировать вопросы.

Дано: ?
Найти: ?
Ограничения.

Пока так понимаю, что вам надо подобрать такие гамма и дельта (константы), Что любое число X <= 2^120 после домножения на гамма, деления на дельта и деления на произвольное i < 2^30 давало 1?

[haqz]

Wataru,

дано input = 0x9fd24b3abe244d6c443df56fa494dc

найти delta, gamma.

огрничения i < = 2^61

Чтобы давало 1

Хотябо приблизительно, какие значения будут у дельты и гаммы ?

И деление тут это умножение делиого на модульную инверсию делителя, а не коассическое деление

По моим прикмдкам работает дельта не больше 2^59. А гамму для нее я не нашел, гамма кратна дельте.

????

[Wataru]

haqz, Ответ, например:
delta = 1
gamma = 1
i = 0x9fd24b3abe244d6c443df56fa494dc
Или
delta = 0x9fd24b3abe244d6c443df56fa494dc
gamma = 1
i = 1

[haqz]

Wataru, мне и не надо i = input в итооге. мой алгоритм чтотбы i было меньше инпута. нет никакого смысла что либо решать алгооритмом который находит инпут, со скорость ничем не отличабшющей от скорости перебора i в диапазоне инпута !!!

[haqz]

Wataru, какая будет дельта что бы i стало всего 2^60 например или 2^59?

[Wattouch]

haqz, А результат обязательно должен быть равен строго единице? Я то знаю что нет. Вы это или умалчиваете или сами не в курсе всех тонкостей задачи.
Вы пытаетесь решить эту задачку в одиночку? Если объединить мозги, то может шансов было бы больше. Я уже обдумал множество подходов, мы могли бы обменяться идеями. И мне ваш диапазон 2^119 - 2^120 не интересен, есть покрупнее.

[haqz]

haqz,

Если result = 1, то получается i = input * (gamma / delta)

input немзвестная переменная !!! Ваш ответ, сорри, но помог тоько частично и еще не выяснил я ,может ли ваш ответ помочь в моем вопросе.

[mayton2019]

haqz, ты тово. Легче дави на газ. Я имею в виду восклицательные знаки. Звучит как окрик.

Ты-же со стороны выглядишь как лодырь который пришел сюда и даже тему лабораторной не сказал.
А хочешь чтобы все бегали вокруг тебя и решали. И скажи спасибо очень доброму Wataru который
хоть взялся тебе помогать.

Answer 1

[Wataru]

Код в вопросе найдет такое i, что result станет равен 1, если цикл сделать до N. Для любых дельта и гамма. (но там цикл не нужен вообще).

И наоборот. Какие бы вы дельта и гамма не взяли, может прийти такой Input, что result станет 1, только для очень большого i.

Во-первых, вам цикл не нужен. Вычисления ваши можно упростить.

result = (input / delta) / (i / gamma) = input * (gamma / delta) / i

Если result = 1, то получается i = input * (gamma / delta) (естественно, умножение и деление по модулю N).
Цикла не надо. Можно сразу вычислить искомое i.
Решение единственно (если N простое. А если оно не простое, то делить по модулю нельзя).

И это самое i может оказаться очень большим. Не всегда N-1, потому что у вас ограничение на Input есть дополнительное, Но даже в самом лучшем случае подбора гамма и дельта (обе по 1), вам может прийти input такой, что i будет равно 2^120.

Ну и, во-вторых, вам не нужны две константы дельта и гамма. Тут есть ровно одна степень свободы - значение gamma / delta. Это должна быть единственная константа в вашем коде. В итоге оно все упрощается до:

beta = 0x42
i = beta * input % N
result = 1

И вообще тут, очевидно, проблема XY. У вас есть какая-то задача X, вы придумали какую-то фигню, как-то сформулировали вот эту вот задачу в вопросе (У), но вы ошиблись. Решение вот этой фигни в вопросе вам никак не поможет решить вашу изначальную задачу, пототму что вам не хватает знаний (теории групп, например, да и математики в целом). Вы задаете практически бессмысленные вопросы (уже не первый раз). Если хотите, чтобы вам тут действительно помогли - давайте вашу изначальную задачу. Я подозреваю, что это взлом криптографии и вам тут популярно объяснят, что вы зря тратите время.

Comments

[haqz]

beta = 0x42
i = beta * input % N
result = 1

z = 0x5f87 * 0x42 % N = 0x18a0ce а не 1!

[haqz]

beta = 0x42
i = beta * input % N
result = 1

этот код к чему ? куда его можно вставить ? я как понял это решение дает всегда i > input ?!

input в задаче неизвестное ! А вы его используете как известную величину. Input и надо найти !!!

???

[haqz]

И полных советов и рекомендаций не получилось от Вас.

Вот результат работы кода:

result 0x0 i 0x0 input 0x5f88
result 0xfec i 0x1 input 0x5f88
result 0x7f6 i 0x2 input 0x5f88
result 0x3fb i 0x4 input 0x5f88
result 0x4 i 0x3fb input 0x5f88
result 0x2 i 0x7f6 input 0x5f88
result 0x1 i 0xfec input 0x5f88

Видите , пройдя i от 0 до 0xfec модно найти инпут input 0x5f88 !!! Разницу в сложно залачи с мои алгоритмом и без вы видите, но уводите меня в тему - что если раздели на 100, умнож на 100 и получищь искомое ... ))

[Wattouch]

Wataru, Вы правы про криптографию. Если автор считает что он близок к решению, то вполне здраво не рассказывать его публично. Задачка скорее всего не решаемая, но поломать над ней голову в свободное время вполне можно.

[haqz]

Wattouch, а нафига вы тогда читаете то что я пишу. вы постоянно хотите чето рвзузнать сами , спрашивая у меня.

[AVKor]

Я подозреваю, что это взлом криптографии и вам тут популярно объяснят, что вы зря тратите время.

Авторы "вечных двигателей" и "решений задачи о трисекции угла" невменяемы. Им что-то объяснять бесполезно.

[Wataru]

haqz,

z = 0x5f87 * 0x42 % N = 0x18a0ce а не 1!

0x5f87 - это input? А почему вы i на input умножаете, если формула в ответе, да и в вашем коде другая?

я как понял это решение дает всегда i > input ?!

Нет. Ведь умножение по модулю. Иногда оно дает i < input. Но всегда найдутся такие input, что i >= input.

input в задаче неизвестное ! А вы его используете как известную величину. Input и надо найти !!!

Но вы сами в своем коде input используете! Что значит, оно неизвестное, его надо найти, но result, вычисленный через него должен быть 1? А еще у вас в вопросе нигде не сказано, что вам надо i маленькое, что вы так какие-то вычисления ускоряете.

вы постоянно хотите чето рвзузнать

Я пытаюсь понять задачу. Поскольку вы не в состоянии свою задачу сформулировать, да и она бредовая и бессмысленая, единственная надежда понять, что же вам надо - это увидеть изначальную задачу (которая, очевидно, пришла к вам из внешнего мира, а не родилась у вас в голове. Это-то вы воспроизвести, надеюсь, можете).

Повторю свой вывод. i задается через gamma/delta/input однозначно (если result нужен 1) простой формулой. Но эта формула дает большие i для каких-то входных данных, как бы вы константы не меняли.
Таким способом вам ваши вычисления не ускорить.

[haqz]

Wataru, про то что пытаются разузнать это не вам адресовалось.

Но вы сами в своем коде input используете! Что значит, оно неизвестное, его надо найти, но result, вычисленный через него должен быть 1? А еще у вас в вопросе нигде не сказано, что вам надо i маленькое, что вы так какие-то вычисления ускоряете.

посмотрите, вот результат работы мтего скрипта:

result 0x0 i 0x0 input 0x5f88
result 0xfec i 0x1 input 0x5f88
result 0x7f6 i 0x2 input 0x5f88
result 0x3fb i 0x4 input 0x5f88
result 0x4 i 0x3fb input 0x5f88
result 0x2 i 0x7f6 input 0x5f88
result 0x1 i 0xfec input 0x5f88

result = 1 а i меньше инпут. Поэтому я могу найти инпут за количество операций = i а не инпуту.

Мои формулы сделаны так, что бы потом можно было инпут востановить кргда находится result = 1. С Вашими формулами все зацикливается на инпут и ничего восстановмть у меня не получается. ((((

[Wataru]

haqz,

result = 1 а i меньше инпут. Поэтому я могу найти инпут за количество операций = i а не инпуту.

Вот для этого конкретного Input у вас оказалось итераций меньше.
А для какого-то другого инпута понадобится больше итераций чем он сам.

Мои формулы сделаны так, что бы потом можно было инпут востановить кргда находится result = 1

Нет. ваши формулы вычисляют result через i и input. Как вы input вычисляете по ним - вообще непонятно. Переформулируйте задачу. Третий раз повторяю. Что дано? Что надо сделать?

У вас там гомоморфное шифрование, что ли, что input дан защифрованный, но вы можете производить над ним арифметические операции и сравнивать с единицей?

[haqz]

0x5f87 - это input? А почему вы i на input умножаете, если формула в ответе, да и в вашем коде другая?

вот в Вашем ответе input:

beta = 0x42
i = beta * input % N
result = 1

и результат конечно только усложняется когда input умножают на бету.

[Wataru]

haqz,

beta = 0x42
i = beta * input % N
result = 1

Ну так высчитайте result = divnum(input*beta %n, i). Получите 1, как и хотите. И не надо в цикле i перебирать вообще.

[Wataru]

haqz, Вы когда цитируете мои ответы, окружайте циату в тег blackquote (кнопка с кавычками в редакторе).

[haqz]

Wataru,

я поместил Вашу формулу i = beta * input % N в код, result = 1 не аолучается

??

from random import randint

N =    115792089237316195423570985008687907852837564279074904382605163141518161494337

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


input = 0x5f87 +1
beta = 2 #12 / 6 # это дельта / гамма
i =0
while i < 100:
    result = divnum(input*beta %N, i)

    if result >=1:print(hex(result),hex(input))
    i = i +1

[Wataru]

я поместил Вашу формулу i = beta * input % N в

Не поместили:
while i < 100:

Вот:

i = beta * input % N
result = divnum(input*beta %N, i)

Очевидно, что тут result будет 1? Потому что это divnum(x,x) - деление себя на себя.

Понятно, что divnum(input*beta %N, i) это то же самое, что ваше:

d= (divnum(input,delta)) 
s = divnum(i,gamma) %N
result = divnum(d,s)

где delta = divnum(1,beta), gamma = 1?

[haqz]

Wataru,

Очевидно, что тут result будет 1? Потому что это divnum(x,x) - деление себя на себя.

в мрем коде

result = divnum(d,s)

тут d использует input, а s не использует и 1 получается, те равенство что я в

s = divnum(i,gamma)

назожу с помощью i и гамма, числр равноое d, но инпут при этом не использую.

По осталььному, сечас я иду спать, проснусь буду разбиратся в вашем месседже.

Спасибо Вам за Ваше время.

До связи