Algoritmprincip:
Pollard Rho är en probabilistisk algoritm för heltalsfaktorisering, särskilt effektiv för att hitta medelstora faktorer i sammansatta tal. Algoritmens namn kommer från dess bana som liknar den grekiska bokstaven ρ (rho).
Optimeringsstrategier:
- Optimerad försöksdivision:Använd först små primtal (2, 3, 5, 7, 11...) för försöksdivision för att snabbt hitta små faktorer.
- Pollard Rho:För större sammansatta tal, använd pseudo-slumpmässig sekvens x = (x² + c) mod n för att hitta faktorer.
- Floyds cykeldetekteringsalgoritm:Använd snabba och långsamma pekare för att upptäcka cykler i sekvensen, vilket optimerar minnesanvändningen.
- Miller-Rabin primtalstest:Efter att ha hittat en faktor, kontrollera om den är ett primtal för att undvika onödig vidare faktorisering.
- Rekursiv faktorisering:Faktorisera de funna faktorerna rekursivt tills alla är primtal.
Tidskomplexitet:
- Försöksdivision:O(√n), lämpligt för små tal eller snabb sökning efter små faktorer.
- Pollard Rho:Förväntad tid O(n^(1/4)), mycket effektivt för tal med medelstora faktorer.
- Miller-Rabin:O(k log³n), där k är antalet testomgångar, används för primtalstestning.