Faktorbas

Inom algoritmisk talteori används faktorbasen vanligen i algoritmer som inbegriper omfattande sållning av potentiella faktorer.

Användning

Faktorbasen är en relativt liten mängd av primtalen P. Säg att vi ska faktorisera ett heltal n. Vi genererar, på något sätt, ett stort antal kongruenta heltalspar (x, y) för vilka $x\neq y$ och $\textstyle x\equiv y{\pmod {n}}$ så att x, y fullständigt kan faktoriseras över den valda faktorbasen, det vill säga, de är p-släta för det största primtalet p i P.

Vi hittar en delmängd S av heltalsparet sådana att $\textstyle \prod _{}x{\hbox{, }}(x{\hbox{ in }}S)$ och $\textstyle \prod _{}y{\hbox{, }}(y{\hbox{ in }}S)$ båda är perfekta kvadrater. Över vår faktorbas reduceras det genom att addera exponenter för deras primtalsfaktorer, modulo 2, då vi kan urskilja kvadrater från icke-kvadrater helt enkelt genom att kontrollera paritet av exponenter.

Vi kan representera varje x och y som en vektor av en matris med 0 och 1 poster för paritet av varje exponent. Det formulerar väsentligen problemet i ett linjärt ekvationssystem, som kan lösas med hjälp av ett flertal metoder som till exempel Gausselimination. I praktiken kan avancerade metoder som Block-Lanczos-algoritmen användas för att dra nytta av vissa egenskaper hos systemet.

När en sådan delmängd hittas, har vi funnit i huvudsak en kongruens av kvadrater modulo n och kan försöka faktorisera n. Denna kongruens kan trivialt generera $\textstyle n=1\cdot n$; i det här fallet försöker vi hitta en annan lämplig delmängd. Om ingen sådan delmängd hittas, kan vi söka efter fler (x, y)-par, eller försöka igen med en annan faktorbas.

Algoritmer

Faktorbaser används i exempelvis Dixons faktorisering, kvadratiska såll och talsåll. Skillnaden mellan dessa algoritmer är huvudsakligen de metoder som används för att generera (x, y)-kandidater.

Källor

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia, Factor base, 9 november 2013.