Lenstra

Dit forum is voor het voortgezetonderwijs (of 2de/3de graad ASO), als je in de bovenbouw zit. We gaan er vanuit dat je een Grafische Rekenmachine hebt.
Plaats reactie
mirjam4
Nieuw lid
Nieuw lid
Berichten: 3
Lid geworden op: 19 sep 2011, 14:47

Lenstra

Bericht door mirjam4 » 19 sep 2011, 14:56

kent iemand de rekenmachine van Lenstra?

mirjam4
Nieuw lid
Nieuw lid
Berichten: 3
Lid geworden op: 19 sep 2011, 14:47

lenstra's rekenmachine

Bericht door mirjam4 » 19 sep 2011, 15:34

Wie kent de rekenmachine van Lenstra en weet waarom Lenstra deze getallen gebruikt? :?:

arno
Vergevorderde
Vergevorderde
Berichten: 1923
Lid geworden op: 25 dec 2008, 16:28
Locatie: Beek en Donk, Noord-Brabant

Re: lenstra

Bericht door arno » 19 sep 2011, 19:34

Wat bedoel je met "rekenmachine van Lenstra"? Kun je misschien een link geven waar dit nader wordt omschreven?
"Mathematics is a gigantic intellectual construction, very difficult, if not impossible, to view in its entirety." Armand Borel

mirjam4
Nieuw lid
Nieuw lid
Berichten: 3
Lid geworden op: 19 sep 2011, 14:47

Re: lenstra

Bericht door mirjam4 » 19 sep 2011, 22:12

Het heeft te maken met het uitrekenen van een bepaalt modulo getal?
Bijvoorbeeld in een schema met modulo 31.

16 13 28 15 18 3
8 22 14 23 9 17
4 11 7 27 20 24
2 21 19 29 10 12
1 26 25 30 5 6
Zou je een bepaalde rekensom bijvoorbeeld 11x19 mod31 uitrekenen door eerst naar 11 te gaan.(2 omhoog, 1 naar rechts) EN dan 19(2 naar rechts, 1omhoog) en dan bij elkaar 3 omhoog en 3 naar rechts. Dan kom kom op je op 23 mod 31. Hoe kunnen wij nu z'n schema voor een andere getal maken, waar zit het verband precies?


Edit: schema komt er niet zo netjes uit, moet 6 rijen van 5 zijn naast elkaar

Code: Selecteer alles

 16    13    28    15    18     3
 08    22    14    23     9    17
 04    11     7    27    20    24
 02    21    19    29    10    12
 01    26    25    30     5     6
Laatst gewijzigd door David op 20 sep 2011, 12:33, 1 keer totaal gewijzigd.
Reden: Schema invoegen.

arie
Moderator
Moderator
Berichten: 3764
Lid geworden op: 09 mei 2008, 09:19

Re: Lenstra

Bericht door arie » 20 sep 2011, 07:11

Geef svp eerst eens antwoord op de volgende vragen:

Waarom staat het getal nul niet in de tabel?
Hoeveel getallen staan er in de tabel, en welke zijn dat?

Waarom staat het getal 1 links onderaan? Ofwel: wat gebeurt er als je een getal met 1 (mod 31) vermenigvuldigd, dus hoeveel stappen moet je daarbij steeds omhoog en naar rechts om het antwoord van deze vermenigvuldiging te vinden?

Kijk nu eens naar het getal direct boven de 1, hier: 2.
Wat is 2x2 = 2^2 (mod 31) ?
Wat is 2x2x2 = 2^3 (mod 31) ?
Wat is 2x2x2x2 = 2^4 (mod 31) ?
Wat is 2x2x2x2x2 = 2^5 (mod 31) ?
Elke stap omhoog is hier een vermenigvuldiging met 2.
Geldt dat ook voor de andere kolomen (reken nog altijd modulo 31)?

Kijk nu eens naar het getal direct rechts van de 1, hier: 26.
Wat is 26x26 = 26^2 (mod 31) ?
Wat is 26x26x26 = 26^3 (mod 31) ?
Wat is 26x26x26x26 = 26^4 (mod 31) ?
Wat is 26x26x26x26x26 = 26^5 (mod 31) ?
Wat is 26x26x26x26x26x26 = 26^6 (mod 31) ?
Elke stap naar rechts is hier een vermenigvuldiging met 26 (mod 31).
Geldt dat ook voor de andere rijen?

