\require{AMSmath}

Getallenlichamenzeef

De getallenlichamenzeef is een algoritme om samengestelde getallen te ontbinden in priemfactoren. Kunt u zeggen hoe dit in haar werk gaat om bijvoorbeeld 56 te factoriseren?

Jan
Ouder - zondag 10 december 2017

Antwoord

Zoals je op de wikipediapagina (zie link hieronder) is die zeef vooral effectief bij zeer grote getallen. Voor een getal als $56$ is de kwadratische zeef beter geschikt.

De eerste stap is een polynoom van niet al te grote graad te maken waarvan de complexe nulpunten een ingrediënt voor de rest van de procedure vormen. Dat gaat via $\sqrt[d]{56}$, met name het gehele deel daarvan. Voor kleine getallen is $d=2$ handig, het gehele deel van $\sqrt{56}$ is gelijk aan $7$.

Vervolgens schrijf je $56$ in basis $7$. Er komt $56=7^2+7$ en je neemt dan $f(x)=x^2+x$. In dit geval ben je klaar want $f$ is reducibel, $x^2+x=x\cdot(x+1)$ en daarmee is de factorizering al gevonden: $56=7\cdot(7+1)=7\cdot8$.

In het algemeen werk je in een deelring van het lichaam der complexe getallen, namelijk $\mathbb{Z}[\theta]$, waar $\theta$ een nulpunt van $f$ is. Alles is er op gericht twee getallen te vinden die modulo $N$ (het te ontbinden getal) hetzelfde kwadraat hebben, en dat kost nogal wat moeite, zoals je op de wikipediapagina kunt lezen.

Zie Wikipedia: Getallenlichaamzeef

kphart
zondag 10 december 2017

Re: Getallenlichamenzeef

©2001-2024 WisFaq