Klassgruppen Introduktion, faktorisering och implementation

Sammanfattning: Givet ett heltal n så utforskar denna text olika sätt att hitta ns faktorer, med fokus på Shanks Klassgruppmetod, även om korta beskrivningar av Pollards p -1- och rho-algoritmer ges. Klassgruppen introduceras som en mängd av ekvivalensklasser av fraktionsideal i imaginära kvadratiska talkroppar, varpå en isomorfi till en mängd av ekvivalensklasser av binära kvadratiska former av given diskriminant D ges. Denna isomorfi ger upphov till en abstrakt gruppoperation under vilken element av ordning 2 svarar mot en faktorisering av n. Shanks Klassgruppmetod beskriver hur en kan finna element av ordning 2 med tidskomplexitet O(|D|^(1/4)), vari det största problemet ligger i att hitta klassgruppens exponent. Detta görs med hjälp av Shanks’ Baby-Steps-Giant-Steps-metod, vilken finner exponenten av ändliga grupper. Implementationer i Python 3 återfinns i appendix.