Een modulaire inverse vinden
Een modulaire inverse maakt vermenigvuldiging binnen één modulus ongedaan. Deze pagina behandelt alleen de multiplicatieve inverse; ze genereert geen RSA-sleutels en ontbindt geen getallen.
Zo werkt het
- Voer een geheel getal a in, eventueel negatief.
- Voer een positieve modulus m groter dan 1 in.
- Bereken de unieke vertegenwoordiger x van 0 tot en met m − 1, als die bestaat.
- Lees de Bézout-regel en echte productrest om het antwoord onafhankelijk te controleren.
Voorwaarde en formule
Een inverse bestaat precies als gcd(a, m) = 1. Het uitgebreide algoritme van Euclides vindt u en v met a·u + m·v = 1; u gereduceerd modulo m is de inverse.
Negatieve a wordt eerst genormaliseerd als ((a mod m) + m) mod m. Het antwoord is altijd de kleinste niet-negatieve vertegenwoordiger.
Uitgewerkte voorbeelden
3 modulo 11
gcd(3, 11) = 1 en 3 × 4 = 12. Omdat 12 mod 11 = 1, is de inverse 4.
−3 modulo 11
−3 wordt genormaliseerd naar 8. Omdat 8 × 7 = 56 en 56 mod 11 = 1, is de inverse 7.
6 modulo 9
gcd(6, 9) = 3, dus geen geheel getal maal 6 kan rest 1 modulo 9 geven.
Invoerlimieten en reikwijdte
- Elke invoer is beperkt tot 200 decimale cijfers om de browser vlot te houden. Voorloopnullen tellen mee voor de typgrens.
- Alleen gehele getallen in grondtal 10 mogen. Decimalen, wetenschappelijke notatie, interne spaties, eenheden en Infinity worden geweigerd.
- Modulus 0, 1 of een negatief getal is ongeldig. a = 0 mag, maar heeft geen inverse bij m > 1.
- Het resultaat is een exact geheel getal, geen decimale benadering. Dit is een rekenhulp, geen cryptografische sleutelgenerator of beveiligingsdienst.
Veelgestelde vragen
Waarom moet de GGD 1 zijn?
Delen a en m een factor groter dan 1, dan deelt elk product a×x die factor en kan het niet congruent zijn met 1 modulo m.
Kan een negatief geheel getal een inverse hebben?
Ja. Het wordt eerst tot zijn kleinste niet-negatieve rest gereduceerd en daarna op dezelfde relatieve priemheid getest.
Waarom wordt maar één antwoord getoond?
Alle inverses verschillen met een veelvoud van m. De calculator toont de unieke waarde van 0 tot m − 1.
Is dit hetzelfde als 1/a?
Nee. Een modulaire inverse is een geheel getal waarvan het product rest 1 heeft bij de gekozen modulus.