Algebraisk gruppfaktoriseringsalgoritm

Algebraisk-gruppfaktoriseringsalgoritmer är algoritmer för att faktorisera ett heltal N genom att arbeta i en algebraisk gruppdefinierad modulo N vars gruppstruktur är den direkta summan av de 'reducerade grupperna' som erhålls genom att utföra ekvationerna som definierar grupparitmetiska modulo de okända primtalsfaktorerna p ₁ , p ₂ , ... Enligt den kinesiska restsatsen motsvarar aritmetisk modulo N aritmetik i alla de reducerade grupperna samtidigt.

Syftet är att hitta ett element som inte är identiteten för gruppen modulo N utan är identiteten modulo en av faktorerna, så en metod för att känna igen sådana ensidiga identiteter krävs. I allmänhet hittar man dem genom att utföra operationer som flyttar runt element och lämnar identiteterna i de reducerade grupperna oförändrade. När algoritmen väl hittar en ensidig identitet kommer alla framtida termer också att vara ensidiga identiteter, så det räcker med att kontrollera med jämna mellanrum.

Beräkningen fortsätter genom att välja ett godtyckligt element x i gruppen modulo N och beräkna en stor och jämn multipel Axe av den; om ordningen för minst en men inte alla reducerade grupper är en divisor av A, ger detta en faktorisering. Det behöver inte vara en primfaktorisering, eftersom elementet kan vara en identitet i mer än en av de reducerade grupperna.

I allmänhet tas A som en produkt av primtal under någon gräns K, och Ax beräknas genom successiv multiplikation av x med dessa primtal; efter varje multiplikation, eller varannan multiplikation, görs kontrollen för en ensidig identitet.

Tvåstegsproceduren

Det är ofta möjligt att multiplicera ett gruppelement med flera små heltal snabbare än med deras produkt, vanligtvis genom skillnadsbaserade metoder; man beräknar skillnader mellan på varandra följande primtal och adderar i följd med $d_{i}r$ . Detta innebär att en tvåstegsprocedur blir vettig, först beräkna Ax genom att multiplicera x med alla primtal under en gräns B1, och sedan undersöka p Ax för alla primtal mellan B1 och en större gräns B2.

Metoder som motsvarar särskilda algebraiska grupper

Om den algebraiska gruppen är den multiplikativa gruppen mod N , identifieras de ensidiga identiteterna genom att beräkna största gemensamma divisorer med N , och resultatet är p − 1 metoden .

Om den algebraiska gruppen är den multiplikativa gruppen av en kvadratisk förlängning av N , blir resultatet p +1-metoden ; beräkningen involverar talpar modulo N . Det är inte möjligt att avgöra om $\mathbb {Z} /N\mathbb {Z} [{\sqrt {t}}]$ faktiskt är en kvadratisk förlängning av ${ \displaystyle \mathbb {Z} /N\mathbb {Z} }$ utan att känna till faktoriseringen av N . Detta kräver att man vet om t är en kvadratisk rest modulo N , och det finns inga kända metoder för att göra detta utan kunskap om faktoriseringen. Men förutsatt att N inte har ett särskilt stort antal faktorer, i vilket fall en annan metod bör användas först, kommer att plocka slumpmässigt t (eller snarare att plocka A med t = A ² − 4) av misstag träffa en kvadratisk icke-rest ganska snabbt . Om t är en kvadratisk rest, degenererar p+1-metoden till en långsammare form av p − 1-metoden.

Om den algebraiska gruppen är en elliptisk kurva , kan de ensidiga identiteterna kännas igen genom misslyckande av inversion i den elliptiska kurvan punkt additionsproceduren, och resultatet är den elliptiska kurva metoden ; Hasses teorem säger att antalet punkter på en elliptisk kurva modulo p alltid är inom $2{\sqrt {p}}$ av p .

Alla tre ovanstående algebraiska grupperna används av GMP-ECM- paketet, som inkluderar effektiva implementeringar av tvåstegsproceduren, och en implementering av PRAC-gruppexponentieringsalgoritmen som är ganska effektivare än den vanliga binära exponentieringsmetoden .

Användningen av andra algebraiska grupper - högre ordningens förlängningar av N eller grupper som motsvarar algebraiska kurvor av högre släkte - föreslås ibland, men nästan alltid opraktiskt. Dessa metoder slutar med jämnhetsbegränsningar för nummer i storleksordningen p ^d för vissa d > 1, som är mycket mindre sannolikt att vara jämna än nummer i storleksordningen p .