On the Inversion Modulo a Power of an Integer

Dit artikel introduceert twee efficiënte algoritmen voor het berekenen van de modulaire inverse $x = a^{-1} \pmod{n^k}$ voor willekeurige gehele getallen $n > 1$, waarbij het eerste algoritme gebaseerd is op $p$-adische expansies en het tweede een generalisatie vormt van bestaande Hensel-lifting-methoden voor machten van de vorm $n^{2^s}$.

De kern

Stel je voor dat je een enorme, ingewikkelde vergrendeling hebt (een wiskundige vergelijking) en je moet de sleutel vinden om hem open te maken. In de digitale wereld is deze "sleutel" vaak een modulair omgekeerd getal. Dit klinkt als saaie wiskunde, maar het is de basis van beveiliging op internet, van banktransacties tot geheime berichten.

Deze paper van Guangwu Xu en zijn collega's is als een nieuw, slimmer gereedschap om die sleutels sneller te vinden. Hier is de uitleg in gewone taal, met een paar creatieve vergelijkingen.

1. Het Probleem: De "Deling" die te lang duurt

Stel je voor dat je een taart wilt verdelen onder vrienden. Als je de taart in stukken snijdt (deling), kost dat veel tijd en energie. In computers is delen ook erg duur en traag. Vermenigvuldigen daarentegen gaat als een speer.

Vroeger probeerden wiskundigen de deling te "omzeilen" door te vermenigvuldigen, maar dat werkte alleen bij heel specifieke getallen (zoals machten van 10). De uitvinding van moderne cryptografie (zoals RSA) maakte echter dat we constant deze "delingen" moesten doen, maar dan met enorme getallen. Computers werden hierdoor een beetje traag.

2. De Eerste Oplossing: De "Schoolboek" Methode

De auteurs van dit paper kijken naar iets heel simpels: vermenigvuldigen zoals we dat op school leren.

