Biderketarekiko alderantzizko modular

Biderketarekiko alderantzizko modularra aritmetika modularrareko eragiketa bat da. ${\displaystyle n}$ zenbaki oso baten biderketarekiko alderantzizkoa modulu ${\displaystyle p}$ beste ${\displaystyle m}$ zenbaki oso bat da non:

${\displaystyle m\,n\equiv 1{\pmod {p}},}$

hau da, ${\displaystyle mn}$ biderketa 1-arekin kongruentea den (modulu ${\displaystyle p}$). ${\displaystyle m}$ zenbakia ${\displaystyle n}$ zenbakiaren alderantzizkoa modulu ${\displaystyle p}$ dela horrela adierazten da:

${\displaystyle n^{-1}\equiv m{\pmod {p}}.}$

Biderketarekiko alderantzizko modularra ez da beti existitzen. ${\displaystyle n}$-ren alderantzizko modularra existitzen da baldin eta soilik baldin ${\displaystyle n}$ eta ${\displaystyle p}$ elkarrekiko lehenak badira, hau da, ${\displaystyle zkh(n,p)=1}$ bada.

${\displaystyle n}$ zenbakiaren alderantzizkoa modulu ${\displaystyle n}$ existitzen denean, orduan beste zenbaki bat ${\displaystyle n}$ balioaz zatitzearen eragiketa (modulu ${\displaystyle p}$) defini daiteke; zenbaki bat ${\displaystyle n}$ balioaz zatitzea ${\displaystyle n^{-1}}$ alderantzizko modularraz biderkatzea da. ${\displaystyle p}$ zenbaki lehena bada, orduan zenbaki guztiak dira alderantzikagarriak, ${\displaystyle 0}$-a izan ezik.

Biderketaren alderantzizko modularra ez da bakarra. Normalean, ${\displaystyle n}$-ren alderantzizkotzat (modulu ${\displaystyle p}$) hartzen den ${\displaystyle m}$ zenbakia aukera guztien artean txikiena den zenbaki arrunta izaten da.

Adibidea:

Demagun ${\displaystyle n=3}$ zenbakiaren alderantzizkoa modulu ${\displaystyle p=11}$ kalkulatu nahi dela,

${\displaystyle m\equiv 3^{-1}{\pmod {11}}}$.

${\displaystyle mn\equiv 1{\pmod {p}}}$ betetzen duen ${\displaystyle m}$ zenbakia aurkitu nahi da, hau da,

${\displaystyle 3^{-1}\cdot 3\equiv 1{\pmod {11}}}$

beteko duena. Kongruentzia hori betetzen duen zenbaki arrunt txikiena ${\displaystyle 4}$ da (${\displaystyle \mathbb {Z} _{11}}$ partizioko balioa da). Horrela egiazta daiteke:

${\displaystyle 4=3^{-1}{\pmod {11}}\quad \rightarrow \quad 4\cdot 3\equiv 1{\pmod {11}}\quad \rightarrow \quad 12\equiv 1{\pmod {11}}}$

Esan bezala, ${\displaystyle m=4}$ ez da aukera bakarra, ${\displaystyle 4}$-ri ${\displaystyle 11}$-ren multiploak gehituz, hau da, ${\displaystyle 4+(11\cdot z),\ z\in \mathbb {Z} ,}$ beste ${\displaystyle 3^{-1}{\pmod {11}}}$ balio posibleak lor daitezke. Horrela, {..., −18, −7, 15, 26, ...} multzoko balio guztietarako ${\displaystyle m\cdot 3\equiv 1{\pmod {11}}}$ betetzen da.

Euklidesen algoritmo hedatua erabiliz ${\displaystyle n}$-ren biderketarekiko alderantzikoa modulu ${\displaystyle p}$ kalkula daiteke.

Esan dugunez, ${\displaystyle n}$-ren alderantzikoa modulu ${\displaystyle p}$

${\displaystyle xn\equiv 1{\pmod {p}}}$

betetzen duen ${\displaystyle x}$ zenbaki osoa da, ${\displaystyle p|xn-1}$ betetzen da, hau da, ${\displaystyle p}$ balioak ${\displaystyle xn-1}$ zatitzen du. Hortaz,

${\displaystyle \exists k\in \mathbb {Z} \quad }$ non ${\displaystyle \quad xn-1=kp.\,}$

Beste era batean idatzita:

${\displaystyle xn-kp=1.\,}$

Euklidesen algoritmo hedatuak ebazten duen problema, hain zuzen ere, hori da. ${\displaystyle n}$ eta ${\displaystyle p}$ zenbaki osoak izanik, ${\displaystyle zkh(n,p)}$ zatitzaile komunetako handiena eta

${\displaystyle xn+yp=zkh(n,p)}$

berdintza betetzen duten ${\displaystyle x}$ eta ${\displaystyle y}$ zenbaki osoak kalkula daitezke. Kasu honetan ${\displaystyle zkh(n,p)=1}$ aurrez ezarrita dator. Baldin ${\displaystyle zkh(n,p)\neq 1}$ bada, orduan ${\displaystyle n}$-ren alderantzikoa modulu ${\displaystyle p}$ ez da existitzen.

${\displaystyle |n|<p}$ bada, algoritmoa ${\displaystyle O(log(p)^{2})}$ denboran exekutatuko da.

Adibidea

