Modulär multiplikativ invers

Inom matematiken , särskilt inom aritmetiken , är en modulär multiplikativ invers av ett heltal a ett heltal x så att produktaxeln är kongruent med 1 med avseende på modulen m . I standardnotationen för modulär aritmetik skrivs denna kongruens som

$ax\equiv 1{\pmod {m}},$

vilket är förkortningen av att skriva påståendet att m delar (jämnt) kvantiteten ax − 1 , eller, uttryckt på annat sätt, resten efter att ha dividerat ax med heltal m är 1. Om a har en invers modulo m , så finns det är ett oändligt antal lösningar av denna kongruens, som bildar en kongruensklass med avseende på denna modul. Dessutom har varje heltal som är kongruent med a (dvs. i a 's kongruensklass) vilket element som helst av x 's kongruensklass som en modulär multiplikativ invers. Genom att använda notationen ${\overline {w}}$ för att indikera kongruensklassen som innehåller w , kan detta uttryckas genom att säga att den modulo multiplikativa inversen av kongruensklassen ${\overline {a }}$ är kongruensklassen ${\overline {x}}$ så att:

${\overline {a}}\cdot _{m}{\overline {x}}={\overline {1}},$

där symbolen $\cdot _{m}$ betecknar multiplikationen av ekvivalensklasser modulo m . Skrivet på detta sätt är analogin med det vanliga konceptet med en multiplikativ invers i uppsättningen av rationella eller reella tal tydligt representerad, och ersätter talen med kongruensklasser och ändrar den binära operationen på lämpligt sätt.

Liksom med den analoga operationen på de reella talen, är en grundläggande användning av denna operation att lösa, när det är möjligt, linjära kongruenser av formen

$ax\equiv b{\pmod {m}}.$

Att hitta modulära multiplikativa inverser har också praktiska tillämpningar inom kryptografi, dvs public -key kryptografi och RSA-algoritmen . En fördel för datorimplementeringen av dessa applikationer är att det finns en mycket snabb algoritm (den utökade euklidiska algoritmen ) som kan användas för beräkning av modulära multiplikativa inverser.

Modulär aritmetik

Huvudartikel: Modulär aritmetik

För ett givet positivt heltal m sägs två heltal, a och b , vara kongruenta modulo m om m delar deras skillnad. Denna binära relation betecknas med,

$a\equiv b{\pmod {m}}.$

Detta är en ekvivalensrelation på mängden heltal, ℤ , och ekvivalensklasserna kallas kongruensklasser modulo m eller restklasser modulo m . Låt ${\overline {a}}$ beteckna kongruensklassen som innehåller heltal a , då

${\overline {a}}=\{b\in \mathbb {Z} \mid a\equiv b{\pmod {m}}\}.$

En linjär kongruens är en modulär kongruens av formen

$ax\equiv b{\pmod {m}}.$

Till skillnad från linjära ekvationer över realerna kan linjära kongruenser ha noll, en eller flera lösningar. Om x är en lösning av en linjär kongruens så är varje element i ${\overline {x}}$ också en lösning, så när vi talar om antalet lösningar av en linjär kongruens hänvisar vi till talet av olika kongruensklasser som innehåller lösningar.

Om d är den största gemensamma divisorn för a och m så har den linjära kongruensen ax ≡ b (mod m ) lösningar om och bara om d delar b . Om d delar b , så finns det exakt d lösningar.

En modulär multiplikativ invers av ett heltal a med avseende på modulen m är en lösning av den linjära kongruensen

$ax\equiv 1{\pmod {m}}.$

Det tidigare resultatet säger att en lösning existerar om och endast om gcd( a , m ) = 1 , det vill säga a och m måste vara relativt primtal (dvs. coprime). Dessutom, när detta villkor gäller, finns det exakt en lösning, dvs. när den existerar, är en modulär multiplikativ invers unik: Om b och b' båda är modulära multiplikativa inverser av ett förhållande till modulen m , då

$ab\equiv ab'\equiv 1{\pmod {m}},$

därför

$a(bb')\equiv 0{\pmod {m}}.$

Om a ≡ 0 (mod m ) , så kommer gcd( a , m ) = a , och a inte ens ha en modulär multiplikativ invers. Därför är b ≡ b' (mod m ) .

När ax ≡ 1 (mod m ) har en lösning betecknas det ofta på detta sätt −

$x\equiv a^{-1}{\pmod {m}},$

men detta kan betraktas som ett missbruk av notation eftersom det kan misstolkas som det reciproka av $a$ (som, i motsats till den modulära multiplikativa inversen, inte är ett heltal förutom när a är 1 eller -1). Notationen skulle vara korrekt om a tolkas som en token som står för kongruensklassen ${\overline {a}}$ , eftersom den multiplikativa inversen av en kongruensklass är en kongruensklass med multiplikationen definierad i nästa sektion.

Heltal modulo m

Kongruensrelationen, modulo m , delar upp mängden heltal i m kongruensklasser. Operationer för addition och multiplikation kan definieras på dessa m objekt på följande sätt: För att antingen addera eller multiplicera två kongruensklasser, välj först en representant (på vilket sätt som helst) från varje klass och utför sedan den vanliga operationen för heltal på de två representanterna och slutligen ta kongruensklassen som resultatet av heltalsoperationen ligger i som resultatet av operationen på kongruensklasserna. I symboler, där $+_{m}$ och $\cdot _{m}$ representerar operationerna på kongruensklasser, är dessa definitioner

${\overline {a}}+_{m}{\overline {b}}={\overline {a+b}}$

och

${\overline {a}}\cdot _{m}{\overline {b}}={\overline {ab}}.$

Dessa operationer är väldefinierade , vilket innebär att slutresultatet inte beror på de val av representanter som gjordes för att få resultatet.

De m kongruensklasserna med dessa två definierade operationer bildar en ring , kallad ringen av heltal modulo m . Det finns flera notationer som används för dessa algebraiska objekt, oftast $\mathbb {Z} /m\mathbb {Z}$ eller $\mathbb {Z} /m$ , men flera elementära texter och tillämpningsområden använder en förenklad notation $\mathbb {Z} _{m}$ när förväxling med andra algebraiska objekt är osannolik.

Kongruensklasserna för heltal modulo m var traditionellt kända som restklasser modulo m , vilket återspeglar det faktum att alla element i en kongruensklass har samma återstod (dvs "rest") när de divideras med m . Varje uppsättning m heltal som väljs så att var och en kommer från en annan kongruensklass modulo m kallas ett komplett system av rester modulo m . Divisionsalgoritmen visar att mängden heltal, {0, 1, 2, ..., m − 1} bildar ett komplett system av rester modulo m , känt som minsta restsystem modulo m . När man arbetar med aritmetiska problem är det ibland mer bekvämt att arbeta med ett komplett system av rester och använda kongruensspråket medan andra gånger synvinkeln för kongruensklasserna i ringen Z / m Z {\ $Z } /m\mathbb {Z} }$ är mer användbar.

Multiplikativ grupp av heltal modulo m

Huvudartikel: Multiplikativ grupp av heltal modulo n

Inte varje element i ett komplett restsystem modulo m har en modulär multiplikativ invers, till exempel har noll aldrig. Efter att ha tagit bort elementen i ett komplett restsystem som inte är relativt prime till m kallas det som finns kvar ett reducerat restsystem , vars alla element har modulära multiplikativa inverser. Antalet element i ett reducerat restsystem är $\phi (m)$ , där $\phi$ är Euler totientfunktionen , dvs antalet positiva heltal mindre än m som är relativt prime till m .

I en allmän ring med enhet har inte alla element en multiplikativ invers och de som gör det kallas enheter . Eftersom produkten av två enheter är en enhet, bildar enheterna i en ring en grupp , gruppen av enheter i ringen och ofta betecknad med R ^× om R är namnet på ringen. Gruppen av enheter i ringen av heltal modulo m kallas den multiplikativa gruppen av heltal modulo m , och den är isomorf till ett reducerat restsystem. I synnerhet har den ordning (storlek), $\phi (m)$ .

Om m är ett primtal , säg p , då $\phi (p)=p-1$ och alla element som inte är noll i $\ mathbb {Z} /p\mathbb {Z}$ har multiplikativa inverser, så $\mathbb {Z} /p\mathbb {Z}$ är ett ändligt fält . I detta fall bildar den multiplikativa gruppen av heltal modulo p en cyklisk grupp av ordningen p − 1 .

Exempel

För alla heltal $n>1$ är det alltid så att $n^{2}-n+1$ är den modulära multiplikativa inversen av $n+1$ med avseende på modulen $n^{2}$ , eftersom $(n+1)(n ^{2}-n+1)=n^{3}+1$ . Exempel är ${\displaystyle 3\times 3\equiv 1{\pmod {4}}} ,$ 4 $\displaystyle 4\times 7\equiv 1{ \pmod {9}}}$ , $5\times 13\equiv 1{\pmod {16}}$ och så vidare.

