Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Algo » HASH
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Ya nashel hash ot podstroki . I mne nado podelit !!! Chto by podelit nado obratniy element po modulu!!!!
a*x=1(mod 2^64) gde x=a^-1
a*x + 2^64*y = 1!!! U menya problema ,kak predstavit 2^64? Ved' 2^64 nezya predstavit vide unsigned long long !!!
A zachem eto nado? Pokashute uslovie,moshet est' bolee vigodnie reshenia,ili voz'mite modul pomen'she (2^63).
Даже если можно было представить, то все равно этот метод работал бы только для нечетных чисел. Я не знаю, действительно ли вам нужно деление, думаю там можно обойтись умножением и отниманием, но если оно все же необходимо, возьмите какой-нибудь простой модуль, правда тогда вместо естественного переполнения надо будет часто брать остаток по модулю и следить, чтобы небыло переполнения.
Net imenno delenie nado!!!! i tam vsegda u menya ne4etnoe 4islo.
a*x+2^64*y=1
a=31^k (t.e a yavlyaetsya stepenuy 31).izpolzuya eti informacii, dumau zdes mojno cheto pridumat!!!
Ну раз так, тогда gcd(a,2^64)=gcd(a,2^64-a). Ну а 2^64-a=~0ull-a+1.
unsigned long long gcd (unsigned long long a,unsigned long long b,unsigned long long & x,unsigned long long & y)
{
if (a == 0)
{
x = 0; y = 1;
return b;
}
unsigned long long x1, y1;
unsigned long longd = gcd (b%a, a, x1, y1);
x = y1 - (b / a) * x1;
y = x1;
return d;
}
(b/a)*x1 -> zdes perepolnenii nebudet?
Мне кажется, проще тогда уже так:
gcd(a,p)=1, где p=2^64.
Тогда
a^(phi(p)) = 1 (mod p)
phi(p)=2^64-2^63=2^63=b
a^b = 1 (mod p)
a^(b-1) = a^(-1) (mod p)
Kadr , thanks!!!!!! Ya ponyal!!!!
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Algo » HASH