Prøvedeling

Prøvedeling, kjent som trial division på engelsk, er en enkel metode for å avgjøre om et heltall n er delelig med et annet tall eller for å faktorisere n. Metoden undersøker potensielle divisorer i et bestemt område, vanligvis fra 2 opp til kvadratroten av n. Hvis en divisor d gir en heltallsquotient n/d, er d og n/d faktorer av n. Hvis ingen divisor gir heltallsquotient, er n et primtall.

For å gjennomføre prøvedelingen tester man først divisjon med 2, deretter med påfølgende oddetall (3, 5, 7, …) opp til floor(sqrt(n)). Når man finner en divisor, kan man dele og registrere faktorparet. For primalitet er det tilstrekkelig å bemerke at ingen divisor ble funnet. Dersom en divisor er funnet, er n dermed ikke primtall, og faktorer kan registreres i par.

Effektivitet og begrensninger: Prøvedeling krever O(sqrt(n)) divisjoner i verste fall og blir upraktisk for store tall. Den kan gjøres raskere ved å bare teste primtall, eller ved å bruke optimeringer som 6k±1 eller wheel-factorization. For større tall brukes ofte mer avanserte algoritmer for faktorisering, mens prøvedeling er vanlig i undervisning og som en enkel metode for små tall.

Eksempel: For n = 91 testes divisorer i rekkefølgen 2, 3, 5 og deretter 7. 91 delbart med 7, og 91/7 = 13, så 91 = 7 × 13. Prøvedeling brukes derfor både som et innledende verktøy i tallteori og som en håndberegningsmetode for faktorisering av små tall.