Нестандартное умножение по модулю - Компьютерный форум OSzone.net

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)

- Программирование и базы данных (http://forum.oszone.net/forumdisplay.php?f=21)

- - Нестандартное умножение по модулю (http://forum.oszone.net/showthread.php?t=245170)

Нестандартное умножение по модулю

Часть реализации шифра.

В общем ТЗ: умножение по модулю 2^16+1 = 65537, причем вместо числа, равного нулю, используется 2^16.
Constants.decip_mod = 65537;
Constants.fyui = 65536;
Constants.one = 65535;

Как сделано в одном источнике (я не могу понять что к чему тут, разъясните пожалуйста полностью):

Код:

long p;

long q;

                if(a==0) p = Constants.decip_mod - b;

                else

                    if(b==0) p=Constants.decip_mod - a;

                    else {

                        q = a * b;

                        p = (q & Constants.one) - (q>>16); // & = битовое логическое умножение  

                        if(p<=0) p = p + Constants.decip_mod;

                         }

        return (long)(p&Constants.one);

Как делаю я:

Код:

if (a == 0) a = Constants.fuyi;

if (b == 0) b = Constants.fuyi;

p = ((a * b) % (Constants.decip_mod));

return p;

Что я делаю не так? (при использовании моего способа вся программа в итоге выдаёт неверный результат, при использовании первого - верный, НО на тестовых (написаны в описании алгоритма шифра) значениях a=2^16 и b=2^15 мой способ работает верно, впрочем как и первый способ - оба выдают 2^15+1).

И ещё: в одном месте находил этот исходник с парой комментариев, один из них был как раз к этой функции:
multiplication using the Low-High algorithm.

Для теста сделал

Код:

for (int i = 0; i < 999; i++)

{

for (int j = 0; j < 999; j++)

{

if (mymul(i,j)!=mul(i,j)) Console.WriteLine("i: {0}, j: {1}, mymul: {2}, mul: {3}", i,j,mymul(i,j), mul(i,j));

}

}

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

multiplication of integers modulo 2^16+1 where the subblock is treated as the usual radix-two representation of an integer except that the all-zero subblock is treated as representing 2^16.

Видимо имелось в виду, что ПОСЛЕ умножения и взятия по модулю возвращаемое значение p, если оно равно 2^16, надо перевести в 0 (т.е. в обратную сторону уже).

Теперь работает. Ох уж эти америкосы, так сложно пообширней написать чтобы понятно было.

Код:

   if (a == 0) a_ = Constants.fuyi; else a_ = a;

    if (b == 0) b_ = Constants.fuyi; else b_ = b;

    p = ((a_ * b_) % (Constants.decip_mod));

    if (p == Constants.fuyi) p = 0;

    return p;

Вопрос: Какими судьбами ты с таким алгоритмом столкнулся? Не для реализации алгоритма IDEA случайно?