Följande exempel använder modulen 10: Två heltal är kongruenta mod 10 om och endast om deras skillnad är delbar med 10, till exempel

$32\equiv 2{\pmod {10}}$ 10 delar 32 − 2 = 30, och

$) {\displaystyle 111\equiv 1{\pmod { 10}}}$ eftersom 10 delar 111 − 1 = 110.

Några av de tio kongruensklasserna med avseende på denna modul är:

${\overline {0}}=\{\cdots ,-20,-10,0,10,20,\cdots \}$

${\overline {1}}=\{\cdots ,-19,-9,1,11,21,\ cdots \}$

${\overline {5}}=\{\cdots ,-15,-5,5,15, 25,\cdots \}$ och

${\overline {9}}=\{\cdots ,-11,-1,9,19,29,\cdots \}.$

Den linjära kongruensen 4 x ≡ 5 (mod 10) har inga lösningar eftersom heltal som är kongruenta med 5 (dvs. de i ${\overline {5}}$ ) är alla udda medan 4 x alltid är jämnt . Den linjära kongruensen 4 x ≡ 6 (mod 10) har dock två lösningar, nämligen x = 4 och x = 9 . Gcd (4, 10) = 2 och 2 delar inte 5, men delar 6.

Eftersom gcd(3, 10) = 1 kommer den linjära kongruensen 3 x ≡ 1 (mod 10) att ha lösningar, det vill säga modulära multiplikativa inverser av 3 modulo 10 kommer att existera. Faktum är att 7 uppfyller denna kongruens (dvs 21 − 1 = 20). Men även andra heltal uppfyller kongruensen, till exempel 17 och −3 (dvs 3(17) − 1 = 50 och 3(−3) − 1 = −10). I synnerhet kommer varje heltal i ${\overline {7}}$ att uppfylla kongruensen eftersom dessa heltal har formen 7 + 10 r för något heltal r och

