fermats faktoriseringsmetode
Lagt inn: 02/10-2009 23:33
hvorfor fungerer denne faktoriseringsmetoden?
Hvis du skal faktorisere f.eks 9991 observerer du at 9991=10000-9
Begge disse tallene er kvadrattall: 10000=100^2 og 9=3^2,
så [tex]9991=100^2-3^2[/tex]
Vi vet at for alle x og y er [tex]x^2-y^2=(x+y)(x-y)[/tex]. Derfor er
[tex]9991=100^2-3^2=(100-3)(100+3)[/tex] Så vi har faktorisert 9991 på en lettvint måte.
Alternativet er mye mer tungvint. f.eks. systematisk å sjekke om hvert primtall fra og med 2 deler 9991