Modulo ömsesidigt nummer

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 20 april 2022; kontroller kräver 18 redigeringar .

Det inversa modulo ett heltal a är ett heltal x så att produktaxeln är kongruent med 1 modulo m [1] . I standard modulär aritmetisk notation skrivs denna ekvivalens som:

ax\equiv 1{\pmod {m)),

vilket är ett förkortat sätt att säga att m delar (utan rest) värdet ax − 1 , eller, för att uttrycka det på ett annat sätt, resten när ax divideras med heltal m är 1. Om a har en invers modulo m , då finns det ett oändligt antal lösningar på denna ekvivalens , som utgör restklassen för denna modul. Dessutom kommer varje heltal som är ekvivalent med a (det vill säga från ekvivalensklassen a ) att ha vilket element som helst av ekvivalensklassen x som sin invers. Med hjälp av notationen för en ekvivalensklass som innehåller , kan ovanstående påstående skrivas på följande sätt: det inversa elementet modulo en ekvivalensklass är en ekvivalensklass så att $\overline {w}$ $w$ ${\overline {a}}$ $\overline{x}$

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

där symbol betyder multiplikation av ekvivalensklasser modulo m [2] . Denna typ av notation representerar en analog till det vanliga konceptet med det inversa talet i uppsättningen av rationella eller reella tal , om vi ersätter tal med ekvivalensklasser och korrekt definierar binära operationer . $\cdot _{m}$

Den grundläggande användningen av denna operation är att lösa en linjär ekvivalens av formen:

ax\equiv b{\pmod {m)).

