Algoritmus Tonelli – Shanks - Tonelli–Shanks algorithm
The Tonelli – Shanks algoritmus (Shanks je označován jako RESSOL algoritmus) se používá v modulární aritmetika vyřešit r ve shodě formy r2 ≡ n (mod p), kde p je primární: to znamená najít druhou odmocninu z n modulo p.
Tonelli – Shanks nelze použít pro složené moduly: nalezení druhých čísel modulo složených čísel je výpočetní problém ekvivalentní celočíselná faktorizace.[1]
Ekvivalentní, ale o něco redundantnější verzi tohoto algoritmu vyvinulaAlberto Tonelli[2][3]v roce 1891. Zde diskutovaná verze byla vyvinuta nezávisle uživatelem Daniel Shanks v roce 1973, který vysvětlil:
Moje nedochvilnost učit se o těchto historických odkazech byla, protože jsem půjčil 1. svazek Dickson Dějiny příteli a nikdy nebyl vrácen.[4]
Podle Dicksona,[3] Tonelliho algoritmus může mít druhou odmocninu X modulo prime power pλ kromě prvočísel.
Základní myšlenky
Vzhledem k nenulové a liché prvočíslo , Eulerovo kritérium říká nám to má druhou odmocninu (tj. je kvadratický zbytek ) právě tehdy, když:
- .
Naproti tomu, pokud číslo nemá druhou odmocninu (není zbytkem), Eulerovo kritérium nám říká, že:
- .
Není těžké takové najít , protože polovina celých čísel mezi 1 a mít tuto vlastnost. Předpokládáme tedy, že k takovému zbytku máme přístup.
Tím, že (normálně) dělíme 2 opakovaně, můžeme psát tak jako , kde je zvláštní. Všimněte si, že pokud to zkusíme
- ,
pak . Li , pak je druhá odmocnina z . Jinak pro , my máme a uspokojující:
- ; a
- je -tý kořen 1 (protože ).
Pokud je na výběr a pro konkrétní splňující výše uvedené (kde není druhá odmocnina z ), můžeme snadno vypočítat další a pro takže výše uvedené vztahy platí, pak to můžeme opakovat, dokud se stává -tý kořen 1, tj. . V tu chvíli je druhá odmocnina z .
Můžeme zkontrolovat, zda je -tý kořen z 1 tím, že jej srovnáme krát a zkontrolujte, zda je to 1. Pokud ano, pak nemusíme dělat nic, stejný výběr a funguje. Ale pokud tomu tak není, musí být -1 (protože druhou mocninou dává 1, a tam mohou být jen dvě odmocniny 1 a -1 z 1 modulo ).
Chcete-li najít nový pár a , můžeme se množit faktorem , být odhodlán. Pak musí být vynásoben faktorem nechat si . Musíme tedy najít faktor aby je -tý kořen 1, nebo ekvivalentně je -tý kořen -1.
Trik je v tom využít známé zbytky. Eulerovo kritérium se vztahovalo na to ukazuje výše je -tý kořen -1. Takže čtvercem opakovaně máme přístup k posloupnosti -tý kořen -1. Můžeme vybrat ten správný, který bude sloužit jako . S trochou variabilní údržby a triviální komprese případů se níže uvedený algoritmus přirozeně vynořuje.
Algoritmus
Operace a srovnání prvků multiplikativní skupina celých čísel modulo str jsou implicitně mod p.
Vstupy:
- pprvočíslo
- n, prvek taková, aby řešení shody r2 = n existovat; když je to tak, říkáme to n je kvadratický zbytek mod p.
Výstupy:
- r v takhle r2 = n
Algoritmus:
- Vyloučením sil 2, najděte Q a S takhle s Q zvláštní
- Vyhledejte a z v což je kvadratický zbytek
- Polovina prvků v sadě budou kvadratické nezbytky
- Uchazeči mohou být testováni Eulerovo kritérium nebo vyhledáním Jacobi symbol
- Nechat
- Smyčka:
- Li t = 0, návrat r = 0
- Li t = 1, návrat r = R
- V opačném případě použijte opakované kvadratury k nalezení nejméně i, 0 < i < M, takový, že
- Nechat a nastavit
Jakmile vyřešíte shodu s r druhým řešením je . Pokud nejméně i takhle je M, potom neexistuje žádné řešení kongruence, tzn n není kvadratický zbytek.
To je nejužitečnější, když p ≡ 1 (mod 4).
Pro prvočísla taková p ≡ 3 (mod 4), tento problém má možná řešení . Pokud tyto uspokojí , jsou to jediné řešení. Pokud ne, , n je kvadratický ne-zbytek a neexistují žádná řešení.
Důkaz
Můžeme ukázat, že na začátku každé iterace smyčky následující smyčkové invarianty držet:
Zpočátku:
- (od té doby z je kvadratickým neresidem podle Eulerova kritéria)
- (od té doby n je kvadratický zbytek)
Při každé iteraci s M ' , C' , t ' , R ' nahrazující nové hodnoty M, C, t, R:
- protože to máme ale (i je ta nejmenší hodnota )
Z a test proti t = 1 na začátku smyčky, vidíme, že vždy najdeme i v 0 < i < M takhle . M je v každé iteraci přísně menší, a proto je zaručeno, že se algoritmus zastaví. Když jsme narazili na podmínku t = 1 a halt, poslední invariant smyčky to znamená R2 = n.
Řád t
Můžeme střídavě vyjádřit smyčkové invarianty pomocí objednat prvků:
- jako dříve
Každý krok algoritmu se pohybuje t do menší podskupiny měřením přesného pořadí t a vynásobením prvkem stejného řádu.
Příklad
Řešení shody r2 ≡ 5 (mod 41). 41 je podle potřeby prime a 41 ≡ 1 (mod 4). 5 je podle Eulerova kritéria kvadratický zbytek: (stejně jako dříve, operace v jsou implicitně mod 41).
- tak ,
- Najděte hodnotu pro z:
- , takže 2 je podle Eulerova kritéria kvadratický zbytek.
- , takže 3 je kvadratický nonresidue: set
- Soubor
- Smyčka:
- První iterace:
- , takže ještě neskončíme
- , tak
- Druhá iterace:
- , takže stále ještě neskončíme
- tak
- Třetí iterace:
- a jsme hotovi; vrátit se
- První iterace:
Opravdu, 282 ≡ 5 (mod 41) a (-28)2 ≡ 132 ≡ 5 (mod 41). Algoritmus tedy přináší dvě řešení naší kongruence.
Rychlost algoritmu
Algoritmus Tonelli – Shanks vyžaduje (v průměru přes všechny možné vstupy (kvadratické zbytky a kvadratické zbytky))
modulární multiplikace, kde je počet číslic v binární reprezentaci a je počet jednotek v binární reprezentaci . Pokud je požadovaná kvadratická rezidence je nalezen kontrolou, zda je náhodně odebrané číslo je kvadratickým neresidem, vyžaduje (v průměru) výpočty symbolu Legendre.[5] Průměr dvou výpočtů symbolu Legendre je vysvětlen následovně: je kvadratický zbytek s náhodou , který je menší než ale , takže budeme muset průměrně zkontrolovat, zda a je kvadratický zbytek dvakrát.
To v podstatě ukazuje, že algoritmus Tonelli – Shanks funguje velmi dobře, pokud je modul je náhodný, tedy pokud není nijak zvlášť velký, pokud jde o počet číslic v binární reprezentaci . Jak bylo napsáno výše, Cipollov algoritmus funguje lépe než Tonelli – Shanks, pokud (a pouze pokud) Pokud však někdo místo toho použije Sutherlandův algoritmus k provedení výpočtu diskrétního logaritmu v podskupině 2-Sylow , jeden může nahradit s výrazem, který je asymptoticky ohraničen .[6] Výslovně jeden počítá takhle a pak splňuje (Všimněte si, že je násobkem 2, protože je kvadratický zbytek).
Algoritmus vyžaduje, abychom našli kvadratický zbytek . Neexistuje žádný známý deterministický algoritmus, který běží v polynomiálním čase pro nalezení takového . Pokud však zobecněná Riemannova hypotéza je pravda, existuje kvadratická rezidua ,[7] což umožňuje zkontrolovat všechny až do tohoto limitu a najít vhodný v rámci polynomiální čas. Pamatujte však, že se jedná o nejhorší scénář; obecně, se nachází v průměru ve 2 studiích, jak je uvedeno výše.
Použití
Algoritmus Tonelli – Shanks lze (přirozeně) použít pro jakýkoli proces, ve kterém jsou nezbytné odmocniny modulo prime. Lze jej například použít k vyhledání bodů na eliptické křivky. To je také užitečné pro výpočty v Rabinův kryptosystém.
Zobecnění
Tonelli – Shanks lze zobecnit na jakoukoli cyklickou skupinu (místo ) a do kth kořeny pro libovolné celé číslo k, zejména s ohledem na kth kořen prvku a konečné pole.[8]
Pokud musí být ve stejné cyklické skupině provedeno mnoho odmocnin a S není příliš velká, lze předem připravit tabulku odmocnin prvků 2-mocninového řádu a algoritmus zjednodušit a zrychlit následujícím způsobem.
- Rozdělte síly 2 z p - 1, definování Q a S tak jako: s Q zvláštní.
- Nechat
- Nalézt ze stolu tak, že a nastavit
- vrátit se R.
Tonelliho algoritmus bude fungovat na módu p ^ k
Podle Dicksonovy „Teorie čísel“[3]
Dicksonova reference ukazuje následující vzorec pro druhou odmocninu z .
- když nebo (pro tuto rovnici musí být 2) a takhle
- pro pak
- kde
- pro pak
Všímat si toho a to si všímat pak
Vezmeme si další příklad: a
Dickson také připisuje Tonelli následující rovnici:
- kde a ;
Použitím a pomocí modulu následuje matematika:
Nejprve najděte modulární druhou odmocninu což lze provést běžným Tonelliho algoritmem:
- a tudíž
A použití Tonelliho rovnice (viz výše):
Dicksonův odkaz[3] jasně ukazuje, že Tonelliho algoritmus pracuje na modulech .
Poznámky
- ^ Oded Goldreich, Výpočetní složitost: koncepční perspektiva, Cambridge University Press, 2008, s. 588.
- ^ Volker Diekert; Manfred Kufleitner; Gerhard Rosenberger; Ulrich Hertrampf (24. května 2016). Diskrétní algebraické metody: aritmetika, kryptografie, automaty a skupiny. De Gruyter. str. 163–165. ISBN 978-3-11-041632-9.
- ^ A b C d E Leonard Eugene Dickson (1919). Dějiny teorie čísel. 1. str.215 –216.
- ^ Daniel Shanks. Pět číselně teoretických algoritmů. Proceedings of the Second Manitoba Conference on Numerical Mathematics. Str. 51–70. 1973.
- ^ Gonzalo Tornaria - odmocniny modulo p, strana 2 https://doi.org/10.1007%2F3-540-45995-2_38
- ^ Sutherland, Andrew V. (2011), „Výpočet struktury a diskrétní logaritmy v konečných abelianských p-skupinách“, Matematika výpočtu, 80: 477–500, arXiv:0809.3413, doi:10.1090 / s0025-5718-10-02356-2
- ^ Bach, Eric (1990), „Explicit bounds for primality testing and related problems“, Matematika výpočtu, 55 (191): 355–380, doi:10.2307/2008811, JSTOR 2008811
- ^ Adleman, L. M., K. Manders a G. Miller: 1977, `O zakořenění v konečných polích '. In: 18. IEEE Symposium on Foundations of Computer Science. 175-177
- ^ „Accademia nazionale dei Lincei, Řím. Rendiconti, (5), 1, 1892, 116–120.“
Reference
- Ivan Niven; Herbert S. Zuckerman; Hugh L. Montgomery (1991). Úvod do teorie čísel (5. vydání). Wiley. str.110–115. ISBN 0-471-62546-9.
- Daniel Shanks. Teoretické algoritmy pěti čísel. Proceedings of the Second Manitoba Conference on Numerical Mathematics. Str. 51–70. 1973.
- Alberto Tonelli, Bemerkung über die Auflösung quadratischer Congruenzen. Nachrichten von der Königlichen Gesellschaft der Wissenschaften und der Georg-Augusts-Universität zu Göttingen. Str. 344–346. 1891. [1]
- Gagan Tara Nanda - Matematika 115: Algoritmus RESSOL [2]
- Gonzalo Tornaria [3]