yundostres
Nieuw lid
Nieuw lid
Berichten: 4
Lid geworden op: 19 okt 2022, 10:19

Re: Lenstra

Bericht door yundostres » 21 okt 2022, 10:13

Dag Arie,

Ik ben momenteel bezig met de Lenstra rekenmachine. Heb er op internet niet veel over kunnen vinden. Ik zou het op prijs stellen als je me meer informatie kan geven over de LR. Om je vragen te beantwoorden:

Waarom staat het getal nul niet in de tabel?
Dat is geen rest.

Hoeveel getallen staan er in de tabel, en welke zijn dat?
Dat zijn er 31-1=30 Want er zijn 30 verschillende resten, de getallen 1t/m 30.

Waarom staat het getal 1 links onderaan?
We zien dat Lenstra de 1 in het midden heeft gezet. Dus het is een keuze.

Geldt dat ook voor de andere kolomen (reken nog altijd modulo 31)?
Ja dat geldt voor alle kolommen en rijen.

arie
Moderator
Moderator
Berichten: 3764
Lid geworden op: 09 mei 2008, 09:19

Re: Lenstra

Bericht door arie » 22 okt 2022, 19:20

Nul is wel een rest bij deling door 31, bijvoorbeeld:
62 = 2*31 rest 0
ofwel
62 ≡ 0 mod 31
Nul past alleen niet in het rekenschema dat we voor ogen hebben: bijvoorbeeld een aantal stappen naar rechts en een aantal stappen omhoog bij vermenigvuldiging. Nul maal welk getal dan ook blijft nul = op dezelfde plaats in het schema, terwijl elk getal een verschillend aantal stappen betekent. En je kan niet voor elk verschillend aantal stappen op nul uitkomen...

Modulo 31 zijn er 31 resten, waarvan we nul niet gebruiken, er blijven dus 31-1=30 verschillende getallen over.

De keuze om 1 in het vakje linksonder te zetten is vrij, maar het opstellen van het schema wordt daardoor wel iets eenvoudiger, evenals het rekenen met het schema.


Opbouw en werking van een Lenstra Rekenmachine (=LR):

Stel we willen een LR-schema mod 29 maken. Dit levert 29-1=28 getallen, waarmee we bijvoorbeeld een 4x7 rechthoek kunnen vullen:

Afbeelding

Als we de 1 linksonder plaatsen, zoeken we een getal \(a\; (2 \le a \le 28)\), zodanig dat
\(a^4 \equiv 1 \mod 29\)
en zodanig dat \(a, a^2 \text{ en } a^3\) ongelijk aan 1 zijn mod 29 (1 mag maar 1 keer voorkomen in het schema).
Dit blijkt te gelden voor bijvoorbeeld \(a=12\):
\(12 \equiv 12 \mod 29\)
\(12^2 \equiv 28 \mod 29\)
\(12^3 \equiv 17 \mod 29\)
\(12^4 \equiv 1 \mod 29\)
We hebben nu de linker kolom gevuld.

Voor de onderste rij zoeken we een getal \(b\; (2 \le b \le 28)\), zodanig dat
\(b^7 \equiv 1 \mod 29\)
en zodanig dat \(b, b^2, b^3, b^4,b^5 \text{ en } b^6\) ongelijk aan elk van de getallen uit de linker kolom zijn mod 29 (elk getal mag maar 1 keer voorkomen in het schema).
Dit blijkt te gelden voor bijvoorbeeld \(b=7\):
\(7 \equiv 7 \mod 29\)
\(7^2 \equiv 20 \mod 29\)
\(7^3 \equiv 24 \mod 29\)
\(7^4 \equiv 23 \mod 29\)
\(7^5 \equiv 16 \mod 29\)
\(7^6 \equiv 25 \mod 29\)
\(7^7 \equiv 1 \mod 29\)

De rest van de LR-elementen zijn de producten van de betreffende linker-kolom-elementen en de betreffende onderste-rij-elementen, zoals aangegeven in het plaatje.

Controleer tenslotte of alle getallen 1 t/m 28 inderdaad in de LR staan.

Ik kom dan uit op dit resultaat:

Afbeelding

