Heltallsfaktorisering

I tallteori består heltallsfaktorisering , primtallsfaktorisering, primtallsfaktorisering eller faktoriseringstre av å dekomponere et (ikke-primtall) sammensatt tall til ikke-trivielle divisorer , som når multiplisert gir det opprinnelige tallet.

Når tallene er veldig store, er ingen algoritme kjent som effektivt løser dette problemet; et nylig forsøk på å faktorisere et 200-sifret tall tok 18 måneder og brukte mer enn et halvt århundre med beregningstid. Den antatte vanskeligheten er kjernen i visse kryptografiske algoritmer , for eksempel RSA . Mange områder innen matematikk og informatikk , for eksempel algebraisk tallteori , elliptiske kurver eller kvanteberegning , er relatert til dette problemet.

Å dekomponere to like lange tall trenger ikke å ha samme komplikasjon. Foreløpig ( 2006 ) anses det at de vanskeligste tilfellene er de der faktorene er to primtall, valgt tilfeldig, av omtrent samme størrelse.

Primfaktorisering

Ved aritmetikkens grunnleggende teorem har hvert positivt heltall en unik dekomponering til primtall ( primtall ). De fleste av de elementære faktoriseringsalgoritmene har generelle formål, det vil si at de tillater å dekomponere et hvilket som helst oppgitt tall, og de skiller seg bare vesentlig i utførelsestid .

Heltallsfaktorisering i polynomtid

Problemet med å faktorisere heltall i polynomisk tid er ennå ikke løst i klassisk databehandling. Hvis noen lykkes, vil dette være av stor interesse innen kryptografi, siden mange kryptosystemer er avhengige av dets umulighet. I akademiske kretser vil eksistensen av et slikt fremskritt være gode nyheter; i andre kretser ville det være en stor hemmelighet, av åpenbare grunner. Det er imidlertid en algoritme for kvanteberegning , foreslått av Peter Shor , som er i stand til å finne faktoriseringen av et heltall til dets primfaktorer i polynomisk tid med begrenset feil, det vil si av klasse BQP . Denne oppdagelsen vekket interesse for kvantedatabehandling, og noen kvantedatamaskiner med noen få qubits , som er i stand til å bryte ned små tall, er allerede bygget. Det er å håpe at med de enorme fremskritt de siste årene, vil disse systemene snart være i stand til å bryte ned tall som er store nok til å bryte flere kryptografiske systemer som er avhengige av denne sammenbruddsvanskeligheten.

Praktiske applikasjoner

Det harde ved dette problemet er kjernen i flere store kryptografiske systemer. En rask algoritme for heltallsfaktorisering vil bety at den offentlige RSA -algoritmen er usikker. Noen kryptografiske systemer, som Rabins offentlige nøkkelalgoritme og Blum Blum Shub pseudo-tilfeldig tallgenerator, vil garantere en forbedring av deres sikkerhet; enhver metode som klarer å bryte dem, kan brukes til å lage en raskere factoring-algoritme; hvis faktoriseringen av heltall er rask, blir de vanskeligere. Derimot kan det eksistere mer effektive angrep på RSA-problemet , men ingen er kjent.

Et lignende vanskelig problem med kryptografiske applikasjoner er det diskrete logaritmeproblemet .

Nåværende tilstand

Et team ved det tyske føderale byrået for informasjonsteknologisikkerhet ( BSI ) har rekorden for semi -prime factoring i serien foreslått av RSA Factoring Competition , sponset av RSA Security . Den 9. mai 2005 kunngjorde dette teamet faktoriseringen av RSA-200 , et 663-bits tall, ved å bruke den generelle tallkroppen .

Det samme teamet kunngjorde senere faktoriseringen av RSA-640 , et mindre tall som inneholder 193 desimalsiffer (640 biter) 4. november 2005.

Begge faktorene krevde flere måneder med datamaskintid, ved å bruke den kombinerte kraften til 80 AMD Opteron -prosessorer .

Vanskelighetsgrad og kompleksitet

Hvis et stort b -bit tall er produktet av to primtall av omtrent samme størrelse, er det ingen kjent algoritme som kan faktorisere det i polynomtid. Dette betyr at ingen kjent algoritme kan faktorisere det inn i O ( bk ) tid , for en konstant k . Selv om det er algoritmer som er raskere enn O ( a b ) for alle a større enn 1. Med andre ord er de beste algoritmene superpolynomiske, men subeksponentielle. Spesielt er den beste asymptotiske utførelsestiden den for den generelle silalgoritmen for tallkroppen (CGCN), som for et tall n er:

For en vanlig datamaskin er CGCN den mest kjente algoritmen for store tall. For en kvantedatamaskin oppdaget i stedet Peter Shor i 1994 en algoritme som løser det i polynomisk tid . Dette ville ha viktige implikasjoner for kryptografi, dersom det noen gang skulle bygges en kvantedatamaskin. Shors algoritme tar bare O(( log n ) 3 ) tid og opptar O( log n ) plass. I 2001 var den første 7-alen kvantedatamaskinen den første som kjørte Shors algoritme. Han faktoriserte tallet 15.

Det er ikke kjent nøyaktig hvilke kompleksitetsklasser som inneholder heltallsfaktoriseringsproblemet. Dens form for beslutningsproblem ("Har N en faktor mindre enn M ?") er kjent for å ha NP- og co-NP- kompleksitet . Dette er fordi både JA og NEI-svar kan kontrolleres hvis primfaktorene er gitt sammen med deres primalitetssertifikater . Det er kjent for å være i BQP takket være Shors algoritme . Det mistenkes å falle utenfor de tre kompleksitetsklassene ( P , NP Complete, co-NP Complete). Hvis det var mulig å bevise at det er i en av disse to siste, ville det bety at NP = co-NP. Det ville være et veldig overraskende resultat, og derfor er det allment mistanke om at heltallsfaktorisering ligger utenfor begge. Mange har prøvd å finne klassiske polynom-tidsalgoritmer for dette, og mislyktes; derfor mistenkes det å ligge utenfor P. Et annet problem i NP, men som ikke antas å være P eller NP Complete, er grafisk isomorfismeproblem .

Interessant nok er beslutningsproblemet "er N et sammensatt tall ?" (eller hva er det samme: "er N et primtall ?") ​​ser ut til å være mye enklere enn problemet med å finne heltallsfaktorene som N brytes ned i . Spesifikt kan det første problemet løses i polynomisk tid (over antallet n siffer av N ), ifølge en nylig artikkel referert nedenfor. Det er også flere tilfeldige algoritmer som kan teste primaliteten til et tall veldig raskt, hvis du er villig til å akseptere en liten sjanse for feil. Primalitetstestanlegget er en avgjørende del av RSA -algoritmen , siden den er nødvendig for å finne store primtal.

Faktoriseringsalgoritmer

Generelle formål

Utførelsestiden for en generell faktoriseringsalgoritme avhenger bare av størrelsen på heltallet som skal faktoriseres. Dette er typen algoritme som brukes til å faktorisere RSA-tall . De fleste generelle faktoreringsalgoritmer er basert på kongruens av kvadraters metode . Noen av de mest kjente generelle algoritmene er listet opp nedenfor:

Spesifikt formål

Utførelsestiden for en bestemt formålsfaktoriseringsalgoritme avhenger av egenskapene til dens ukjente faktorer: størrelse, spesiell form, etc. Disse faktorene endres fra en algoritme til en annen.

Andre viktige algoritmer

Se også

Referanser

Bibliografi

Eksterne lenker

På spansk

På engelsk