${\displaystyle n=117}$ eta ${\displaystyle p=244}$ izanik, ${\displaystyle 117}$-ren alderantzizkoa modulu ${\displaystyle 244}$ horrela kalkulatzen da. Hasteko, existitzen dela egiaztatu behar da, hau da, ${\displaystyle zkh(n,p)=1}$ dela. Horretarako, Euklidesen algoritmoa aplikatuko dugu. Ondoren, ${\displaystyle zkh(n,p)}$ kalkulatzeko egindako eragiketetatik ${\displaystyle n^{-1}}$ lortuko dugu:

1. ${\displaystyle |n|<p}$ denez, ${\displaystyle p=qn+r}$ idatz daiteke. Hau da, ${\displaystyle 244=2\cdot 117+10}$. Hondarra askatuz: ${\displaystyle 10=224-2\cdot 117}$
2. ${\displaystyle 117>10}$ denez, ${\displaystyle 117=11\cdot 10+7}$. Hondarra askatuz: ${\displaystyle 7=117-11\cdot 10}$
3. ${\displaystyle 10>7}$ denez, ${\displaystyle 10=1\cdot 7+3}$. Hondarra askatuz: ${\displaystyle 3=10-1\cdot 7}$
4. ${\displaystyle 7>3}$ denez, ${\displaystyle 7=2\cdot 3+1}$. Hondarra askatuz: ${\displaystyle 1=7-2\cdot 3}$
5. ${\displaystyle 3>1}$ denez, ${\displaystyle 3=1\cdot 3+0}$. Hortaz, ${\displaystyle zkh(244,117)=1}$ betetzen denez, ${\displaystyle 244}$ eta ${\displaystyle 117}$ elkarrekiko lehenak dira eta ondorioz, bilatzen dugun alderantzizko modularra existitzen da.
6. Koefizienteen kalkulurako abiapuntua 4. urratseko ${\displaystyle 1=7-2\cdot 3}$ adierazpena da. Ondorengo urratsetan aurreko urratsetako hondarren adierazpenak ordezkatu behar dira.
7. 3. urratseko hondarra 6. urratseko ekuazioan txertatuz: ${\displaystyle 1=7-2\cdot (10-1\cdot 7)}$, hau da, ${\displaystyle 1=2\cdot 10+3\cdot 7}$.
8. 2. urratseko hondarra 7. urratseko ekuazioan txertatuz: ${\displaystyle 1=2\cdot 10+3\cdot (117-11\cdot 10)}$, hau da, ${\displaystyle 1=3\cdot 117-35\cdot 10}$.
9. 1. urratseko hondarra 8. urratseko ekuazioan txertatuz: ${\displaystyle 1=3\cdot 117-35\cdot (244-2\cdot 117)}$, hau da, ${\displaystyle 1=35\cdot 244+73\cdot 117}$. Esan dezakegu ${\displaystyle n^{-1}=73}$ dela, ${\displaystyle 1=x\cdot n+k\cdot p}$ ekuazioa kontuan hartuz.
10. ${\displaystyle n^{-1}}$ negatiboa bada, ${\displaystyle n^{-1}}$-en alderantzizkoa ${\displaystyle n^{-1}+p}$ izango da.

Biderketarekiko alderantzizko modularrak erabilera ugari ditu algoritmoetan, zenbaki teoria-rekin erlazioa dutenetan bereziki, algoritmo horietako askoren oinarrian aritmetika modularraren teoria dagoelako.

Makina askok ez daukate zatiketa eragiketa egiteko hardware berezirik eta ondorioz, zatiketaren eragiketa biderketarena baino motelago exekutatzen da. Alderantzizko modularraren erabilerarekin kalkuluak azkarrago egitea lortzen da.

//Calculador de inversos modulares (CIM), Arget-ek sortua
//Biderketarekiko alderantzizko modularraren kalkulua.
//Erabilera: cim a m
//(cim) programak (a * b)(mod m) = 1 betetzen duen b aurkituko du.
//Exekutatzean ez bada emaitzik itzultzen, ‘a’ balioak ez du alderantzizkorik modulu ‘m’.
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char** argv)
{
    if(argc == 1)exit(-1);

    int b, // (a * b)(mod m)-n esprezioko b balioa gordeko da
        x, //eragiketaren emaitza gordeko da
        a = atoi(argv[1]), //a gorde
        m = atoi(argv[2]); //m gorde

    for(b = 0; b < m; b++)
    {
        x = (a * b) % m;
        if(x == 1)
            printf("%i", b);
    }
    return 0;
}

    //JLCY-k sortua,  (17-1-2016) 
    // Bezout-en lema aplikatuz
    //zkh(z,p) lortzen da euklidesen algoritmoa erabiliz
    //zkh(a,p)=1 bada, "a" eta "p" elkarrekiko lehenak dira; "a"-ren alderantzizkoa modulu "m" existitzen da.
    public void Inverso(int a,int m)
    {
        int c1=1,c2=-1*(m/a);//a-ren eta b-ren koefizienteak hurrenez hurren
        int t1=0,t2=1;
        int r=m%a;//hondarra
        int x=a,y=r,c;
        while(r!=0)
        {
        c= x/y;//zatidura
        r= x%y;//hondarra
        //koefizienteen aldi baterako balioak gordetzen dira
        c1*=-1*c;
        c2*=-1*c;
        //aurreko korritzea batzen da
        c1+=t1;
        c2+=t2;
        //korritzea eguneratzen da
        t1=-1*(c1-t1)/c;
        t2=-1*(c2-t2)/c;
        x=y;
        y=r;
        }
      if(x==1)//aurreko hondarra 1 bada, elkarrekiko lehenak dira eta alderantzizko existitzen da
            System.out.println(""+t2);
      else
            System.out.println("ez dago alderantzizkorik");
    }

• Datuak: Q2741788