3. Eentallige bewerkingen

Zij gegeven een verzameling X met een eentallige bewerking f : X → X. Wat kun je hiermee doen? Eigenlijk alleen maar kijken naar de banen: x, f(x), f(f(x)), ...

De functie f heet idempotent als voor alle x geldt dat f(f(x)) = f(x).

De functie f heet periodiek (met periode n) als voor alle x geldt dat fⁿ(x) = x.

Een involutie is een periodieke afbeelding met periode 2.

Bijvoorbeeld: de bewerking die een getal x naar zijn tegengestelde –x stuurt is een involutie. En verticale projectie uit de ruimte op het vlak Z = 0 is idempotent.

3.1 Rho

Als de verzameling X eindig is, dan moet elke baan ook eindig zijn. Dat betekent dat na een aantal stappen weer een element voorkomt dat al eerder gezien is: fⁿ(x) = f^m(x). (En natuurlijk kan dit ook voorkomen als X niet eindig is.)

Bij computertoepassingen treedt vaak het probleem op: Als het ondoenlijk is om van een baan alle elementen te bewaren omdat dat niet in het geheugen past, of als het zeer tijdrovend is om telkens een element met alle eerder geziene elementen te vergelijken, hoe moet je dan detecteren dat de operatie f in herhalingen vervalt?

Een standaard oplossing (gegeven door Floyd) gaat als volgt. Volg de baan met twee vingers, waarbij de ene tweemaal zo snel gaat als de andere. Dwz: bereken (x,x), dan (fx,ffx), dan (ffx,ffffx), dan (fffx,ffffffx) enz., telkens door f drie keer toe te passen, een keer links en twee keer rechts. (Hier staat fx in plaats van f(x) om een oerwoud aan haakjes te vermijden.) We merken herhaling op als beide vingers weer naar dezelfde plaats wijzen. Bijvoorbeeld, als f¹⁷(x) = f¹¹(x) dan merken we herhaling op bij de twaalde stap: f²⁴(x) = f¹²(x).

Opgave (i) Ga na dat dit algoritme altijd werkt. Als fⁿ(x) = f^m(x), (met n > m) en dit is de eerste herhaling die optreedt, op welk moment detecteert dit algoritme dan de herhaling?

(ii) Ga na welke banen optreden bij kwadrateren modulo M, voor M = 7 en M = 10. Construeer een voorbeeld waarbij een lus ter lengte drie optreedt.

3.2 Pollard rho

Een toepassing wordt gevonden bij het ontbinden in factoren. Als n geen priemgetal is, dan duurt het vinden van een priemfactor p als we delen door 2, 3, 5, 7, ... O(p) stappen (of O(p/log p) stappen als we slim zijn, en alleen door priemgetallen delen). Maar Pollard rho vindt p in O(√p) stappen. Als een stap een microseconde duurt, en p 16 cijfers heeft, dan vindt proefdelen deze factor na 100 jaar en Pollard rho na 100 seconden.

Dit algoritme werkt als volgt. Stel we willen een of ander getal n ontbinden. Verzin een of andere afbeelding f : N → N gedefinieerd door een polynoom. Bijvoorbeeld f(x) = x² + 3. Bereken dan in navolging van Floyd (fx,ffx),..., (f^mx,f^2mx), alles modulo n, en bereken telkens de ggd van n en het verschil van beide elementen in het paar. Stop zodra de ggd niet 1 is. Is hij n dan hebben we pech gehad en beginnen overnieuw met een nieuwe startwaarde x of een nieuwe functie f. Is hij niet 1 of n dan hebben we de gezochte deler van n gevonden.

Voorbeeld Bekijk n = 1000000013. (Met Maple of Mathematica of GAP of met een klein C programmaatje.) Na 96 stappen vinden we de factor 7699. (En 1000000013 = 7699 * 129887.) Dat was met f(x) = x² + 3 en beginwaarde x = 0. Andere beginwaarden zijn beter (bijvoorbeeld bij 2 kost de ontbinding 24 stappen, en bij 45 maar 7 stappen) of slechter (bijvoorbeeld bij 60 kost de ontbinding 192 stappen). Bij beginwaarde 17 wordt de factor 129887 gevonden na 17 stappen.

Volledig uitgewerkt bij beginwaarde 719:
Begin met (719,719). Nu is (719*719+3)%1000000013 = 516964 en (516964*516964+3)%1000000013 = 251773828, dus na 1 stap hebben we (516964,251773828), en ggd(251773828–516964,1000000013) = 1.
Vervolgens is (251773828*251773828+3)%1000000013 = 641702820 en (641702820*641702820+3)%1000000013 = 842779864, dus na 2 stappen hebben we (251773828,842779864) en ggd(842779864–251773828,1000000013) = 7699. Klaar!

Waarom werkt dit eigenlijk? Als de functie voldoende willekeurig verspreide getallen oplevert (modulo p) dan verwachten we vanwege de "verjaardagsparadox" dat een herhaling (modulo p) optreedt na orde wortel p stappen.

Statistiek [Hieronder wordt wat getaltheorie gebruikt. Sla over wat je niet herkent.]

Alle beginwaarden tussen 0 en 999999 proberend vind ik minimum 2, maximum 192, gemiddeld 92 stappen nodig voor factorisatie. Het algoritme faalde nooit.

Maar dit was met f(x) = x² + 3. Hoe zit het met andere functies? Met f(x) = x² + c en beginwaarde tussen 0 en 99999 vinden we:

Hmm. Voor alle c werkt dit wel bevredigend: na gemiddeld 100 stappen of zo is 1000000013 ontbonden. Alleen bij c = 0 en bij c = –2 gaat het veel slechter. Is daar een theoretische reden voor?

Bij f(x) = x² kwadrateren we steeds. Dat is niet willekeurig genoeg. In dit geval, met p = 7699, is de multiplicatieve groep van de niet-nul resten modulo p cyclisch van orde 7698, kortom, kwadrateren modulo 7699 gedraagt zich als verdubbelen modulo 7698. Maar 7698 = 2*3*1283, en 2 is een primitieve wortel modulo 1282, dus herhaling treedt pas op na 1282 stappen. (En deze redenering geldt algemeen: in het algemeen zullen grote lussen voorkomen.)

Bij f(x) = x²–2 is er iets dergelijks aan de hand. Met x = a + 1/a geldt f(x) = a² + 1/a². Dus weer herhaald kwadrateren, maar nu van a ipv x. In dit voorbeeld hebben we ook erg veel pech, d.w.z. dat op het moment dat we een factor ontdekken beide factoren al voorkomen. Dat komt omdat a + 1/a = b + 1/b als a = b of als a = 1/b, met andere woorden niet alleen de delers van p–1 maar ook de delers van p+1 spelen een rol. In dit voorbeeld geldt toevallig 7700 = 2*2*5*5*7*11 en 129888 = 2*2*2*2*2*3*3*11*41, allemaal kleine factoren, en dit zorgt voor veel korte periodes.

Tot zover Pollard rho. Een goede manier om middelgrote getallen in factoren te ontbinden als je f(x) = x²+c neemt met c niet 0 of –2.