Kochanského násobení - Kochanski multiplication

Kochanského násobení je algoritmus, který umožňuje efektivní provádění modulární aritmetiky (násobení nebo na ní založené operace, jako je umocňování ), když je modul velký (obvykle několik stovek bitů). To má zvláštní uplatnění v teorii čísel a v kryptografii : například v kryptosystému RSA a výměně klíčů Diffie – Hellman .

Nejběžnějším způsobem implementace multi-násobení velkého celého čísla v hardwaru je vyjádření multiplikátoru v binárním formátu a výčet jeho bitů, jeden po druhém, počínaje nejvýznamnějším bitem, provedení následujících operací na akumulátoru :

  1. Zdvojnásobte obsah akumulátoru (pokud akumulátor ukládá čísla v binární podobě, jak je tomu obvykle, jedná se o jednoduchý „posun doleva“, který nevyžaduje žádný skutečný výpočet).
  2. Pokud je aktuální bit multiplikátoru 1, přidejte multiplikátor do akumulátoru; pokud je 0, nedělejte nic.

Pro n -bitový multiplikátor to bude trvat n hodinových cyklů (kde každý cyklus provede buď posun nebo posun a přidání).

Chcete-li to převést na algoritmus pro modulární násobení, s modulem r , je nutné v každé fázi podmíněně odečíst r :

  1. Zdvojnásobte obsah akumulátoru.
  2. Pokud je výsledek větší nebo roven r , odečtěte r . (Ekvivalentně odečtěte r z akumulátoru a výsledek uložte zpět do akumulátoru, jen pokud je nezáporný).
  3. Pokud je aktuální bit multiplikátoru 1, přidejte multiplikátor do akumulátoru; pokud je 0, nedělejte nic.
  4. Pokud je výsledek sčítání větší nebo roven r , odečtěte r . Pokud k žádnému přidání nedošlo, nedělejte nic.

Tento algoritmus funguje. Je však kriticky závislá na rychlosti přidávání.

Přidání dlouhých celých čísel trpí problémem, který nese, musí být šířeno zprava doleva a konečný výsledek není znám, dokud nebude tento proces dokončen. Šíření přenosu lze zrychlit pomocí logiky dopředného výhledu, ale díky tomu je přidávání mnohem pomalejší, než je třeba (u 512bitového přidávání je přidávání s hledáním dopředu 32krát pomalejší než přidávání bez přenášení vůbec) .

Nemodulární násobení může využívat sčítání carry-save , které šetří čas ukládáním carry z každé pozice číslic a jejich pozdějším použitím: například výpočtem 111111111111 + 000000000010 jako 1111111111212 místo čekání na šíření carry přes celou číslo, aby se získala skutečná binární hodnota 1000000000001. Toto konečné šíření je ještě nutné provést, aby se získal binární výsledek, ale toto je třeba provést pouze jednou na samém konci násobení.

Bohužel výše popsaná modulární metoda násobení potřebuje znát velikost akumulované hodnoty v každém kroku, aby se mohla rozhodnout, zda odečíst r : například pokud potřebuje vědět, zda je hodnota v akumulátoru větší než 1000000000000, přenos -uložit reprezentaci 111111111121 je k ničemu a je třeba ji převést na její skutečnou binární hodnotu, aby bylo možné provést srovnání.

Zdá se tedy, že lze mít buď rychlost carry-save nebo modulární násobení, ale ne obojí.

Nástin algoritmu

Princip Kochanského algoritmu spočívá v odhadu, zda má být r odečteno, na základě několika nejvýznamnějších bitů hodnoty carry-save v akumulátoru. Takový odhad bude někdy nesprávný, protože neexistuje způsob, jak zjistit, zda latence nese méně významné číslice (které nebyly zkoumány), nemusí vést k neplatnosti výsledku srovnání. Tím pádem:

  • Odečtení možná nebylo provedeno, když bylo požadováno. V takovém případě je výsledek v akumulátoru větší než r (i když to algoritmus ještě neví), a tak po dalším posunu doleva bude nutné z akumulátoru odečíst 2 r .
  • Odečtení mohlo být provedeno, když jeden nebyl vyžadován. V takovém případě je výsledek v akumulátoru menší než 0 (i když to algoritmus ještě neví), a tak po dalším posunu doleva bude třeba do akumulátoru přidat r nebo dokonce 2 r, aby byl pozitivní znovu.

To, co se děje, je v podstatě závod mezi chybami, které vyplývají z nesprávných odhadů, které se zdvojnásobí s každým posunem doleva, a opravami provedenými přidáním nebo odečtením násobků r na základě odhadu, jaké chyby mohou být.

Ukazuje se, že zkoumání nejvýznamnějších 4 bitů akumulátoru je dostatečné k udržení chyb v mezích a že jediné hodnoty, které je třeba přidat do akumulátoru, jsou -2 r , - r , 0, + r a +2 r , což vše lze okamžitě generovat jednoduchými posuny a negacemi.

Na konci úplného modulárního násobení musí být vyhodnocen skutečný binární výsledek operace a je možné, že bude třeba další sčítání nebo odčítání r jako výsledek nést, které jsou poté objeveny; ale náklady na tento další krok jsou malé, pokud jsou amortizovány během stovek kroků posunu a přidání, které dominují celkovým nákladům na násobení.

Alternativy

Brickell publikoval podobný algoritmus, který vyžaduje větší složitost elektroniky pro každou číslici akumulátoru.

Montgomeryho násobení je alternativní algoritmus, který zpracovává multiplikátor „zpět“ (nejméně platná číslice jako první) a používá nejméně platnou číslici akumulátoru k řízení, zda by měl nebo neměl být modul přidán / odečten. Tím se zabrání potřebě šíření nosítek. Algoritmus je však nepraktický pro jednoduché modulární multiplikace, protože je třeba provést dva nebo tři další kroky Montgomeryho, aby se operandy před zpracováním převedly do speciální formy a na konci se výsledek převedl zpět do konvenční binární podoby.

Reference

  • Vytvoření čipu FAP4 Neformální vysvětlení a motivace algoritmu s podrobnostmi o skutečné implementaci hardwaru.