[1] Willen we hiermee het produkt van \(n=a\cdot b^2 = 8\) en \(m=a^2\cdot b^3 = 5\) uitrekenen,
dan schuiven we vanuit m 2 plaatsen op naar links en 1 naar boven (dit zijn de machten van b resp a van n),
en komen uit op 11, dus
\(8 \cdot 5 \equiv 11 \mod 29\)
en genoteerd met a en b:
\((a\cdot b^2) \cdot (a^2\cdot b^3) \equiv (a^3\cdot b^5) \mod 29\)

Merk op:
Omdat \(a^4 = a^0 = 1\)
en \(b^7 = b^0 = 1\)
hebben we genoeg aan de machten van a mod 4 en aan de machten van b mod 7.
Voorbeeld:
23 = 5*4 rest 3, en voor die rest geldt: 23 mod 4 ≡ 3, dus
\(a^{23} = a^{5\cdot 4 + 3} = a^{4\cdot 5}\cdot a^3 = (a^4)^5 \cdot a^3 = 1^5 \cdot a^3= a^3 = a^{23\mod 4}\)


Hierdoor is
\(11\cdot 19 \equiv (a^3\cdot b^5) \cdot (a^3\cdot b^6) \equiv a^6\cdot b^{11} \mod 29\)
en dit mogen we schrijven als:
\(\equiv a^{6\mod 4}\cdot b^{11\mod 7} \equiv a^2 \cdot b^4 \mod 29\)
En vanuit 1 gaan we dus 2 stappen omhoog en 4 naar links, wat het antwoord levert: 6 mod 29.


[2] Dit werkt ook voor machtsverheffen:
\(5^{1001} \equiv (a^2b^3)^{1001}\equiv a^{2002}b^{3003}\equiv a^{(2002 \mod 4)}\cdot b^{(3003 \mod 7)}\equiv a^2b^0\equiv 28 \mod 29\)
Nog even ten overvloede: in plaats van \(5^{1001} \equiv (a^2b^3)^{1001}\equiv a^{2002}b^{3003}\)
kan je ook zeggen:
\(5^{1001} = \text{(2 omhoog en 3 naar rechts)}^{1001} = \text{2002 omhoog en 3003 naar links}\)
immers: a betekent "omhoog" en b betekent "naar rechts"


[3] Kan je ook een manier bedenken om snel de inverse \(k^{-1}\) van een gegeven getal \(k\) te bepalen (mod 29) met bovenstaande tabel?
Voorbeeld: als \(k=9\) dan is \(k^{-1}=13\), want \(k^{-1}\cdot k \equiv 13\cdot 9 \equiv 1 \mod 29\)


Lukt het je om zelf zo'n rekenmachine te maken, bijvoorbeeld: \(\mod 13\), met 3 rijen en 4 kolommen?

yundostres
Nieuw lid
Nieuw lid
Berichten: 4
Lid geworden op: 19 okt 2022, 10:19

Re: Lenstra

Bericht door yundostres » 27 okt 2022, 16:12

Beste Arie,

Geweldig! Hartelijk bedankt voor je uitgebreide antwoord. Het helpt ons enorm om de LR beter te begrijpen en er meer van te gaan houden.

Snel de inverse? Jazeker! Neem een getal, zeg 5, dan kijk je welke stappen je moet doen om naar 1 te gaan. In dit geval dus 2 naar beneden en 3 naar links. Vanuit 1 gezien doe je dan hetzelfde en kom je uit op 6. (Ik vind het makkelijk om te bedenken dat de 1 rechtsboven de 19 staat)

LR van mod 13:

9 6 4 7
3 2 10 11
1 5 12 8

Ik vraag me af of je bronnen met ons kan delen van de LR want online kan ik bijna niets vinden. Met name bronnen waarin een bewijs wordt gegeven van de LR.

arie
Moderator
Moderator
Berichten: 3764
Lid geworden op: 09 mei 2008, 09:19

Re: Lenstra

Bericht door arie » 30 okt 2022, 16:04

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):

Afbeelding

en hier een plaatje met getallen, nu voor de mod 13 LR die jij hierboven gegeven hebt:

Afbeelding


[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\)

Afbeelding

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.

yundostres
Nieuw lid
Nieuw lid
Berichten: 4
Lid geworden op: 19 okt 2022, 10:19

Re: Lenstra

Bericht door yundostres » 31 okt 2022, 18:49

Arie je bent een held! Veel dank voor je energie en tijd. Ik ga hier woensdag uitgebreid naar kijken. Als ik vragen heb weet ik je te vinden. Echt top!

