] >
Getallen zijn vaak gegeven in hun tientallige schrijfwijze. Of een getal deelbaar is door of is te zien aan het laatste cijfer, of het door deelbaar is aan de som van de cijfers en deelbaarheid door aan de alternerende som van de cijfers. Dat zijn dan kleine voordelen, maar over het algemeen zet het weinig zoden aan de dijk.
We beschrijven twee basale methoden. Bij de eerste wordt systematisch naar delers gezocht, te beginnen bij . Bij de tweede wordt eerst informatie verkregen over priemgetallen die klein genoeg zijn om in een ontbinding van een gegeven getal voor te kunnen komen.
De meest primitieve vorm van delers zoeken bestaat uit herhaald delen door kleinere getallen totdat een rest is gevonden. Bij het zoeken van delers van hoef je alleen delers met te proberen: bij een deler met hoort een deler . Wordt geen deler gevonden, dan is een priemgetal. Na en geprobeerd te hebben hoeven alleen nog delers met geprobeerd te worden. Voor zulke geldt of . De rij te proberen delers is dan . Deze rij ontstaat door er afwisselend en bij te tellen. Dan zijn er natuurlijk nog steeds onnodige pogingen (te beginnen met het delen door ). Ook kun je eerst een lijstje met priemgetallen maken en dat lijstje bij het zoeken van delers gebruiken. Levert dat geen deler op (omdat de lijst te kort is), dan kunnen andere technieken worden gebruikt.
In de moderne cryptografie wordt gebruik gemaakt van het feit dat het ontbinden van zeer grote getallen voor ons ondoenlijk is als ze alleen grote priemdelers hebben. Zijn en priemgetallen in de orde van , dan is een natuurlijk getal in de orde van . De kleinste echte deler is (als ). Om die systematisch met proberen te vinden moeten zo’n delingen worden uitgevoerd. Doe je er miljard in een seconde, dan duurt dat ongeveer jaar. Dat aantal jaren is in de orde van grootte van het aantal elementaire deeltjes in het heelal.
De functie trial_factors(n, N) geeft een gedeeltelijke priemfactorontbinding van n door alleen priemfactoren kleiner dan te proberen. Is de resterende factor kleiner dan , dan is de volledige priemfactorontbinding gevonden. De functie trial_factorization(n) bepaalt de volledige priemfactorontbinding: het is trial_factors(n,N) met groot genoeg.
Om een lijst te maken van alle priemgetallen kleiner dan een gegeven kun je uitgaan van de lijst . Schrap alle -vouden , ga naar het eerstvolgende getal dat over is (dat moet een priemgetal zijn, want anders was het geschrapt) en schrap alle veelvouden , etc. Zodra het eerstvolgende resterende getal voldoet aan kan het proces stoppen. Over blijft een lijst van priemgetallen kleiner dan . Deze procedure staat bekend als de Zeef van Eratosthenes.
Begin met een lijst van lengte met op iedere plaats een . We maken er een lijst van met op plaats als een priemgetal is en anders. Eerst zetten we een op de plaatsen en . Vervolgens passen we het procedé van Eratosthenes toe, alleen we schrappen niet maar vervangen een door een . Dit gebeurt met de functie eratosthenes(N). De Zeef van Eratosthenes werkt snel, er wordt alleen opgeteld en niet vermenigvuldigd. Het grote nadeel is dat er voor grote veel geheugen nodig is. De functie primes(N) zet het resultaat van eratosthenes(N) om in een lijst met de priemgetallen kleiner dan .
Met een kleine variatie op de zeef, kun je een lijst krijgen met bij ieder samengesteld getal niet een , maar de kleinste priemdeler van dat getal: in plaats van een te plaatsen, plaats een als er nog een staat. Dit is de functie factor_table(N). Die lijst kan gebruikt worden om een getal kleiner dan te factoriseren. Dit doet de functie table_factorization(n). Deze is vooral geschikt als er veel getallen moeten worden gefactoriseerd.
Het is wel duidelijk dat je minder priemgetallen hebt naarmate de getallen groter worden. De volgende functie geeft per definitie voor ieder natuurlijk getal het aantal priemgetallen dat getal.
Een tabel van voor enkele met daarbij tot op nauwkeurig:
Deze tabel doet al wel wat vermoeden. We komen daarop terug in hoofdstuk 15 op bladzijde §.