Att hitta den modulära inversen har praktiska tillämpningar inom kryptografiområdet , såsom kryptosystemet med publik nyckel och RSA-algoritmen [3] [4] [5] . Fördelen med att implementera dessa applikationer är att det finns en mycket snabb algoritm ( Extended Euclid's algorithm ) som kan användas för att beräkna modulära inverser.

Modulär aritmetik

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

a\equiv b{\pmod {m)).

Detta är en ekvivalensrelation på mängden heltal , och ekvivalensklasserna kallas restklasser modulo m . Låt beteckna en ekvivalensklass som innehåller ett heltal a [6] , då $\mathbb {Z}$ ${\overline {a}}$

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

Linjär jämförelse är en modulo-jämförelse av formen

ax\equiv b{\pmod {m)).

Till skillnad från linjära ekvationer i heltal kan en linjär jämförelse ha noll, en eller flera lösningar. Om x är en lösning på en linjär jämförelse, så är vilket element som helst av också en lösning, så när vi talar om antalet lösningar till en linjär jämförelse menar vi antalet olika ekvivalensklasser som dessa lösningar innehåller. $\overline{x}$

Om d är den största gemensamma delaren för a och m , så har den linjära jämförelsen lösningar om och endast om d delar b . Om d delar b , så finns det exakt d lösningar [7] . $ax\equiv b{\pmod {m))$

Modulo reciprocal av ett heltal a modulo m är lösningen på den linjära jämförelsen

ax\equiv 1{\pmod {m)).

Det sades tidigare att en lösning existerar om och bara om den största gemensamma delaren för a och m är 1, det vill säga a och m måste vara relativt primtal . Dessutom, om detta villkor är uppfyllt, finns det exakt en lösning, det vill säga om det finns en lösning är den modulära inversen unik [8] .

Om den har en lösning betecknas den ofta på följande sätt $ax\equiv 1{\pmod {m))$

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

detta kan dock betraktas som ett missbruk av , eftersom det kan misstolkas som en normal reciprok (som, till skillnad från modulus reciprocal, inte är ett heltal förutom när a är 1 eller -1). Notationen skulle vara acceptabel om a tolkades som notationen för restklassen , eftersom det inversa elementet i restklassen återigen är en restklass med multiplikationsoperationen definierad i nästa avsnitt. $a$ ${\overline {a}}$

Heltal modulo m

Ekvivalensrelationen modulo m delar upp mängden heltal i m ekvivalensklasser. Operationerna för addition och multiplikation kan definieras på dessa objekt enligt följande: för addition eller multiplikation av ekvivalensklasser väljs först representanter för dessa klasser på något sätt, sedan utförs den vanliga operationen på de valda heltalen och slutligen resultatet av operationen ligger i restklassen, som är resultatet av operationen på klasserna . I symbolisk form, med och representerande operationer på restklasser, kan dessa definitioner skrivas som ${\displaystyle +_{m))$ $\cdot _{m}$

{\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å valet av representanter).

Restklasserna modulo m bildar med dessa två operationer en ring , kallad ringen av heltal modulo m . Det finns flera notationer som används för dessa algebraiska enheter, den vanligaste är eller , men vissa elementära läroböcker och applikationer använder den förenklade notationen såvida de inte står i konflikt med andra algebraiska enheter. $\mathbb{Z}/m\mathbb{Z}$ $\mathbb {Z} /m$ $\mathbb {Z} _{m}$

Restklasser av heltal modulo m var traditionellt kända som restklasser mod m , vilket återspeglar det faktum att alla element i en ekvivalensklass har samma återstod när de divideras med m . Varje uppsättning m heltal som väljs från olika klasser av rester modulo m kallas ett komplett system av rester modulo m [9] . Dividering med en kolumn visar att mängden heltal {0, 1, 2, ..., m − 1} bildar ett komplett system av rester modulo m , känt som det minsta systemet av rester modulo m . När man arbetar med aritmetiska problem är det ibland bekvämare att arbeta med hela systemet av rester och använda ekvivalensspråket, medan det i andra fall är mer bekvämt att titta i termer av ringekvivalensklasser [10] . $\mathbb{Z}/m\mathbb{Z}$

Den multiplikativa gruppen av restringen

Inte varje element i hela systemet av rester modulo m har ett inverst element, till exempel har noll ingen invers. Efter att ha tagit bort elementen i det kompletta systemet av rester som inte är relativt prime till m , har de återstående elementen, som kallas det reducerade systemet av rester , alla inverser. Antalet element i det reducerade systemet av rester är , där är Euler-funktionen , det vill säga antalet positiva heltal mindre än m som är relativt primtal till m . $\phi (m)$ $\phi$

I en ring med en generell enhet har inte alla element en invers , och de som gör det kallas invertible . Eftersom produkten av inverterbara element är inverterbar, bildar de inverterbara elementen i en ring en grupp , gruppen av inverterbara element i en ring , och denna grupp betecknas ofta som om R är namnet på en ring. Gruppen av inverterbara element i ringen av heltal modulo m kallas den multiplikativa gruppen av heltal modulo m , och den är isomorf till det reducerade systemet av rester. I synnerhet är dess ordning (storlek) . ${\displaystyle R^{\times ))$ $\phi (m)$

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

Exempel

För att illustrera definitionerna ovan, överväg exemplet med siffror modulo 10.

Två tal är ekvivalenta med 10 om och endast om deras skillnad är delbar med 10, till exempel

32\equiv 12{\pmod {10}}

eftersom 10 delar 32 − 12 = 20,

111\equiv 1{\pmod {10}}

eftersom 10 delar 111 − 1 = 110.

Några av restklasserna för denna modulo är:

{\displaystyle {\overline {0}}=\{\cdots ,-20,-10,0,10,20,\cdots \))

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

{\displaystyle {\overline {5}}=\{\cdots ,-15,-5,5,15,25,\cdots \))

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

Linjär jämförelse har ingen lösning eftersom heltal som är kongruenta med 5 (dvs. de i ) alla är udda, medan 4x alla är jämna. Den linjära jämförelsen har dock två lösningar, nämligen och . gcd(4, 10) = 2 och 2 delar inte 5 men delar 6. $4x\equiv 5{\pmod {10}}$ ${\overline {5}}$ $4x\equiv 6{\pmod {10}}$ $x=4$ $x=9$

Eftersom gcd(3, 10) = 1 kommer den linjära jämförelsen att ha lösningar, det vill säga modulo reciprocal av 3 modulo 10 kommer att existera. 7 uppfyller denna ekvation (21 − 1 = 20). Men även andra heltal uppfyller denna ekvation, såsom 17 och −3 (eftersom 3(17) − 1 = 50 och 3(−3) − 1 = −10). I synnerhet kommer alla heltal från att uppfylla ekvationen, eftersom dessa tal är av formen 7 + 10 r för vissa r och det är tydligt att $3x\equiv 1{\pmod {10}}$ ${\overline {7))$

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

är delbart med 10. Denna ekvation har bara en klass av rester som lösningar. Lösningen i detta fall kan erhållas helt enkelt genom uppräkning av möjliga klasser, men systematiska algoritmer behövs för att få en lösning för stora moduler, och de kommer att presenteras i följande avsnitt.

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

Ett komplett restsystem modulo 10 kan vara uppsättningen {10, −9, 2, 13, 24, −15, 26, 37, 8, 9}, där varje heltal tillhör sin egen restklass modulo 10. Det minimala restsystemet modulo 10 fungerar som {0, 1, 2, ..., 9}. Det reducerade systemet av rester modulo 10 kan vara {1, 3, 7, 9}. Produkten av vilka två restklasser som helst som representeras av dessa siffror är återigen en av dessa fyra klasser. Härav följer att dessa fyra restklasser bildar en grupp, i detta fall en cyklisk grupp av ordning 4, med generator 3 eller 7. De presenterade restklasserna bildar gruppen av inverterbara element i ringen . Dessa restklasser är exakt de som har modulo reciproka. $\mathbb {Z} /10\mathbb {Z}$

Beräkning

Utökad Euklids algoritm

Modulo- inversen av en modulo m kan hittas med den utökade euklidiska algoritmen.

Euklids algoritm bestämmer den största gemensamma divisorn (gcd) av två heltal, säg a och m . Om a har den inversa modulom m måste denna gcd vara lika med 1. De sista få likheterna som erhållits under driften av algoritmen kan lösas för att hitta gcd. Sedan, genom att använda metoden "omvänd substitution", kan ett uttryck erhållas som länkar de ursprungliga parametrarna och GCD. Med andra ord kan heltal x och y hittas som uppfyller Bézouts likhet ,

ax+my={\text{gcd }}(a,m)=1.

Låt oss skriva om det enligt följande

ax-1=(-y)m,

det är,

ax\equiv 1{\pmod {m)),

och modulo reciproka för a beräknas. En mer effektiv version är den utökade euklidiska algoritmen, som reducerar två pass av algoritmen (tillbaka substitution kan tänkas gå igenom algoritmen i omvänd ordning) till en som använder ytterligare likheter.

I big O-notation körs denna algoritm i tid under antagandet att , och anses vara mycket snabb. Det är vanligtvis mer effektivt än den alternativa exponentiella algoritmen. $O(\log(m)^{2})$ $|a|<m$

Använder Eulers teorem

Som ett alternativ till den utökade euklidiska algoritmen för att beräkna det modulära inverselementet kan man överväga användningen av Eulers sats [11] .

Enligt Eulers teorem , om a är relativt primtal till m , dvs gcd( a , m ) = 1, då

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

var är Euler-funktionen . Detta följer av att a tillhör den multiplikativa gruppen om och endast om a är relativt primtal till m . Så den modulära inversen kan hittas direkt: $\phi$ ${\displaystyle (\mathbb {Z} /m\mathbb {Z} )^{\times ))$

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

I det speciella fallet där m är primtal och den modulära inversen ges av $\phi (m)=m-1$

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 om en implementering för modulär exponentiering redan är tillgänglig. Nackdelar med denna metod:

Värdet måste vara känt, och den mest effektiva beräkningsmetoden kräver m expansioner . Nedbrytning är välkänt som ett problem där beräkningar tar upp det mesta av lösningens komplexitet. Det kan dock beräknas direkt om nedbrytningen i primtalsfaktorer av talet m är känd . $\phi (m)$ $\phi (m)$
Relativt hög kostnad för exponentiering. Även om detta kan göras mer effektivt med modulär konstruktion , för stora värden på m , är Montgomery-algoritmmetoden mest effektiv . Denna algoritm i sig kräver beräkning av den inversa modulom . Utan Montgomerys algoritm är den vanliga binära exponentieringsalgoritmen , som kräver modulo m vid varje steg, en långsam operation för stora m .

Den anmärkningsvärda fördelen med den här tekniken är att det inte finns några villkorade grenar som är beroende av värdet av a , och därför kan värdet av a , som kan vara en viktig hemlighet i kryptosystem med offentlig nyckel , skyddas från sidokanalattacker . Av denna anledning använder standardimplementeringen av Curve25519 den inversa elementberäkningstekniken.

Beräknar flera inverser

Det är möjligt att beräkna reciproken av flera tal modulom genom att använda ett pass av Euklids algoritm och tre multiplikationer för varje ytterligare ingångsnummer [12] . Grundidén är att bilda allt , vända det och sedan multiplicera med för alla , lämnar bara . $a_{i}$ $a_{i}$ $a_{j}$ $j\neq i$ ${\displaystyle a_{i}^{-1))$

Algoritm (all aritmetik görs modulo m ):

Beräkna prefixprodukter för alla . ${\textstyle b_{i}=\prod _{j=1}^{i}a_{j}=a_{i}b_{i-1))$ $i\leqslant n$
Beräkna med någon tillgänglig algoritm. ${\displaystyle b_{n}^{-1))$
För i från n till 2 räknar vi
- ${\displaystyle a_{i}^{-1}=b_{i}^{-1}b_{i-1))$ och
- ${\displaystyle b_{i-1}^{-1}=b_{i}^{-1}a_{i))$ .
Slutligen ,. ${\displaystyle a_{1}^{-1}=b_{1}^{-1))$

Det är möjligt att implementera multiplikation i form av en trädstruktur, snarare än en linjär, för att säkerställa parallelliteten i beräkningarna .

Applikationer

Sökandet efter den modulära inversen har många tillämpningar i algoritmer baserade 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 mindre minneskrav, medan andra operationer blir svårare att utföra [13] . Båda dessa egenskaper kan användas för gott. I synnerhet i RSA- algoritmen görs kryptering och den omvända kommunikationsprocessen med hjälp av ett par siffror som är ömsesidiga i förhållande till varandra i någon noggrant vald modulo. Ett av dessa nummer är offentligt och kan användas i snabbkrypteringsproceduren, medan det andra numret används i dekrypteringsproceduren och avslöjas inte. Att bestämma en dold nyckel från en offentlig nyckel anses vara en omöjlig uppgift, eftersom dess lösning kräver mer datorkraft än det finns på jorden, vilket skyddar mot obehörig åtkomst [14] .

Som en annan användning i ett annat sammanhang, överväg det exakta divisionsproblemet i datorer, där du får en lista med udda tal i ordstorlek på dator, som vart och ett är delbart med k , och du måste dividera dem med k . En lösning är följande:

Vi använder den utökade euklidiska algoritmen för att beräkna , den modulära inversen av , där w är lika med antalet bitar i ordet. Detta omvända existerar, eftersom alla tal är udda, och resterna anses vara modulo, som inte har några udda delare. $k^{{-1}}$ ${\displaystyle k{\pmod {2^{w))))$
Vi multiplicerar varje nummer i listan med och väljer de minst signifikanta bitarna av resultatet (det vill säga vi kasserar alla bitar utanför datorordet). $k^{{-1}}$

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 resultera i en betydande hastighetsökning. Det första steget är relativt långsamt, men det behöver bara göras en gång.

Modulära reciproka används för att få en lösning på ett system av linjära jämförelser, vilket garanteras av den kinesiska restsatsen .

Till exempel systemet

{\begin{cases}X\equiv 4{\pmod {5}}\\X\equiv 4{\pmod {7}}\\X\equiv 6{\pmod {11}}\\\end {fall}}

har en generell lösning eftersom 5, 7 och 11 är parvis coprime . Lösningen ges av formeln

X=t_{1}(7\ gånger 11)\ gånger 4+t_{2}(5\ gånger 11)\ gånger 4+t_{3}(5\ gånger 7)\ gånger 6

var

t_{1}=3

modulär omvänd ,

7\times 11{\pmod {5}}

t_{2}=6

modulär omvänd ,

5\times 11{\pmod {7}}

t_{3}=6

modulär omvänd .

5\times 7{\pmod {11}}

Sedan,

X=3\ gånger (7\ gånger 11)\ gånger 4+6\ gånger (5\ gånger 11)\ gånger 4+6\ gånger (5\ gånger 7)\ gånger 6=3504

och i den angivna formen

X\equiv 3504\equiv 39{\pmod {385}}

eftersom 385 är den minsta gemensamma multipeln av 5, 7 och 11.

Den modulära inversen är framträdande i definitionen av Kloosterman-summor .

Se även

Den inversa kongruentialmetoden är en algoritm för att generera pseudoslumptal som använder modulo inversa tal.
Återvinning av ett rationellt tal modulo it

Anteckningar

↑ Rosen, 1993 , sid. 132.
↑ Schumacher, 1996 , sid. 88.
↑ Stinson, 1995 , sid. 124–128.
↑ Trappe, Washington, 2006 , sid. 164-169.
↑ Moriarty, K.; Kaliski, B.; Jonsson, J.; Rusch, A. PKCS #1: RSA-krypteringsspecifikationer version 2.2 . Internet Engineering Task Force RFC 8017 . Internet Engineering Task Force (2016). Hämtad 21 januari 2017. Arkiverad från originalet 12 december 2018. (obestämd)
↑ Andra beteckningar används ofta, inklusive [ a ] och [ a ] m .
↑ Irland, Rosen, 1990 , sid. 32.
↑ Shoup, 2005 , sid. 15 Sats 2.4.
↑ Rosen, 1993 , sid. 121.
↑ Irland, Rosen, 1990 , sid. 31.
↑ Koshy, 2007 , sid. 346.
↑ Brent, Zimmermann, 2010 , sid. 67–68.
↑ Trappe, Washington, 2006 , sid. 167.
↑ Trappe, Washington, 2006 , sid. 165.

Litteratur

Douglas R. Stinson. Kryptografi / teori och praktik. - CRC Press, 1995. - ISBN 0-8493-8521-0 .
Victor butik. En beräkningsintroduktion till talteori och algebra . - Cambridge University Press, 2005. - ISBN 9780521851541 .
Thomas Koshy. Elementär talteori med tillämpningar . — 2:a upplagan. - Academic Press, 2007. - ISBN 978-0-12-372487-8 .
Richard P. Brent , Paul Zimmermann . §2.5.1 Flera inversioner samtidigt // Elementär talteori med tillämpningar. Modern datoraritmetik . - Cambridge University Press, 2010. - V. 18. - (Cambridge Monographs on Computational and Applied Mathematics). — ISBN 978-0-521-19469-3 .

Kenneth Irland, Michael Rosen. En klassisk introduktion till modern talteori. — 2:a. - Springer-Verlag, 1990. - ISBN 0-387-97329-X .
- C. Irland, M. Rosen. Klassisk introduktion till modern talteori / Översatt från engelska av S. P. Demushkin. - Moskva: Mir, 1987.

Kenneth H. Rosen. Elementär talteori och dess tillämpningar. — 3:a. - Addison-Wesley, 1993. - ISBN 978-0-201-57889-8 .
Carol Schumacher. Kapitel Noll: Grundläggande begrepp i abstrakt matematik . - Addison-Wesley, 1996. - ISBN 0-201-82653-4 .
Wade Trappe, Lawrence C. Washington. Introduktion till kryptografi med kodningsteori. — 2:a. - Prentice-Hall, 2006. - ISBN 978-0-13-186239-5 .

Länkar

Weisstein, Eric W. Modular Inverse (engelska) på Wolfram MathWorld- webbplatsen .
Guevara Vasquez, Fernando ger ett exempel på att lösa den inversa modulo med den euklidiska algoritmen.