Ik heb geen literatuur over de LR, maar de werking ervan volgt uit een aantal resultaten van de getaltheorie en algebra.
Hier een aantal aspecten van de LR:
[1] het cyclisch karakter van de LR:
Dit volgt uit de constructie van de LR: voor een priemgetal
\(p\) verdelen we alle getallen
\(n\;\; (1\le n \le p-1)\) over een rooster met hoogte
\(H\) en breedte
\(B\) (waarbij
\(H \cdot B = p-1\)).
Voor de linker kolom gebruikten we machten van
\(a \;\;(a^0=1, a, a^2, ... a^{H-1})\) en waarbij
de multiplicatieve orde van
\(a \mod p\) gelijk is aan
\(H\), notatie:
\(ord_p(a)=H\).
(Definitie: de multiplicatieve orde van
\(a \mod p\) = de kleinste
\(k \ge 1\) zodanig dat
\(a^k \equiv 1 \mod p\), dus
voor alle
\(i \;\; (1 \le i \le k-1)\) geldt:
\(a^i \not\equiv 1 \mod p\), zie bijvoorbeeld
https://en.wikipedia.org/wiki/Multiplicative_order)
Evenzo voor b en de breedte B van het rooster:
\(ord_p(b)=B\).
Omdat elke stap omhoog in het rooster een vermenigvuldiging is met a, en elke stap naar rechts een vermenigvuldiging met b, krijgen we nu voor elk getal
\(n \equiv a^i\cdot b^j \mod p\;\;\;(i,j \in \mathbb{Z})\) in het rooster:
\(n \equiv a^{i \mod H}\cdot b^{j \mod B} \mod p\)
immers:
- elke
\(i\) kunnen we schrijven als
\(i = q\cdot H + r\) waarbij
\(0\le r \le H-1\), dus
\(a^{i\mod H}= a^{q\cdot H + r \mod H}=a^{r\mod H}\)
- elke
\(j\) kunnen we schrijven als
\(j = s\cdot B + t\) waarbij
\(0\le t \le B-1\), dus
\(b^{j\mod B}= b^{d\cdot H + t \mod B}=b^{t\mod B}\)
zodat
\(n \equiv a^i\cdot b^j \equiv a^r\cdot b^t \mod p\) waarmee we n hebben teruggebracht naar het basisrooster.
Hier een plaatje van het mod 29 rooster uit mijn eerdere post (basisblok geel, kopieen in rood, groen en blauw):
en hier een plaatje met getallen, nu voor de mod 13 LR die jij hierboven gegeven hebt:
[2] Het zoeken van geschikte a en b:
De LR is een rechthoekig rooster met hoogte
\(H\) en breedte
\(B\) waarin de getallen 1 t/m p-1 staan.
Het aantal plaatsen in het rooster =
\(H\cdot B\) en dit moet gelijk zijn aan p-1:
\(H\cdot B = p-1\).
Hierdoor zijn
\(H\) en
\(B\) delers van p-1.
Hierboven hadden we ook al gezegd dat
\(H=ord_p(a)\) en
\(B=ord_p(b)\) moet zijn.
We mogen optimistisch zijn over de kans dat we voor een gegeven
\(p\) geschikte
\(a\) en
\(b\) kunnen vinden, want ook de multiplicatieve ordes zijn delers van p-1.
Dit volgt uit de stelling van Lagrange: de orde van
\(a \mod n\) is een deler van
\(\varphi(n)\)
(zie ook de wiki-pagina hierboven in deze post, onder de paragraaf "Properties":
"As a consequence of Lagrange's theorem, the order of a (mod n) always divides φ(n)").
Hierbij is
\(\varphi(n)\) de Euler phi functie = Euler totient functie
(zie bv.
https://nl.wikipedia.org/wiki/Indicator_(getaltheorie)).
Deze functie geeft het aantal getallen
\(g\) van 1 t/m n waarvoor geldt dat de grootste deler die
\(g\) en
\(n\) gemeenschappelijk hebben gelijk is aan 1. Ofwel: waarvoor
\(ggd(g,n)=1\).
En als
\(n\) een priemgetal
\(p\) is, dan hebben alle getallen van 1 t/m p-1 geen delers groter dan 1 gemeenschappelijk met p, dus
\(\varphi (p)=p-1\).
Volgens de stelling van Lagrange hebben we nu:
\(ord_p(g) \text{ deelt } p-1\)
Bij het zoeken van geschikte
\(a\) en
\(b\) bepalen we dus de delers van
\(p-1\), kijken we of
\(a^H\equiv 1 \mod p\) resp.
\(b^B\equiv 1 \mod p\) en controleren we tenslotte of er geen kleinere delers
\(d\) dan
\(H\) resp.
\(B\) zijn waarvoor
\(a^d\equiv 1 \mod p\) of
\(b^d\equiv 1 \mod p\)
Voorbeeld: \(p=29, H=4, B=7\):
een geschikte
\(a\):
2^4 mod 29 = 16; 3^4 mod 29 = 23; 4^4 mod 29 = 24; ... ; 11^4 mod 29 = 25; 12^4 mod 29 = 1, mogelijk a=12
De delers van p-1 = 28 zijn: 1, 2, 4, 7, 14 en 28, dus moeten we nog controleren of machten 1 en 2 ongelijk aan 1 zijn:
12^1 mod 29 = 12 ≠ 1 (logisch omdat a=12 ≠ 1 is)
12^2 mod 29 = 28 ≠ 1
Dus a = 12 blijft mogelijk.
NOOT: deze controles zijn noodzakelijk: 28^4 mod 29 = 1, maar ook 28^2 mod 29 = 1, waardoor we
\(a=28\) niet kunnen gebruiken.
Evenzo voor geschikte
\(b\):
b=7: 7^7 mod 29 = 1, en controles:
7^1 mod 29 = 7 ≠ 1
7^2 mod 29 = 20 ≠ 1
7^4 mod 29 = 23 ≠ 1
Dus b=7 is ook een mogelijkheid.
Nu moeten we alleen nog controleren of er geen machten
\(i>0\) en
\(j>0\) zijn waarvoor
\(a^i = b^j\), anders hebben we een getal dubbel in de tabel, en daar is geen plaats voor: voor elk getal 1 t/m p-1 hebben we precies 1 plaats in de tabel.
Hier zijn de getallen in de linker kolom (behalve
\(a^0=b^0=1\)) 12, 28 en 17; en in de onderste rij 7, 20, 24, 23, 16 en 25, dus geen dubbelingen, en kunnen we
\(a=12\) en
\(b=7\) gebruiken voor onze LR.
Hier nog een voorbeeld met p=61, H=6 en B=10, waarbij deze laatste controle
voor
\(a=14\) en
\(b=3\) mis gaat: zowel
\(14^3\equiv 60 \mod 61\) als ook
\(3^5 \equiv 60 \mod 61\)
Terzijde: een LR kan nooit een even hoogte H en tegelijkertijd een even breedte B hebben (zoals hierboven 6 resp. 10): één van de twee moet oneven zijn. Kan je hiervoor een (eenvoudige) reden bedenken?
[3] Alle getallen 1 t/m p-1 zijn aanwezig in de LR:
Omdat voor alle getallen
\(n \;\; (1\le n \le p-1)\) geldt dat
\(ggd(n,p)=1\), hebben al die getallen
\(n\) een inverse
\(\text{mod }p\) (die je kan bepalen via het uitgebreide algoritme van Euclides, zie bv
https://nl.wikipedia.org/wiki/Uitgebrei ... n_Euclides)
In de linker kolom van de LR staan de machten van
\(a\), dat wil zeggen
\(a^i\) met
\(0\le i \le H-1\).
De inverse van
\(a^i\) is dan
\(a^{H-i}\), want
\(a^i \cdot a^{H-i} \equiv a^H \equiv 1 \mod p\)
Al die machten
\(a^i\) zijn verschillend, immers:
STEL: er zijn een
\(i\) en
\(j\) met
\(0 \le i < j \le H-1\), zodanig dat
\(a^j \equiv a^i \mod p\)
we weten dat er een inverse
\((a^i)^{-1}=a^{-i}\;\) van
\(a^i\) bestaat, vermenigvuldig links en rechts met
\(a^{-i}\):
\(a^{-i}a^j \equiv a^{-i}a^i \mod p\)
ofwel
\(a^{j-i}\equiv a^{i-i} \equiv a^0 \equiv 1 \mod p\)
maar voor alle
\(j\) en
\(i\) is
\(j-i<H\) en dat is strijdig met de definitie dat
\(H=ord_p(a)\) = de kleinste positieve macht H zodanig dat
\(a^H \equiv 1 \mod p\) is.
Dus moeten alle
\(a^i\) verschillend zijn.
Evenzo voor de onderste rij met de machten van
\(b\):
\(b^j\) met
\(0\le j \le B-1\) waarbij de inverse van
\(b^j\) dan
\(b^{B-j}\) is.
Alle
\(b^j\) zijn ook verschillend.
We hadden ook al de eis gesteld dat alle
\(a^i\) en
\(b^j\) verschillend moeten zijn (behalve
\(a^0 \equiv b^0 \equiv 1 \mod p\) op het hoekpunt van de LR).
We hebben nu dus
\(H+B-1\) hokjes van de LR gevuld met allemaal verschillende getallen.
Nu naar alle getallen van de LR:
Neem 2 verschillende posities (= hokjes) van de LR:
\(a^ib^j \equiv n \mod p\;\) en
\(\;a^sb^t \equiv m \mod p\)
waarbij
\(\small 0\le i,s \le H-1\;\) en
\(\small \; 0\le j,t \le B-1\)
De posities zijn verschillend, dus moet
\(i\neq s \vee j\neq t\)
We willen dan aantonen dat
\(n \not\equiv m \mod p\)
We onderscheiden 3 gevallen:
[1]
\(i=s \wedge j\neq t\):
Stel
\(n\equiv m \mod p\)
ofwel
\(a^ib^j \equiv a^ib^t \mod p\)
vermenigvuldig links en rechts weer met de inverse van
\(a^i\):
\(a^{-i}a^ib^j \equiv a^{-i}a^ib^t \mod p\)
\(b^j \equiv b^t \mod p\)
We zitten nu op de onderste regel van de LR, en daar is bovenstaande alleen mogelijk als
\(j=t\), maar dit is strijdig met de voorwaarde dat
\(j\neq t\), dus dit kan niet.
[2]
\(i\neq s \wedge j= t\):
Stel
\(n\equiv m \mod p\)
ofwel
\(a^ib^j \equiv a^sb^j \mod p\)
vermenigvuldig links en rechts met de inverse van
\(b^j\):
\(a^ib^jb^{-j} \equiv a^sb^jb^{-j} \mod p\)
\(a^i \equiv a^s \mod p\)
We zitten nu op de linker kolom van de LR, en daar is bovenstaande alleen mogelijk als
\(i=s\), maar dit is strijdig met de voorwaarde dat
\(i\neq s\), dus dit kan niet.
[3]
\(i\neq s \wedge j\neq t\):
Stel
\(n\equiv m \mod p\)
ofwel
\(a^ib^j \equiv a^sb^t \mod p\)
vermenigvuldig links en rechts met de inverse van
\(a^s \text{ en } b^t\):
\(a^{-s}a^ib^jb^{-t} \equiv a^{-s}a^sb^tb^{-t} \equiv a^{s-s}b^{t-t} \equiv 1 \mod p\)
We hebben nu:
\(a^{i-s}b^{j-t}\equiv 1 \mod p\)
Dit zou betekenen dat
\(a^{i-s}\) de inverse is van
\(b^{j-t}\)
Echter:
- vanwege de voorwaarde
\(i\neq s \wedge j\neq t\) zijn zowel
\(i-s\) als
\(j-t\) ongelijk aan nul
- we hebben ook gezien dat alle inversen van machten van b op de onderste regel staan, en de vorm
\(b^k\) hebben
- en we hebben gezien dat alle
\(a^{i \text{ mod }H}\) verschillen van alle
\(b^{j \text{ mod } B}\)
Een macht van a (hier
\(a^{i-s}\)) kan dus nooit een inverse zijn van een macht van b (hier
\(b^{j-t}\)).
Dus ook dit is strijdig, waarmee de aanname
\(n \equiv m \mod p\) verworpen is.
NOOT: In feite werken we in de exponenten van
\(a\) met getallen
\(\text{mod } H\). Door de begrenzing van
\(i\) en
\(s\) en het feit dat
\(i-s\neq 0\) is, is
\(1 \le (i-s) \text{ mod } H \le (H-1)\) waarmee we bovenstaande wat exacter uitdrukken.
Conclusie: alle waarden in de LR zijn verschillend, en dit zijn precies de getallen
\(1\) t/m
\(p-1\)
[4] de werking van de LR:
Dit hadden we al bekeken in eerdere posts:
- vermenigvuldigen:
\(n\cdot m \equiv a^ib^ja^sb^t \equiv a^{i+s\text{ mod }H}\cdot b^{j+t\text{ mod }B} \mod p\)
wat neerkomt op
\(j+t\text{ mod }B\) stappen naar rechts en
\(i+s\text{ mod }H\) stappen omhoog in de LR.
- machtsverheffen:
\(n^k \equiv (a^ib^j)^k \equiv a^{i\cdot k\text{ mod }H}\cdot b^{j\cdot k\text{ mod }B} \mod p\)
- inverse:
\(n^{-1} \equiv a^{-i\text{ mod }H}\cdot b^{-j\text{ mod }B} \mod p\)
machtsverheffen en inverse ook weer uit te drukken in stappen naar rechts en omhoog in de LR.
Een boel tekst, laat s.v.p. weten als er onduidelijkheden zijn of als je meer vragen hebt.