Hvordan finne primfaktorer raskt?

[stensrud]

Finnes det en enkel metode for å finne primfaktorer til tall mellom ca. 500 og 10 000? Ta tallet 2017 som et eksempel: det ER et primtall, men hvordan går det an å komme fram til det uten kalkis? Hva med tall som 2183? (59 ganger 37).

Hvis dere hadde måtte gjort det for hånd under en oppgave, ville dere sjekket deleligheten på 3, 7 og 9 først, for å deretter prøve 13, 17 og 19 før dere hadde gitt opp, eller hva?

[Reignors]

Den beste måten jeg vet om er å ta kvadratroten av tallet du vil finne ut om er et primtall, hvis ingen av primtallene under dette tallet går opp i det originale tallet, så er det originale tallet et primtall.

Det blir fortsatt prøve/feile metode, men på denne måten vet du hvert fall hvor mange tall du må prøve med for å være sikker.

[Nebuchadnezzar]

Dersom du finner en rask metode å faktorisere store primtall på vinner du nok uten tvil abelprisen.
På den negative siden vil nok de fleste store banker i verden prøve å ta livet av deg fort som fy.

En veldig naiv måte er å teste alle tall fra 2 til og med $\sqrt{n}$. Dersom 2 ikke går dropper
vi å teste alle partall fremmover. Dersom 3 ikke går dropper vi å teste alle tall i 3 gangen osv.
Denne metoden er basert på Eratosthene Siv elns

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

http://rosettacode.org/wiki/Primality_by_trial_division Masse praktiske eksempler. Dette er nok
den aller enkleste metoden.

Under står det litt om noen primtalls faktoriseringer. Vil en lære mer om sånt finnes det store grener
innen matematikk som omhandler dette. Eg mye tallteori, spesifikt kodeteori og kryptografi.

http://en.wikipedia.org/wiki/Primality_test

Eksakte metoder for å finne primtall er helt latterlig trege. Derimot er det langt raskere å kjøre
sannsynlighets-algoritmer. Dersom algoritmen spytter ut 0 vet vi at tallet ikke er primtall. Dersom
det spytter ut 1 er det 50% sannsynlig at tallet er primtall. Da kan vi bare kjøre denne algoritmen noen ganger
(banker bruker gjerne rundt 88 ganger) for å teste om tallet sannsynligvis er primsk.

Populære metoder her er http://en.wikipedia.org/wiki/Fermat_primality_test , http://rosettacode.org/wiki/Miller-Rabin_primality_test eller http://en.wikipedia.org/wiki/Solovay%E2 ... ality_test. En driver også med med modulære elliptiske kurver og hvordan disse kan brukes til å
bestemme om tall er primtall. Uten at jeg har helt snøring på hvordan dette fungerer i praksis.

Her er en liten video som forklarer en metode https://www.youtube.com/watch?v=xMj3jzFDZ38