Stel je voor dat je twee lange getallen vermenigvuldigt. Je schrijft ze onder elkaar, vermenigvuldigt cijfer voor cijfer en schuift de resultaten een beetje op (net als bij het optellen van geld: centen worden euro's).

• De oude methode: Probeerde de sleutel te vinden door ingewikkelde formules te gebruiken die veel "delingen" vereisten.
• De nieuwe methode (Deze paper): Kijkt naar hoe de "overdrachten" (de getallen die je naar de volgende kolom schuift) werken bij vermenigvuldigen. Ze ontdekten dat je deze overdrachten kunt gebruiken om de sleutel stap voor stap te bouwen, zonder dure delingen.

De Analogie:
Stel je voor dat je een toren bouwt met blokken.

• De oude methode was alsof je elke keer de hele toren moest afbreken om te controleren of hij recht stond.
• De nieuwe methode is alsof je elke laag bouwt en direct ziet of hij perfect past. Als hij niet past, pas je alleen het bovenste blokje aan. Omdat computers heel goed zijn in het "schuiven" van blokken (bit-shifts), gaat dit razendsnel.

3. Het Geniale Trucje: Kies je eigen "Basis"

De meeste computers werken in het binaire systeem (alleen 0 en 1, macht van 2). De auteurs zeggen echter: "Waarom beperken we ons tot 2?"

Stel je voor dat je een auto hebt die normaal gesproken op benzine rijdt (basis 2). Deze paper zegt: "Je kunt deze auto ook laten rijden op diesel of elektriciteit (basis 2^64 of 2^128), zolang je maar de juiste brandstofkoppeling gebruikt."

• Basis 2^64: Dit is de natuurlijke grootte van een "woord" in een moderne computer (64 bits). Door te rekenen met blokken van 64 bits in plaats van 1 bit, kan de computer in één keer een heel groot stuk van de sleutel berekenen.
• Het resultaat: Het is alsof je van een fiets op een snorfiet overstapt. De paper toont aan dat hun methode met deze grote blokken (basis 2^64 of zelfs 2^128) veel, veel sneller is dan de beste methoden die daarvoor bestonden.

4. De Tweede Oplossing: De "Hensel Lift" (De Trap)

Er was al een andere methode bekend, gebaseerd op iets dat "Hensel-liften" heet.

• De Analogie: Stel je voor dat je een trap beklimt. De oude methode sprong van stap 1 naar stap 2, dan naar 4, dan naar 8 (verdubbeling). Dit was snel, maar alleen als je op een heel specifieke trap (macht van een priemgetal) liep.
• De verbetering: De auteurs van deze paper hebben die trap verbreed. Ze hebben laten zien dat je deze sprongmethode ook kunt gebruiken op elke trap, niet alleen de speciale ones. Ze hebben een simpele algebraïsche formule bedacht die deze methode werkt maakt voor willekeurige getallen.

Waarom is dit belangrijk voor jou?

Je merkt het misschien niet direct, maar dit soort wiskundige optimalisaties zijn de reden dat:

1. Je online bankieren veilig en snel is.
2. Je versleutelde berichten (zoals WhatsApp) direct aankomen.
3. Computers minder stroom verbruiken omdat ze minder "zware" berekeningen hoeven te doen.

Samenvattend:
Deze paper is als een nieuwe, slimmere manier om een puzzel op te lossen. In plaats van te hameren op de oplossing met een zware hamer (deling), gebruiken ze een precieze schroevendraaier (vermenigvuldiging en schuiven) en ze hebben ontdekt dat je de schroevendraaier kunt vergroten om nog grotere puzzels in één keer op te lossen. Het resultaat? Snellere computers en veiligere communicatie.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "On the Inversion Modulo a Power of an Integer" van Guangwu Xu, Yunxiao Tian en Bingxin Yang, vertaald en samengevat in het Nederlands.

Titel: Over de Inversie Modulo een Macht van een Geheel Getal

1. Het Probleem

De berekening van de multiplicatieve inversie $x = a^{-1} \pmod{m}$ is een fundamentele bewerking in de moderne cryptografie (zoals RSA en elliptische krommen) en homomorfische encryptie. Traditionele methoden voor het berekenen van deze inversie, zoals de uitgebreide Euclidische algoritme, zijn vaak duur in termen van rekentijd, vooral wanneer de modulus $m$ een grote macht is van een geheel getal ($m = n^k$).

Bestaande efficiënte algoritmen zijn vaak beperkt tot specifieke gevallen:

• Koç's algoritme: Werkt efficiënt voor $m = p^k$ (waarbij $p$ een priemgetal is), maar is minder flexibel voor willekeurige basissen $n$.
• Hensel-lifting (Dumas/Hurchalla): Werkt uitstekend voor $m = p^{2^s}$ (vaak $p=2$), maar is beperkt tot machten van priemgetallen.

De uitdaging is om een algoritme te ontwikkelen dat zowel efficiënt is (vooral voor moderne computerarchitecturen) als generiek (werkend voor elke basis $n > 1$, niet alleen priemgetallen).

2. Methodologie

Het artikel introduceert twee hoofdmethodes om dit probleem aan te pakken:

Deel 1: Een nieuw algoritme gebaseerd op "Schoolbook" vermenigvuldiging

De auteurs ontwerpen een algoritme voor het berekenen van $a^{-1} \pmod{n^k}$ voor willekeurige $n > 1$ en $k > 0$, mits $\gcd(a, n) = 1$.

• Inspiratie: Het algoritme is gebaseerd op de mechaniek van de klassieke "schoolbook" vermenigvuldiging en de verwerking van overdrachten (carries).
• Werkingsprincipe:
  • Het getal $a$ en de gezochte inversie $x$ worden weergegeven in het $n$-talstelsel: $a = \sum a_i n^i$ en $x = \sum X_i n^i$.
  • Door de vergelijking $ax \equiv 1 \pmod{n^k}$ te analyseren, leiden de auteurs een recursieve relatie af voor de cijfers $X_i$ en de overdrachten $T_i$.
  • De recursie luidt: $T_{i+1} = T_i + \frac{a X_i}{n}$ en $X_i = -c \cdot T_i \pmod n$, waarbij $c = a^{-1} \pmod n$.
• Flexibiliteit: Omdat $n$ willekeurig kan zijn, kan men $n$ kiezen als een macht van 2 die overeenkomt met de woordgrootte van de processor (bijv. $n = 2^{64}$ of $n = 2^{128}$). Dit maakt gebruik van de ingebouwde hardware-arithmetic van de CPU, waardoor duurdere delingen worden vermeden ten gunste van bit-shifts en optellingen.

Deel 2: Generalisatie van Hensel-lifting

De auteurs analyseren en generaliseren bestaande methoden van Dumas en Hurchalla.

• Bestaande methode: Deze gebruiken Newton-Raphson iteratie (Hensel-lifting) om de oplossing van $ax \equiv 1 \pmod{p^{2^s}}$ te vinden, waarbij de exponent van de modulus verdubbelt in elke stap.
• Generalisatie: De auteurs tonen via eenvoudige algebraïsche manipulaties aan dat deze recursie ook geldt voor moduli van de vorm $n^{2^s}$ voor elke $n > 1$.
• Formule: Ze leiden een recursie af van de vorm $x_{m+1} = x_m(1 + y^{2^m}) \pmod{n^{2^s}}$, waarbij $y = 1 - ax_0$. Dit stelt hen in staat om de efficiëntie van Hurchalla's algoritme toe te passen op niet-priem bases.

3. Belangrijkste Bijdragen

1. Algoritmische Generalisatie: De eerste algoritmes die de berekening van $a^{-1} \pmod{n^k}$ efficiënt uitvoeren voor willekeurige gehele getallen $n > 1$, niet beperkt tot priemgetallen.
2. Hardware-optimalisatie: Door $n$ te kiezen als $2^{64}$of$2^{128}$, benut het algoritme de native 64-bit of 128-bit rekenkracht van moderne CPU's. Dit elimineert de noodzaak voor dure softwarematige delingen.
3. Alternatief Bewijs: Het paper biedt een nieuw, compleet ander bewijs van correctheid voor Koç's algoritme, wat inzicht geeft in de eigenschappen van de tussenstappen (zoals het berekenen van $(p^s)^{-1} \pmod a$ als bijproduct).
4. Nieuwe Initialisatieformules: Voor het geval $i_0=4$ in Hensel-lifting, wordt een nieuwe expliciete formule voor de initiële schatting $x_0$ voorgesteld die uitsluitend XOR-bewerkingen vereist.

4. Resultaten en Experimentele Prestaties

De auteurs hebben hun algoritmen geïmplementeerd en getest op een systeem met een AMD Ryzen 7 8845HS processor (Ubuntu 24.04). De resultaten tonen aanzienlijke verbeteringen:

• Vergelijking: Het nieuwe algoritme (met $n=2^{64}$ en $n=2^{128}$) werd vergeleken met Koç's algoritme en Hurchalla's algoritme voor verschillende bitlengtes ($k$ van 128 tot 4096).
• Snelheidswinst:
  • Voor kleine $k$ (bijv. 128 bits) is het nieuwe algoritme al aanzienlijk sneller dan Koç's methode (2.81 ns vs 177.89 ns).
  • Voor grotere $k$ (bijv. 4096 bits) is de snelheidswinst dramatisch: 7253 ns voor het nieuwe algoritme (met $n=2^{64}$) versus 389.627 ns voor Koç's algoritme.
  • Het gebruik van $n=2^{128}$ is vaak nog sneller dan $n=2^{64}$ voor zeer grote moduli, omdat het aantal iteraties wordt gehalveerd.
• Conclusie: De prestaties tonen aan dat het benutten van de native woordgrootte van de hardware een cruciale factor is voor het maximaliseren van de efficiëntie.

5. Betekenis en Toekomstperspectief

Dit onderzoek is van groot belang voor de cryptografie en het hoge-prestatie rekenen:

• Efficiëntie: Het biedt een snellere manier om modulaire inversies te berekenen, wat een kritieke bottleneck is in veel cryptografische protocollen.
• Generaliteit: Het opent de deur voor efficiënte berekeningen in positiestelsels met niet-priem basissen (zoals decimaal of duodecimaal), hoewel de huidige toepassing vooral gericht is op binaire systemen voor hardware-optimalisatie.
• Architectuur-afhankelijkheid: Het paper benadrukt dat algoritmes die zijn ontworpen met inachtneming van de specifieke eigenschappen van computerhardware (zoals bit-shifts en native woordgroottes), aanzienlijk superieur kunnen zijn aan theoretisch geoptimaliseerde maar hardware-agnostische methoden.

Samenvattend biedt dit paper een robuust, flexibel en uiterst snel alternatief voor bestaande methoden om modulaire inverses te berekenen, met name door slim gebruik te maken van de architectuur van moderne computers.