Faktorová základna - Factor base
v výpočetní teorie čísel, a faktorová základna je malá sada prvočísel běžně používaná jako matematický nástroj v algoritmech zahrnujících rozsáhlé prosévání pro potenciální faktory daného celého čísla.
Využití v factoringových algoritmech
Faktorová základna je relativně malá soubor výrazných prvočísla P, někdy společně s -1.[1] Řekněme, že chceme faktorizovat celé číslo n. Generujeme nějakým způsobem velké množství celočíselných párů (X, y) pro který , , a mohou být zcela faktorizovány přes vybranou faktorovou základnu - to znamená, že všechny jejich hlavní faktory jsou v P.
V praxi několik celých čísel X jsou nalezeny takové, že má všechny své hlavní faktory ve předem zvolené faktorové základně. Zastupujeme každého výraz jako vektor a matice přičemž celočíselné položky jsou exponenty faktorů v základně faktorů. Lineární kombinace řádků odpovídá znásobení těchto výrazů. Relace lineární závislosti mod 2 mezi řádky vede k požadované kongruenci .[2] Tím se v zásadě přeformuluje problém na soustava lineárních rovnic, které lze vyřešit pomocí mnoha metod, jako je Gaussova eliminace; v praxi pokročilé metody jako blokovat Lanczosův algoritmus jsou využívány, které využívají určité vlastnosti systému.
Tato shoda může generovat triviální ; v tomto případě se pokusíme najít jinou vhodnou shodu. Pokud opakované pokusy o faktor selžou, můžeme to zkusit znovu s použitím jiné faktorové základny.
Algoritmy
Faktorové báze se používají například v Dixonova faktorizace, kvadratické síto a číslo pole síto. Rozdíl mezi těmito algoritmy je v podstatě v metodách použitých k generování (X, y) kandidáti. Faktorové báze se také používají v Algoritmus indexového počtu pro výpočet diskrétních logaritmů.[3]
Reference
- ^ Koblitz, Neal (1987), Kurz teorie čísel a kryptografieSpringer-Verlag, str. 133, ISBN 0-387-96576-9
- ^ Trappe, Wade; Washington, Lawrence C. (2006), Úvod do kryptografie s teorií kódování (2. vyd.), Prentice-Hall, str. 185, ISBN 978-0-13-186239-5
- ^ Stinson, Douglas R. (1995), Kryptografie / teorie a praxe, CRC Press, str. 171, ISBN 0-8493-8521-0