Всем доброго времени суток! Реализую RSA в своем приложении, но уперся в проблему с большими числами. Интересует такой вопрос: как проц умножает двоичные целые числа без знака, сам принцип этого процесса и сколько тактов уходит на выполнение инструкции mul? Думаю, что один. И еще: при умножении больших чисел в представлении цифра - dword, типа "eax пишем, edx "в уме"", все сводится, в конечном итоге, к сложению adc? Если можно, по-подробней этот алгоритм...
Hottabych этож элементарно На современных процессорах скорость умножения примерно соответствует скорости сложения, но чтобы увеличить скорость умножения больших чисел стоит воспользоваться следующим а) произведение (a*232+b)*(c*232+d)=a*c*264+(a*d+b*c)*232+b*d далее используйте команды MUL, ADD и ADC итого 4 операции умножения, 3 сложения и 2 сдвига б) можем воспользоваться алгоритмом Карацуба: 1. вычислим b*d – первое умножение 2. вычислим a*c – второе умножение 3. вычислим t=(a + b)*(c+d) – третье умножение X*Y=(a*232 + b)*(c*232 + d)=a*c*264 +(t– a*c– b*d)*232 + bd итого 3 умножения, 2 сложения, 2 вычитания, 2 сдвига в) алгоритм Тоома-Кука: 1. вычислим b*d – первое умножение 2. вычислим t0=(a + b)*(c + d) – второе умножение 3. вычислим t1=(b - a)*(d - с) – третье умножение Так как (t0 – t1)/2 = ad + bc и (t0 + t1)/2 - b*d = ac поэтому X*Y=(a*232 + b)*(c*232 + d)=((t0 + t1)/2 - b*d)264 +(t0 – t1)231 + b*d итого 3 умножения, 3 сложения, 3 сдвига, 2 вычитания г) Можно также использовать следующее свойство: X*Y=(X+Y)2/4 – (X–Y)2/4 = ((a + c)*232 + b + d)2/4 – ((a – c)*232 + b – d)2/4 По поводу "как проц умножает двоичные целые числа без знака, сам принцип этого процесса" поищите в Гугле "Алгоритм Booth", вот несколько ссылок Booth's multiplication algorithm Radix-4 Booth Encoding Radix-8 Booth Encoding
Mikl___, возможно я соглашусь с тобой, что это элементарно несколько позже Спасибо, буду разбирать...
Наверное ещё можно использовать SSE2 для ускорения. Вроде бы тогда получится параллельно умножить ac и bd. Правда есть шанс, что весь профит будет съеден затратами на перегруппировку в xmm регистрах... Кто-нибудь пробовал использовать xmm для умножения больших чисел? Есть выгода или смысла нет?
В смысле, что мне это даст, если длина a,b,c,d будет больше 32 бита? Ведь проц это не помножит... Как описать это алгоритмически?
Hottabych вспомните детсадовское умножение "в столбик"... только там было десятичное счисление, а здесь двоичное... или, лучше сказать, 32-битное
= 0x78 39 03 05 * 1 + 0x48 38 39 2A * (232) + 0x82 29 92 43 * (232)2 + .. Если битов 512 то будет у вас 16 разрядов (16 тридцатидвух-ичных цифр), каждый храните в двойном слове и перемножаете по алгоритмам, аналогичным тем что выше.
1) обычное умножение 512x512 бит можно представить как 4 умножения 256x256 бит, каждое из которых как 4 128x128 и т.д. до 32x32. Всего потребуется 256 умножений 32x32 2) для умножения двух 512-битных чисел X=a*2256+b, Y=c*2256+d по алгоритму Карацубы нужно выполнить ТРИ умножения 256x256: b*d, a*c, t=(a + b)*(c+d) Тогда X*Y = a*c*2512 +(t– a*c– b*d)*2256 + b*d Всего для умножения 512x512 нужно 81 умножение 32x32. CreatorCray написал Вообще рекомендую следующую литературу (если проблем с английским нету) Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone. Там в разделе Efficient Implementation есть эффективные алгоритмы для работы с длинной математикой такие как: Addition and subtraction, Multiplication, Squaring, Division, Montgomery reduction, Montgomery multiplication, Barrett reduction, Binary gcd algorithm, Lehmer’s gcd algorithm, Binary extended gcd algorithm, Chinese remainder theorem for integers, Garner’s algorithm, пачка разных exponentiation включая наиболее быстрый Montgomery exponentiation.
64-битное умножение, используя 32-разрядную арифметику (a0 + a1 *232)x(b0 + b1 *232)=a0b0 + (a0b1+a1b0) 232+a1b1 *264 результат: 4 умножения, 3 сложения, 2 сдвига 96-битное умножение, используя 32-разрядную арифметику (a0 + a1 *232 + a2 *264)x(b0 + b1*2³² + b2 *264)=a0b0 + a2b2 *2128 + (a0b1+a1b0)*2³² + (a2b1+a1b2)*296 + (a2b0 + a1b1 + a0b2)*264 результат: 9 умножений, 8 сложений, 4 сдвига 128-битное умножение, используя 32-разрядную арифметику (a0 + a1 *2³² + a2 *264 + a3 *296)x(b0 + b1 *2³² + b2 *264 + b3 *296)=a0b0 + a3b3 *2192 + (a0b1+a1b0) 2³²+(a2b3+a3b2)2160+(a2b0+a1b1+a0b2)264+(a1b3+a3b1+a2b2)2128+(a0b3+b0a3+a1b2+a2b1)296 результат: 16 умножений, 15 сложений, 6 сдвигов Не пугайтесь, до 512 бит мы не пойдем, тем более до 1024, тем не менее, налицо тенденция - от количества членов ai*2i*32 в многочлене равного n -- зависимость количества умножения n², сложений n² - 1, сдвигов 2n. По сравнению со сложением и сдвигом умножение достаточно медленная операция – постараемся свести количество умножений к минимуму. Так получилось, что a1b0+a0b1=a0b0+a1b1+(a0-a1)(b1-b0) сохраняем в переменных c0=a0b0 c1=a1b1 c2=a2b2 p=c0+c1+c2 тогда (a0 + a1 *2³² + a2 *264)x(b0 + b1 *2³² + b2 *264)=с0+c2*2128 + (p-c2+(a0-a1)(b1-b0)) 2³²+(p+(a0-a2)(b2-b0)) 264+(p-c0+(a1-a2)(b2-b1)) 296 количество умножений сократилось до 6 пусть c0=a0b0 c1=a1b1 c2=a2b2 с3=a3b3 p=c0+c1+c2+c3 тогда (a0 + a1 *2³² + a2 *264+a3296)x(b0 + b1 *2³² + b2*264+b3*296)=с0+c3*2192 + (p-c2-c3+(a0-a1)(b1-b0)) 2³²+(p-c0-c1+(a2-a3)(b3-b2)) 2160+(p-c3+(a0-a2)(b2-b0)) 264 +(p-c0+(a1-a3)(b3-b1)) 2128+(p+(a0-a3)(b3-b0)+(a1-a2)(b2-b1)) 296 количество умножений сократилось до 10. А как же умножение для 512 и 1024 бит? «Сама, сама, сама» (© «Вокзал для двоих»)