$3(7+10r)-1=21+30r-1=20+ 30r=10(2+3r),$

är delbart med 10. Denna kongruens har bara denna ena kongruensklass av lösningar. Lösningen i detta fall hade kunnat erhållas genom att kontrollera alla möjliga fall, men systematiska algoritmer skulle behövas för större moduler och dessa kommer att ges i nästa avsnitt.

Produkten av kongruensklasserna ${\overline {5}}$ och ${\overline {8}}$ kan erhållas genom att välja ett element av ${\overline {5 }}$ , säg 25, och ett element av ${\overline {8}}$ , säg −2, och observera att deras produkt (25)(−2) = −50 är i kongruensklassen ${\overline {0}}$ . Således, ${\overline {5}}\cdot _{10}{\overline {8}}={\overline {0}}$ . Addition definieras på liknande sätt. De tio kongruensklasserna tillsammans med dessa operationer av addition och multiplikation av kongruensklasser bildar ringen av heltal modulo 10, dvs $\mathbb {Z} /10\mathbb {Z}$ .

Ett komplett restsystem modulo 10 kan vara mängden {10, −9, 2, 13, 24, −15, 26, 37, 8, 9} där varje heltal är i en annan kongruensklass modulo 10. Det unika minsta restsystemet modulo 10 är {0, 1, 2, ..., 9}. Ett reducerat restsystem modulo 10 skulle kunna vara {1, 3, 7, 9}. Produkten av vilka två kongruensklasser som helst som representeras av dessa siffror är återigen en av dessa fyra kongruensklasser. Detta innebär att dessa fyra kongruensklasser bildar en grupp, i detta fall den cykliska gruppen av ordning fyra, som har antingen 3 eller 7 som en (multiplikativ) generator. De representerade kongruensklasserna bildar gruppen av enheter i ringen $\mathbb {Z} /10\mathbb {Z}$ . Dessa kongruensklasser är just de som har modulära multiplikativa inverser.

Beräkning

Utökad euklidisk algoritm

