Помогите реализовать деление больших чисел

[Perfilev]

Нужно посчитать

u=s^2 mod N

где
N - 64-битное число
s - 64-битное (т.е. s^2 уже 128 бит)

Как это реализовать на асме? Помогите пожалуйста, очень нужно!!!

[Andrewpg]

Способ 1 (самый простой): использовать мат. сопроцессор.
Способ 2 (чуть сложнее): вспомнить школьный курс математики (а именно: алгорить умножения "столбиком" и деления "углом"), и закодировать его на асме.
Способ 3: <надо вспомнить курс лекций на случай, если 1 и 2 не помогут>

[Perfilev]

А можно чуточку поподробнее?
Особенно про 1-й способ?

[lak_b]

юзай
ya.ru: длинная арифметитка

[XPEHOMETP]

А переход на 128-битные числа нужен принципиально? Если нет, почему бы не обойти это дело таким трюком:

a = s\N (результат целочисленного деления, пардон за Basic)
b = s mod N
s = a*N + b
Тогда:
s^2 = a^2*N^2 + 2*a*b*N + b^2
В результате получаем:
u = s^2 mod N = b^2 mod N = (s mod N)^2 mod N

Разве не так?

[crawler]

Никто не гарантирует что (s mod N) меньше 31 бита

[Ghost]

Абсолютно верно. Поскольку приведение по модулю N является гомоморфным отображением из кольца целых в кольцо целых о модулю N, верны следующие утверждения:
(A + B) mod N = [(A mod N) + (B mod N)] mod N
(A - B) mod N = [(A mod N) - (B mod N)] mod N
(A * B) mod N = [(A mod N) * (B mod N)] mod N
Последнее равенство как раз нужно. Это элементы модулярной арифметики, использующейся в некоторых асимметричных криптосистемах (RSA, системы Полига-Хеллмана и Эль-Гамаля). Я по этому диплом писал...

[Perfilev]

я думаю решить эту задачу при помощи sse, там xmm регистры 128-битные, только я не знаю как их использовать, т.к. при компиляции masm-ом выдаются ошибки:
Assembling: _gendll.asm
_gendll.asm(118) : error A2085: instruction or register not accepted in current CPU mode
_gendll.asm(120) : error A2006: undefined symbol : xmm0

118: movaps xmm0, eax
120: or xmm0, 10000000000000000000000000000000b

Пробовал подключать iaxmm.inc - ещё больше ошибок.
В чем проблема?

[XPEHOMETP]

А если подсмотреть, как такие вычисления компилятор делает? И подправить при необходимости? Могу вечером проделать на Фортране с g95, только он выдает ассемблер в стиле ATT. Обычный асм выдает Salford FTN95, но он пишет много лишнего: присоединение рантайм-модулей и прочее.

[Perfilev]

боюсь, это слишком сложно для меня.
могу скинуть исходники, посмотреть, в чём дело.

[XPEHOMETP]

Виноват, наобещал лишнего! Нету у меня компиляторов, которые с такими большими числами работают.

[Willow]

Сообщение от Andy1

я думаю решить эту задачу при помощи sse, там xmm регистры 128-битные, только я не знаю как их использовать, т.к. при компиляции masm-ом выдаются ошибки:
Assembling: _gendll.asm
_gendll.asm(118) : error A2085: instruction or register not accepted in current CPU mode
_gendll.asm(120) : error A2006: undefined symbol : xmm0

118: movaps xmm0, eax
120: or xmm0, 10000000000000000000000000000000b

Пробовал подключать iaxmm.inc - ещё больше ошибок.
В чем проблема?

Ну начнем стого, что строка 118 ошибочная. (Левый операнд 128 бит, а правый только 32)

МАСМ я давно не юзал, так что сказать конкретно тяжело, но должна быть деректива которая разрешит юзать ССЕ. Но могу сказать что Делфа и Вижуалы уже года три как позволяют на асме вставлять такие инструкции (7 Делфа и 2003 Вижуалы точно, предки вроде тоже).

А вообще есть такой замечательный ассемблер как FASM (http://flatassembler.net/)

[GOre01]

Не совсем то, но вдруг поможет. Рассматриваются операции для работы с большими числами. Принципы работы с ними и т.п. Но... применительно к С++. Может окажется полезным.