есть некое число a
нужно найти b -  обратный к нему по модулю 2^32
т.е. такое чтобы a*b = 1 mod (2^32)

перебором медленно...
расширенный алгоритм евклида даже не знаю как применить... модуль специфический

, а не проще разделить 2^32 на некое число a и найти число b?  

эм, ну во первых если делить то делить 2^32 + 1,
во вторых мы не получим обратное как таковое.
получим тока частное и остаток.
а для частного не факт что будет при умножении давать 1 по модулю 2^32

Попробую сформулировать так, как я понял.

Для заданного a найти такое b, что (a*b) mod (2^32) = 1

Пусть (2^32) = a*k + m, причём m < a
Пусть b=k*x-y
Тогда a*b mod (2^32) = a*(k*x-y) mod (2^32) = (x*(a*k) - y*a) mod (2^32) = (x*m - y*a) mod (2^32) = 1
Осталось найти такую пару x и y, что x*m - y*a = 1
a и m нам известны, решение полученного уравнения в целых положительных x и y элементарно.

Можно доказать, что решение существует, если m>0 - само собой, это проверяется до начала расчёта.

ну на самом деле не так элементарно, это раз
во 2-х как реализовать это на asm-e

Элементарно, элементарно.


А тебе часом не в Центр помощи надо было?

turbanoff
a * b = n*2^32 + 1
b = (n*2^32 + 1)/a
  

алгоритм канечно хороший, но по сути тот же перебор, если взять к примеру
a = 0xefb1256d
то считает довольно долго...
а про 0xFE3ED1EF я вообще не говорю, ну это канечно я специально подобрал, но факт есть факт


Это сообщение отредактировал(а) turbanoff - 21.5.2009, 14:33

так, нашел в себе силы разобраться более или менее что тут написано.
тут такой вопрос: по ходу равенств a*k заменяется на m mod (2^32), 
что неверно, так как из

следует что a*k = -m mod (2^32)

и честно я не представляю как решается такие уравнения в целых числах

мб ссылочку подкините?

Это сообщение отредактировал(а) turbanoff - 21.5.2009, 15:51

Есть смысл продолжить разбираться имхо... 


Реши-ка: найти минимальную пару целых положительных x и y такую, что 5x-3y=1... неужели ЭТО может представлять проблему??? ясно, что это 2 и 3... 

ну понятно что в твоем описании ошибка, или как ты это можешь объяснить?
по поводу решения таких уравнений ничего кроме перебора в голову не приходит...

нет

какая-то бредоватая запись... mod - это операция, такая же как сложение или деление
а если имеется в виду a*k mod (2^32) = -m - так, во-первых, ЭТО не следует из моих записей, во-вторых, остаток от целочисленного деления не бывает отрицательным.

ааа... ну раз понятно, так о чём мы тогда толкуем-то...

вот замена, a*k на m.

Хочу немного разъяснить (или наоборот запутать) по поводу mod, имеется в виду во
1-х: необходимо нахождение обратного элемента в кольце Z(n), n в данном случае равно 2^32.
по сути это тоже самое что 


mod имеется в виду не просто операция взятие по модулю, а обозначение равенства этих элементов в нашем кольце.
то есть например 33 = 49 mod 16

и -m = 2^32 - m mod (2^32), в этом нет ничего
 

Это сообщение отредактировал(а) turbanoff - 21.5.2009, 18:20

А немного решить проблему хочешь? А я вот не хочу играть в телепата, даже немного. Мало ли что там имеется в виду... это тебе имеется, а я твою задачу ни сном ни духом. И догадываться больше не буду, надоело. Или все факты, или без меня.

ладно, забудь все что написал, вот задача:


как я понимаю основная твоя идея, взять во 1-х, найти 

k = (2^32) / a    (/ - целочисленное деление)
m = (2^32) - a*k            =>     a*k = (2^32) - m

далее b=k*x-y
Тогда a*b mod (2^32) = a*(k*x-y) mod (2^32) = (x*(a*k) - y*a) mod (2^32) = (x*((2^32) - m) - y*a) mod (2^32) = 1 

так как x*(2^32) = 0 mod (2^32)

то получаем:
-(x*m + y*a) mod (2^32) = 1

а вот дальше у меня даже нет идей что делать

PS. тема наз-ся "нахождение обратного элемента", я думаю всем понятно что обратный элемент находят не просто как-то так, а в соответствующем кольце, модуль для кольца я привел

Это сообщение отредактировал(а) turbanoff - 21.5.2009, 18:57