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  och  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  och  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 ; 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 -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 -kandidater.

Källor 
 

Algoritmer för primtalsfaktorisering
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 och 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 och båda är perfekta kvadrater . Över vår faktorbas reduceras det genom att addera exponenter för deras primtalsfaktorer , modulo 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 medochposter 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 ; 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 -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 -kandidater . Källor Algoritmer för primtalsfaktorisering