arie
Moderator
Moderator
Berichten: 3764
Lid geworden op: 09 mei 2008, 09:19

Re: Lenstra

Bericht door arie » 01 nov 2022, 23:03

Nog even dit:

Als het is voor een werkstuk kan je ook nog kijken naar de beperkingen van de Lenstra Rekenmachine:
Ten eerste het feit dat ze alleen maar werken modulo een priemgetal.
Ten tweede moet \(H\cdot B = p-1\) zijn, ofwel: \(H\) en \(B\) zijn delers van \(p-1\). Kijk eens naar \(p=263\): de delers van \(p-1=262\) zijn 1, 2, 131 en 262: de rechthoeken van 2 bij 131 en van 1 bij 262 zijn dan de enige mogelijkheden, en die hebben dan een behoorlijk ongelukkige hoogte-breedte verhouding.
Ten derde: voor grotere p wordt het al snel lastig om de benodigde getallen in de tabel terug te vinden.
Hier een LR voor \(p=337\): het wordt al een aardig zoek- en telwerk om daarmee bijvoorbeeld \(234^{56}\mod 337\) te bepalen:
Afbeelding

Je zou dit kunnen oplossen door een index-tabel te maken die voor elk getal 1 t/m p-1 de (x, y)-locatie in de tabel geeft, en daarnaast de rijen en kolommen van de tabel te voorzien van hun coordinaten.
Maar dan is het handiger om te werken met een 1 bij p-1 LR: we hoeven dan bij berekeningen alleen te reduceren modulo breedte, en niet modulo breedte EN modulo hoogte van de tabel.
Voorbeeld: \(p = 11\), hoogte = 1, breedte = 10:
Afbeelding
In de LR staan achtereenvolgens de getallen \(2^0=1, 2^1=2, 2^2, 2^3, ... ,2^{p-2}=2^9\) (alles \(\text{mod 11}\)). Bij \(2^{10} \equiv 1 \text{ mod 11}\) start de volgende kopie van de LR.
Onder de LR in rood staan de positienummers van de LR (= de kolomnummers van de LR).
We kunnen dit ook in tabelvorm weergeven:
Afbeelding
In geel gesorteerd op positie: we zien direct welk getal \(a\) op een gegeven positie staat
in groen gesorteerd op getal \(a\): we zien direct de positie van een gegeven getal \(a\;\; (1 \le a \le p-1)\)
Lukt het je om hiermee:
\(1*2*3*4*5 \mod 11\),
\(8^{32} \mod 11\) en
de inverse van \(3 \mod 11\)
te bepalen?

NOOT: voor elk priemgetal p lukt het om een 1 bij p-1 LR te maken.
We maken dan gebruik van getallen \(a\) waarvoor geldt dat \(ord_p(a)=p-1\).
Dit zijn primitieve wortels (Engels: primitive roots) van p, en daar zijn er \(\varphi(\varphi(p))\) van.
(zie bv. https://mathworld.wolfram.com/PrimitiveRoot.html)
Voor \(p=11\) is \(\varphi(\varphi(11))=\varphi(10)=4\).
De primitieve wortels blijken 2, 6, 7 en 8. Deze 4 getallen hebben een multiplicatieve orde 10 mod 11, van alle overige getallen is de orde kleiner:

Code: Selecteer alles

 a   ord(a)    opeenvolgende machten van a mod 11:
 1:     1      [1]
 2:    10      [1, 2, 4, 8, 5, 10, 9, 7, 3, 6]
 3:     5      [1, 3, 9, 5, 4]
 4:     5      [1, 4, 5, 9, 3]
 5:     5      [1, 5, 3, 4, 9]
 6:    10      [1, 6, 3, 7, 9, 10, 5, 8, 4, 2]
 7:    10      [1, 7, 5, 2, 3, 10, 4, 6, 9, 8]
 8:    10      [1, 8, 9, 6, 4, 10, 3, 2, 5, 7]
 9:     5      [1, 9, 4, 3, 5]
10:     2      [1, 10]

yundostres
Nieuw lid
Nieuw lid
Berichten: 4
Lid geworden op: 19 okt 2022, 10:19

Re: Lenstra

Bericht door yundostres » 03 nov 2022, 16:51

Bedankt Arie. Dankzij je heldere toelichting kunnen we het goed volgen. De vragen beantwoorden we een andere keer.

Plaats reactie