Huvudartikel: Utökad euklidisk algoritm

En modulär multiplikativ invers av en modulom kan hittas genom att använda den utökade euklidiska algoritmen .

Den euklidiska algoritmen bestämmer den största gemensamma divisorn (gcd) av två heltal, säg a och m . Om a har en multiplikativ invers modulo m måste denna gcd vara 1. Den sista av flera ekvationer som produceras av algoritmen kan lösas för denna gcd. Sedan, med hjälp av en metod som kallas "back substitution", kan ett uttryck som förbinder de ursprungliga parametrarna och denna gcd erhållas. Med andra ord kan heltal x och y hittas för att uppfylla Bézouts identitet ,

$ax+my=\gcd(a,m)=1.$

Omskrivet, det här

$ax-1=(-y)m,$

det är,

$ax\equiv 1{\pmod {m}},$

så en modulär multiplikativ invers av a har beräknats. En mer effektiv version av algoritmen är den utökade euklidiska algoritmen, som genom att använda hjälpekvationer reducerar två pass genom algoritmen (återbyte kan ses som att passera genom algoritmen omvänt) till bara en.

I big O-notation körs denna algoritm i tiden O(log ² ( m )) , förutsatt att | en | < m , och anses vara mycket snabb och generellt sett mer effektiv än dess alternativ, exponentiering.

Använder Eulers teorem

Som ett alternativ till den utökade euklidiska algoritmen kan Eulers teorem användas för att beräkna modulära inverser.

Enligt Eulers teorem , om a är coprime till m , det vill säga gcd( a , m ) = 1 , då

$a^{\phi (m)}\equiv 1{\pmod {m}},$

där $\phi$ är Eulers totientfunktion . Detta följer av det faktum att a tillhör den multiplikativa gruppen $(\mathbb {Z} /m\mathbb {Z} )$ ^× om och endast om a är coprime till m . Därför kan en modulär multiplikativ invers hittas direkt:

$a^{\phi (m)-1}\equiv a^{-1}{\pmod {m}}.$

I specialfallet där m är ett primtal, $\phi (m)=m-1$ och en modulär invers ges av

$a^{-1}\equiv a^{m-2}{\pmod {m}}.$

Denna metod är i allmänhet långsammare än den utökade euklidiska algoritmen, men används ibland när en implementering för modulär exponentiering redan är tillgänglig. Några nackdelar med denna metod inkluderar:

• Värdet $\phi (m)$ måste vara känt och den mest effektiva kända beräkningen kräver m :s faktorisering . Faktorisering anses allmänt vara ett beräkningsmässigt svårt problem. ${\displaystyle \phi (m)} är$ dock enkelt när primtalsfaktoriseringen av m är känd.
• Den relativa kostnaden för exponentiering. Även om det kan implementeras mer effektivt med hjälp av modulär exponentiering , när stora värden på m är involverade, beräknas detta mest effektivt med Montgomery-reduktionsmetoden . Denna algoritm i sig kräver en modulär invers mod m , vilket är vad som skulle beräknas i första hand. Utan Montgomery-metoden är den vanliga binära exponentieringen , som kräver division mod m vid varje steg, en långsam operation när m är stor.

En anmärkningsvärd fördel med den här tekniken är att det inte finns några villkorade grenar som beror på värdet av a , och därför kan värdet på a , som kan vara en viktig hemlighet i kryptografi med publik nyckel , skyddas från sidokanalattacker . Av denna anledning använder standardimplementeringen av Curve25519 denna teknik för att beräkna en invers.

Flera inverser

Det är möjligt att beräkna inversen av multipla tal ai _. , modulo a common m , med ett enda anrop av den euklidiska algoritmen och tre multiplikationer per ytterligare ingång Grundidén är att bilda produkten av alla a i _, invertera det och sedan multiplicera med a _j för alla j ≠ i för att bara lämna det önskade a
⁻¹ _i .

Mer specifikt är algoritmen (all aritmetik utförd modulo m ):

1. Beräkna prefixprodukterna ${\textstyle b_{i}=\prod _{j=1}^{i}a_{j}=a_{i} b_{i-1}}$ för alla i ≤ n .
2. Beräkna b
   ⁻¹ _n med valfri tillgänglig algoritm.
3. För i från n ner till 2, beräkna
   • a
     ⁻¹ _i = b
     ⁻¹ _i b _{i −1} och
   • b
     ⁻¹ _{i −1} = b
     ⁻¹ _i a _i .
4. Slutligen, a
   ⁻¹ ₁ = b
   ⁻¹ ₁ .

Det är möjligt att utföra multiplikationerna i en trädstruktur snarare än linjärt för att utnyttja parallell beräkning .

Ansökningar

Att hitta en modulär multiplikativ invers har många tillämpningar i algoritmer som bygger på teorin om modulär aritmetik. Till exempel, i kryptografi tillåter användningen av modulär aritmetik att vissa operationer kan utföras snabbare och med färre lagringskrav, medan andra operationer blir svårare. Båda dessa funktioner kan med fördel användas. I synnerhet, i RSA-algoritmen, görs kryptering och dekryptering av ett meddelande med användning av ett par tal som är multiplikativa inverser med avseende på en noggrant utvald modul. Ett av dessa nummer är offentligt och kan användas i en snabb krypteringsprocedure, medan det andra, som används i dekrypteringsproceduren, hålls dolt. Att bestämma det dolda numret från det offentliga numret anses vara beräkningsmässigt omöjligt och det är detta som gör att systemet fungerar för att säkerställa integritet.

Som ett annat exempel i ett annat sammanhang, betrakta det exakta divisionsproblemet inom datavetenskap där du har en lista med tal med udda ordstorlek som var och en är delbar med k och du vill dividera dem alla med k . En lösning är följande:

1. Använd den utökade euklidiska algoritmen för att beräkna k ⁻¹ , den modulära multiplikativa inversen av k mod 2 ^w , där w är antalet bitar i ett ord. Denna invers kommer att existera eftersom talen är udda och modulen inte har några udda faktorer.
2. För varje tal i listan, multiplicera det med k ⁻¹ och ta det minst signifikanta ordet av resultatet.

På många maskiner, särskilt de utan hårdvarustöd för division, är division en långsammare operation än multiplikation, så detta tillvägagångssätt kan ge en avsevärd snabbhet. Det första steget är relativt långsamt men behöver bara göras en gång.

Modulära multiplikativa inverser används för att erhålla en lösning av ett system av linjära kongruenser som garanteras av den kinesiska restsatsen .

Till exempel systemet

X ≡ 4 (mod 5)

X ≡ 4 (mod 7)

X ≡ 6 (mod 11)

har gemensamma lösningar eftersom 5,7 och 11 är parvis coprime . En lösning ges av

X = t ₁ (7 × 11) × 4 + t ₂ (5 × 11) × 4 + t ₃ (5 × 7) × 6

var

t ₁ = 3 är den modulära multiplikativa inversen av 7 × 11 (mod 5),

t ₂ = 6 är den modulära multiplikativa inversen av 5 × 11 (mod 7) och

t ₃ = 6 är den modulära multiplikativa inversen av 5 × 7 ( mod 11).

Således,

X = 3 × (7 × 11) × 4 + 6 × (5 × 11) × 4 + 6 × (5 × 7) × 6 = 3504

och i sin unika reducerade form

X ≡ 3504 ≡ 39 (mod 385)

eftersom 385 är LCM på 5,7 och 11.

Dessutom är den modulära multiplikativa inversen framträdande i definitionen av Kloosterman-summan .

Se även

• Inversiv kongruentialgenerator – en pseudo-slumptalsgenerator som använder modulära multiplikativa inverser
• Rationell rekonstruktion (matematik)

Anteckningar

•   Irland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (2:a upplagan), Springer-Verlag, ISBN 0-387-97329-X
•   Rosen, Kenneth H. (1993), Elementary Number Theory and its Applications (3:e upplagan), Addison-Wesley, ISBN 978-0-201-57889-8
•   Schumacher, Carol (1996). Kapitel Noll: Grundläggande begrepp i abstrakt matematik . Addison-Wesley. ISBN 0-201-82653-4 .
•   Trappe, Wade; Washington, Lawrence C. (2006), Introduktion till kryptografi med kodningsteori (2:a upplagan), Prentice-Hall, ISBN 978-0-13-186239-5

externa länkar

• Weisstein, Eric W. "Modular Inverse" . MathWorld .
• Guevara Vasquez, Fernando ger ett löst exempel på att lösa den modulo multiplikativa inversen med Euklids algoritm