Peter Ypma – Pagina 3

Toetsen cryptografie

Op deze pagina vind je de uitwerkingen van de oefentoets die je hier kunt downloaden. Op de volgende pagina staan oude toetsen die ik in het verleden gegeven heb.

Opdracht 1: (Python, 4 punten)
Als input krijg je op de eerste regel een $x$ -coördinaat en op de tweede regel een $y$ -coördinaat. Beide inputs zijn gehele getallen ongelijk aan nul. Als output moet je geven in welk kwadrant het punt met dit $x$ – en $y$ -coördinaat zit. In het diagram hieronder zie je welke kwadranten er zijn.
Voorbeeld input:
3
-4
Voorbeeld output:
4

Uitwerking:

Een voorbeeld van een correct antwoord is:

x = int(input())
y = int(input())
if x>0 and y>0:
    print(1)
elif x<0 and y>0:
    print(2)
elif x<0 and y<0:
    print(3)
else:
    print(4)

Dit kun je ook met geneste if-statements doen:

x = int(input())
y = int(input())
if x>0:
    if y>0:
        print(1)
    else:
        print(4)
else:
    if y>0:
        print(2)
    else:
        print(3)

De punten krijg je voor de volgende elementen:

Punt 1: Het correct inlezen van de input en deze omzetten naar integers.
Punt 2: De juiste syntax bij if-statements (denk aan: eindig met dubbele punt, ingesprongen regels, etcetera).
Punt 3: Correcte output van 1 als de input in kwadrant 1 zit.
Punt 4: De andere kwadranten zijn allemaal ook correct gedaan.

Je kunt een ander antwoord controleren bij de opdracht Quadrant selection op Kattis.

Opdracht 2: (Python, 4 punten)
Als input krijg je een getal van precies zeven cijfers. Als output moet je 1 geven als dit getal begint met 555. Als output moet je 0 geven in alle andere gevallen.
Voorbeeld input:
5552314
Voorbeeld output:
1

Uitwerking:

Je kunt dit op twee manieren oplossen. De meest voorkomende manier is om eerst te delen door 10000 (naar beneden afgerond) om alleen de eerste drie cijfers over te houden en dan te controleren of dit getal 555 is.

getal = int(input())
eerste3 = getal // 10000
if eerste3 == 555:
    print(1)
else:
    print(0)

Een alternatieve manier is om te controleren of het begingetal tussen (en met) 5550000 en 5559999 zit. Een manier om dit te programmeren is als volgt:

getal = int(input())
if getal >= 5550000 and getal <= 5559999:
    print(1)
else:
    print(0)

Voor het eerste alternatief krijg je punten voor de volgende stappen:

Punt 1: Het idee dat je de laatste vier cijfers moet verwijderen.
Punt 2: Dit correct uitvoeren met // 10000
Punt 3: De correcte syntax bij het if-statement (let op ==, de dubbele punt en dat de volgende regel ingesprongen is)
Punt 4: Het programma geeft het juiste antwoord.

Voor het tweede alternatief krijg je de punten als volgt:

Punt 1: Het idee dat de input minstens 5550000 en maximaal 5559999 moet zijn.
Punt 2 en 3: Dit correct implementeren in een if-statement (met and en juiste syntax)
Punt 4: Het programma geeft het juiste antwoord.

Je kunt een ander antwoord controleren bij de opdracht FYI op Kattis.

Opdracht 3: (Python, 6 punten)
Op de eerste regel van de input staat een getal. Dit geeft het aantal getallen op de volgende regel aan (al deze getallen zijn geheel en gescheiden met een spatie). Als output moet je op de eerste regel het aantal getallen printen dat groter is dan alle vorige getallen in de rij. Op de tweede regel print je al deze getallen (die groter zijn dan alle vorige in de rij) van klein naar groot met steeds een spatie ertussen.
Voorbeeldinput:
9
3 5 2 6 1 4 8 7 9
Voorbeeldoutput:
5
3 5 6 8 9

Uitwerking:

Een voorbeeld van een goed antwoord is:

aantal = int(input())
getallen = input().split()
grootsteGetal = int(getallen[0])
antwoord1 = 1
antwoord2 = getallen[0]
for i in range(1, aantal):
    getal = int(getallen[i])
    if getal > grootsteGetal:
        antwoord1 += 1
        antwoord2 += " " + getallen[i]
        grootsteGetal = getal
print(antwoord1)
print(antwoord2)

Hierbij krijg je de punten als volgt:

Punt 1: Correct inlezen van de variabelen, waarbij je de getallen uit je array later nog omzet naar integers.
Punt 2: Je houdt correct bij wat het grootste getal is dat tot nu toe in de lijst voorgekomen is.
Punt 3: Je lijst begint met het eerste element van de lijst van de input. Dit element tel je ook mee bij het antwoord wat op de eerste regel van de output komt.
Punt 4: Je doet een for-loop waarin je met een if-statement controleert of alle getallen groter zijn dan de grootste die eerder in de lijst stond.
Punt 5: De for-loop en het if-statement hebben een correcte syntax.
Punt 6: Binnen het if-statement pas je de antwoorden op de juiste manier aan en je print deze op het eind van het programma op de juiste manier.

Bonus:
Dit probleem is geïnspireerd op de opdracht Greedily Increasing Subsequence op Kattis. Aangezien de getallen daar groot zijn en werken met grote strings langzaam is, wordt dit antwoord echter niet goed gerekend. Een snellere manier is om in een lijst bij te houden wat de antwoorden zijn. Daarvoor heb je echter wel een paar methodes nodig die je nog niet gehad hebt:

lijst.append(3)
Dit voegt het element 3 aan het einde van de lijst toe.
print(*lijst)
Het sterretje zorgt ervoor dat de lijst zonder [] en met alleen spaties tussen de elementen geprint wordt.

Als uitdaging kun je proberen of je hiermee het probleem op Kattis kunt oplossen. Een correcte oplossing staat hieronder.

Antwoord probleem Kattis:

aantal = int(input())
getallen = input().split()
grootsteGetal = int(getallen[0])
antwoord = [grootsteGetal]
for i in range(1, aantal):
    getal = int(getallen[i])
    if getal > grootsteGetal:
        antwoord.append(getal)
        grootsteGetal = getal
print(len(antwoord))
print(*antwoord)

Opdracht 4: (3 punten)
Bereken met het algoritme van Euclides de grootst gemene deler van 2796 en 3528.

Uitwerking:

Hieronder staat het algoritme van Euclides uitgewerkt. Merk op dat je gewoon de MOD-functie op de CASIO (onder OPTN -> Numeric) of de Remainder-functie op de TI (onder Math -> Num) kunt gebruiken voor de modulo berekeningen:

$\text{ggd}(2796,3528)=\text{ggd}(2796, 3528\text{ mod }2796)=\text{ggd}(2796, 732)$
$\text{ggd}(2796,732)=\text{ggd}(2796\text{ mod }732, 732)=\text{ggd}(600, 732)$
$\text{ggd}(600,732)=\text{ggd}(600, 732\text{ mod }600)=\text{ggd}(600, 132)$
$\text{ggd}(600, 132)=\text{ggd}(600\text{ mod }132, 132)=\text{ggd}(72, 132)$
$\text{ggd}(72, 132)=\text{ggd}(72, 132\text{ mod }72)=\text{ggd}(72, 60)$
$\text{ggd}(72, 60)=\text{ggd}(72\text{ mod }60, 60)=\text{ggd}(12, 60)$
$\text{ggd}(12, 60)=\text{ggd}(12, 60\text{ mod }12)=\text{ggd}(12, 0)=12$
Uit de bovenstaande rekenstappen volgt $\text{ggd}(2796,3528)=12$ .

De punten krijg je op de toets voor de volgende zaken:

Punt 1 krijg je voor het toepassen van de regel $\text{ggd}(a,b)=\text{ggd}(a \text{ mod } b,b)$ .
Punt 2 en 3 krijg je voor het proces correct doorlopen tot $\text{ggd}(2796,3528)=12$ . Bij het maken van één rekenfout of schrijffout krijg je hiervan nog één punt. Bij het maken van twee of meer rekenfouten krijg je hiervan geen enkel punt.

Opdracht 5: (3 punten)
Je wilt een RSA wachtwoordpaar $(d,e)$ maken en kiest hiervoor $p=29$ , $q=59$ en $e=5$ . Bereken de waarde van $d$ .

Uitwerking:

We hebben $\phi(N)=28\cdot 58=1624$ . We moeten nu $d$ zo berekenen dat $d\cdot 5\text{ mod } 1624 = 1$ . We zien dat $d=1625/5=325$ werkt (het is met zo’n kleine $e$ dus niet nodig om het algoritme van Euclides te gebruiken).

Je krijgt de punten voor de volgende stappen:

Het eerste punt voor het correct berekenen van $\phi(N)=1624$ .
Het tweede punt voor de observatie dat $d\cdot 5\text{ mod } 1624 = 1$ .
Het derde punt voor hieruit $d=325$ berekenen.

Opdracht 6: (3 punten)
In het jaar dat ik deze oefentoets maakte, zaten de volgende leerlingen in de wiskunde D-klas: Anne, Bart, Elis, Evan, Imre, Koen, Lars, Loek, Paul, Stef, Joris, Marte, Merel, Reyer, Roman, Yasin, Hannah, Jochem, Liesje, Marius, Nathan, Pepijn, Thomas, Eulalia, Florice, Kirstin, Maurits, Vivienne, Giamingga en Christiaan (geordend op lengte van naam en vervolgens op alfabet). Twee van deze namen zijn met dezelfde encryptiefunctie versleuteld die iedere letter telkens op dezelfde manier versleuteld. Uit de encryptiefunctie komt ABST en XAGAD. Welke namen zijn dit? Leg uit hoe je zeker kan weten dat er geen andere mogelijkheid is.

Uitwerking:

Er zijn maar twee vijfletterige namen waarvan de tweede en de vierde letter hetzelfde zijn. Dat zijn Merel en Reyer. Bij Reyer is de vijfde letter echter ook hetzelfde als de eerste letter. Dat is niet het geval bij XAGAD. Dit moet dus wel voor Merel staal. We weten dus dat ABST met een E begint. Dit moet dus Elis of Evan zijn. Aangezien Elis echter een l gemeenschappelijk heeft met Merel en er geen andere letters overeenkomen uit ABST en XAGAD moet het wel Evan zijn.

Je krijgt de punten voor de volgende stappen:

Punt 1 krijg je voor het hebben van de naam Merel.
Punt 2 krijg je voor het hebben van de naam Evan.
Punt 3 krijg je voor een sluitende uitleg dat het alleen deze twee namen kunnen zijn. De uitleg hierboven is een voorbeeld van een correcte uitleg.

Opdracht 7: (3 punten)
We ordenen alle positieve getallen in het 3-tallig stelsel die geen 2 bevatten van klein naar groot. Zet het honderste getal uit deze lijst om naar het tientallig stelsel. Geef dit getal en ligt toe hoe je hieraan komt.

Uitwerking:

Als je de lijst maakt, zie je dat dit precies de binaire getallen zijn. honderd in binair is 64+32+4 en dus 1100100. Dit weer terug omzetten naar het tientallig stelsel is $3^6+3^5+3^2=981$ .

De punten krijg je voor de volgende stappen:

Punt 1 krijg je voor als duidelijk uit je uitwerking te zien is dat je honderd moet omzetten naar een binair getal.
Punt 2 krijg je als je op het getal 1100100 uitkomt (als je dit anders doet dan met binaire getallen, krijg je punt 1 ook).
Punt 3 krijg je als je het gevonden getal in het drietallig stelsel weer correct omzet naar het tientallig stelsel.

Pagina's: 12

Voorbereiden toets deel 2: Cryptografie

Op de toets komen ook vragen over cryptografie. Hierbij hoef je niet te programmeren (want dat deel wordt al getest bij de Python-vragen van de toets). In plaats daarvan zal ik vragen stellen waarin je de geleerde principes uit de lessen toepast. Op deze pagina zie je bij iedere les een aantal voorbeelden van vragen die ik bij die les zou kunnen stellen op de toets.

Les 5: Encryptiefuncties

In deze les leerden we het volgende stappenplan om teksten te versleutelen:

Zet de versleutelde tekst om in getallen.
Voer de decryptiefunctie uit ( is de inverse functie van )
Zet de getallen om in een leesbare tekst.

Voor het omzetten van en naar getallen gebruiken we de volgende tabel.

Opdrachten

Vraag 1:
Bij Caesars versleuteling schuiven alle letters 3 plekken op. Zo werd de A versleuteld als een D, de B werd versleuteld als een E, enzovoort tot en met een Z die een C wordt. Welke encryptiefunctie hoort hierbij?

Uitwerking:

Hier hoort de encryptiefunctie $E(x)=(x+3) \text{ mod }(26)$ .

Vraag 2:
Meneer Ypma heeft met de Encryptiefunctie $E(x)=(x+2)\text{ mod }26$ een woord versleuteld. Zijn uitkomst was RNWU. Wat was het oorspronkelijke woord?

Uitwerking:

Om het bericht te ontcijferen, gebruik je de decryptiefunctie $D(x)=(x-2)\text{ mod }26$ . Dit betekent dat je simpelweg alle letters twee moet terugschuiven. De R wordt dus een P, de N wordt een L, de W een U en de U een S. We krijgen dus het woord PLUS.

Vraag 3:
Imre gebruikt een encryptiefunctie die letters op letters afbeeldt. Deze wordt gedefinieerd door de onderstaande tabellen:

Hij versleuteld een woord en krijgt SABR. Welk woord heeft hij versleuteld?

Uitwerking:

Om het woord te ontcijferen, moeten we het omgekeerde doen van wat Imre gedaan heeft. Dat betekent dat we de tabel van onder naar boven moeten lezen. De S was dus een G, de A was een O, de B was een E en de R was een D. Het oorspronkelijke woord was dus GOED.

Vraag 4:
a) Leg uit waarom $E(x)=13x\text{ mod }26$ geen goede encryptiefunctie is.
b) Bereken hoeveel encryptiefuncties er zijn van de vorm $E(x)=(ax+b)\text{ mod }26$ met $0\leq a\leq 25$ en $0\leq b\leq 25$ gehele getallen waarbij er geen twee letters zijn die op dezelfde letter afgebeeld worden.

Uitwerking a:

$E(0)=0$ en $E(2)=0$ . Hierdoor worden meerdere letters op dezelfde letter afgebeeld. Daardoor bestaat er geen inverse functie en kan de versleutelde tekst niet meer teruggehaald worden.

Uitwerking b:

Het probleem uit opdracht 4a gebeurt als $a=13$ of als $a$ een even getal is. In het laatste geval is $E(0)$ gelijk aan $E(13)$ . Dit betekent dat $a$ alleen 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 of 25 zijn. We hebben daarom 12 opties voor $a$ .

De plus $b$ kun je altijd ongedaan maken door min $b$ te doen. Hierdoor kan $b$ ieder getal van 0 t/m 25 zijn. Dat zijn dus 26 opties. In totaal hebben we dus $12\cdot 26=312$ goede functies.

NB: Eén van die functies is $E(x)=x \text{ mod } 26$ . Die is wellicht om andere redenen geen goede encryptiefunctie, maar hij telt wel mee bij deze vraagstelling.

Vraag 5:
Voor een zekere encryptiefunctie van de vorm $E(x)=(ax+b)\text{ mod }26$ geldt $E(0)=5$ en $E(3)=12$ . Achterhaal de waarden van $a$ en $b$ .

Uitwerking:

Uit $E(0)=5$ volgt direct $b=5$ . Vervolgens hebben we $E(3)-E(0)=(a\cdot 3+5) \text{ mod } 26 - (a\cdot 0 +5) \text{ mod } 26 = 3a \text{ mod } 26$ . We hebben ook $E(3)-E(0)=12-5=7$ . We moeten dus oplossen voor welke $a$ er geldt dat $3a \text{ mod } 26=7$ .

$3a \text{ mod } 26=7$ kun je oplossen op de manier van les 6 of door slim te proberen. We weten dat uit de som 7 komt als voor het modulo rekenen de uitkomst 7, $7+26=33$ of $7+2\cdot 26=59$ was. Hiervan is 33 een drievoud. Het antwoord is daarom $a=11$ , omdat $3\cdot 11 \text{ mod } 26 = 7$ .

Conclusie: $a=11$ met $b=5$

Vraag 6:
Voor een zekere encryptiefunctie van de vorm $E(x)=(ax+b)\text{ mod }26$ geldt $E(3)=7$ en $E(5)=11$ . Achterhaal de waarden van $a$ en $b$ als je weet dat E een encryptiefunctie is waarbij geen twee letters op dezelfde letter afgebeeld worden.

Uitwerking:

Er geldt $E(5)-E(3)=(a\cdot 5+b) \text{ mod } 26 - (a\cdot 3 +b) \text{ mod } 26 = 2a \text{ mod } 26$ . We hebben ook $E(5)-E(3)=11-7=4$ . We moeten dus oplossen voor welke $a$ er geldt dat $2a \text{ mod } 26=4$ . Dat kan als de uitkomst van de som voor modulorekenen 4 of $4+26=30$ is. Dit geeft $2a=4\vee 2a=30$ oftewel $a=2\vee a=15$ . Bij $a=2$ worden meerdere letters op dezelfde letter afgebeeld (zie vraag 4) en het antwoord is dus $a=15$ .

Door $a=15$ in te vullen in $E(3)=7$ krijgen we de vergelijking $(15\cdot 3+b) \text{ mod } 26 = 7$ . Oftewel $(45+b)\text{ mod } 26 = 7$ . Een correct antwoord voor $b$ is nu $7-45=-38$ . Ik vind het zelf mooier om $b$ tussen de 0 en de 25 te geven. Dat geeft $b=-38+2\cdot 26=14$ .

Conclusie: Het antwoord is $a=15$ met $b=14$ .

Pagina's: 1234567

Meetkundige bewijzen

Alle onderstaande puzzels komen uit de finales van de Wiskunde Olympiade. Mijn advies is om deze te proberen nadat je hoofdstuk 9 t/m 12 van de finaletraining van de Wiskunde Olympiade doorgewerkt hebt. De uitwerkingen vind je hier.

Puzzel 1 (Wiskunde Olympiade Finale 2025 – versie klas 4):
Binnen een driehoek $ABC$ ligt een punt $P$ met de eigenschap dat $\angle ACP = \angle BAP$ en $\angle BCP=\angle ABP$ . De lijn door $C$ en $P$ snijdt de zijde $AB$ in het punt $D$ .
Bewijs dat $D$ het midden is van het lijnstuk $AB$ .

Stap 1: Het maken van een mooi plaatje

Stap 1 in het oplosproces is om een mooi plaatje te maken. Hier is daarbij de moeilijkheid dat je nog niet precies weet waar punt $P$ in de driehoek komt. In dit geval vertelt echter de laatste regel dat uiteindelijk gaat gelden dat het midden $D$ van lijnstuk $AB$ op de lijn $CP$ ligt. Teruggedacht ligt de juiste ligging van $P$ dus schijnbaar ook op de lijn $CD$ . Hiermee kun je met de volgende stappen een mooi plaatje tekenen.

Ik heb een grote driehoek $ABC$ getekend.
Ik heb een punt $D$ ongeveer halverwege $AB$ gezet.
Ik heb de lijn $CD$ ingetekend.
Ik heb een punt $P$ op $CD$ gezet, zodat $\angle ACP \approx \angle BAP$ .
Ik teken nu ook de lijn $BP$ in en controleer dat ongeveer klopt dat $\angle BCP\approx \angle ABP$ .

Dit geeft bij mij het volgende plaatje:

Merk op dat ik in dit plaatje de hoeken die vaker voorkomen alvast een naam heb gegeven ( $\alpha$ en $\beta$ ). Vaak geef ik die ook een aparte kleur, zodat ik in één oogopslag zie welke hoeken gelijk zijn.

Stap 2: Het oplossen van het probleem

Gelijke hoeken doet mij direct denken aan gelijkvormige driehoeken. Ik kijk daarom of de hoeken $\angle DAP$ en $\angle AC$ ( $\alpha$ in het plaatje) in driehoeken zitten die gelijkvormige zijn met elkaar. $\angle DAP$ zit alleen in de driehoek $\triangle DAP$ en hoek $\angle ACP$ zit in de driehoeken $\triangle ACP$ en $ACD$ .

$\triangle DAP$ en $\triangle CAP$ lijken in de verste verte niet gelijkvormig ( $\triangle CAP$ heeft een stompe hoek en $\triangle DAP$ niet), maar ik zie dat $\triangle ACD$ en $\triangle PAD$ ook nog $\angle ADP = \angle CDA$ gemeenschappelijk hebben. Daarom geldt dus $\triangle ACD\sim \triangle DAP$ .
Aan de andere kant van het figuur zie ik nu soortgelijke gelijkvormige driehoeken: $\triangle DBP \sim \triangle DCB$ .

Nu ik gelijkvormigheden heb, maak ik eerst een tabel van wat deze gelijkvormigheden zeggen over de zijden:

Ik lees op dit punt nog even in de vraag wat we ook alweer wilden bewijzen. Dat is dat $AD=DB$ (want dan ligt $D$ in het midden van $AB$ ). Het is dus logisch om in de tabellen de kolommen te pakken waar de zijden $AD$ en $DB$ in voorkomen. Daarin krijg ik uitdrukkingen voor $AD$ en $DB$ :

$\frac{AD}{CD}=\frac{DP}{AD}$ geeft $AD^2=CD\cdot DP$
$\frac{DB}{DC}=\frac{DP}{DB}$ geeft $DB^2=DC\cdot DP$

Uiteraard is $CD\cdot DP$ hetzelfde als $DC\cdot DP$ . We hebben dus $AD^2=DB^2$ . Aangezien lengtes positief zijn, volgt daar het gevraagde $AD=DB$ uit.

Stap 3: Het opschrijven van het nette bewijs

De laatste stap is altijd om het bewijs op een nette manier op te schrijven, waarbij je alle denkstappen duidelijk opschrijft. Ik doe dat in dit geval als volgt:

Vanwege het gelijkvormigheidsgeval $hh$ zijn de driehoeken $\triangle ADP$ en $\triangle CDA$ gelijkvormig. We hebben namelijk $\angle ADP=\angle CDA$ (zelfde hoek) en $\angle DAP=\angle BAP=\angle ACP=\angle ACD$ (gegeven).
Uit deze gelijkvormigheid volgt $\frac{AD}{CD}=\frac{DP}{AD}$ . Kruiselings vermenigvuldigen geeft $AD^2=CD\cdot DP$ .
Vanwege het gelijkvormigheidsgeval $hh$ zijn de driehoeken $\triangle DBP$ en $\triangle DCB$ gelijkvormig. We hebben namelijk $\angle BDP=\angle CDB$ (zelfde hoek) en $\angle DBP=\angle ABP=\angle BCP = \angle BCD$ (gegeven).
Uit deze gelijkvormigheid volgt $\frac{DB}{CD}=\frac{DP}{DB}$ . Kruiselings vermenigvuldigen geeft $DB^2=CD\cdot DP$ .
We hebben dat $AD^2=CD\cdot DP = DB^2$ . Aangezien lengtes positief zijn, volgt hieruit $AD=DB$ . Uit dit gegeven in combinatie met dat $D$ op het lijnstuk $AB$ ligt, kunnen we concluderen dat $D$ het midden van lijnstuk $AB$ is.

Pagina's: 12345

Wiskundewedstrijden

Persoonlijk vind ik puzzels uit wiskundewedstrijden een van de leukste manieren om aan wiskunde te werken. Dat komt vooral doordat iedere Olympiadepuzzel net weer een andere oplosstrategie vraagt. Hierdoor vervelen Olympiadepuzzels voor mij nooit.

Wel is het zo dat je door veel te oefenen steeds beter kan worden in deze puzzels. In mijn ogen is de beste manier om hiervoor de opdrachten op de volgende manier te doen:

Stap 1: Probeer ze zelf
Besteed veel tijd aan een probleem, waarbij je met het probleem speelt. De puzzels zijn gemaakt om even mee bezig te zijn en verwacht dus niet dat je direct de oplossing ziet. Dat vraagt proberen en alleen door dit eerst zelf te doen, kom je bij de oplossing.
Stap 2: Vergelijk je oplosproces
Nadat je een probleem geprobeerd hebt, is het nuttig om jouw oplosproces met die van iemand anders te vergelijken. Kijk naar wat diegene anders heeft gedaan. Vraag je af of dat hier handiger is en onthoud de verschillen voor volgende problemen waar die techniek vast ook weer van pas komt.

Op deze site vind je veel puzzels om eerst zelf te proberen. Als je dat gedaan hebt, kun je mijn antwoorden vergelijken. Ik wens je daarbij veel plezier toe!

HAVO Wiskunde B

Op deze website vind je examensommen van HAVO 5 uitgewerkt per thema. Deze thema’s zijn:

Driehoeken
Cirkels
Goniometrie
Differentiëren (komt nog)
Exponentieel verband (komt nog)
Logaritmes (komt nog)
Redeneren
Contextsommen (komt nog)
Oefeneindexamen (komt nog)

Daarnaast vind je hier op pagina 2 een overzicht van de belangrijkste basisvaardigheden voor je examen. Dat zijn:

Pagina 2: Exacte-waarden-cirkel
Pagina 3: Goniometrische vergelijkingen
Pagina 4: Periodieke verbanden
Pagina 5: Afstanden
Pagina 6: Cirkels
Pagina 7: Hoek tussen lijnen
Pagina 8: Rechthoekige driehoeken
Pagina 9: Overige driehoeken

Pagina's: 123456

Bewegingsvergelijkingen (VWO 6 wis B)

Hier kun je een bestand downloaden met 10 examencontexten over bewegingsvergelijkingen. Tips en uitwerkingen van deze contexten vind je op de volgende pagina’s:

Pagina 2: Bewegend punt (som uit 2018)
Pagina 3: Beweging over twee lijnen
Pagina 4: Bewegend punt (som uit 2019)
Pagina 5: Een baan
Pagina 6: Twee bewegende punten
Pagina 7: Een ellipsvormige baan
Pagina 8: Lus
Pagina 9: Een hartvormige kromme
Pagina 10: Tussen twee bewegende punten
Pagina 11: Lemniscaat

Pagina's: 1234567891011

Veelhoeken (VWO 6 wis B)

Hier kun je een bestand downloaden met tien examencontexten over veelhoeken. Tips en uitwerkingen van deze contexten vind je op de volgende pagina’s:

Pagina 2: Onbekende zijde
Pagina 3: Op de diagonaal van een vierkant
Pagina 4: Vereenvoudigde sterrenkunde
Pagina 5: Drie vierkanten in een rechthoek
Pagina 6: Vierkanten
Pagina 7: Slingshot
Pagina 8: Vier vierkanten
Pagina 9: Gekanteld vierkant
Pagina 10: Driehoek met bewegend hoekpunt
Pagina 11: Drie op een rij

Pagina's: 1234567891011

Cryptografie les 11: RSA

In de vorige les hebben we gezien dat het mogelijk is om een geheim wachtwoord af te spreken, terwijl anderen meeluisteren. Een vereiste van deze techniek is echter wel dat je een kanaal hebt waar je informatie kunt delen zonder dat iemand halverwege de berichten kan aanpassen (dat was de man in the middle attack die we vorige keer gezien hebben).

In deze les gaan we naar RSA kijken waarmee je zowel kunt zorgen dat voor iedereen duidelijk is dat het bericht van jou afkomstig is als dat je kunt zorgen dat het bericht alleen voor de ontvanger te lezen is.

Stelling van Euler

RSA maakt gebruik van de zogenaamde stelling van Euler. Deze stelling heeft te maken met de functie $\phi(n)$ die telt hoeveel getallen $m$ kleiner of gelijk dan $n$ er zijn waarvoor geldt $\text{ ggd }(m, n)=1$ . Zo is bijvoorbeeld $\phi(6)=2$ , want alleen voor 1 en 5 geldt dat $\text{ ggd }(6, 1)=\text{ ggd }(6, 5)=1$ .

Opdracht 1:
Bereken $\phi(n)$ voor $n=1$ t/m $n=10$ .

Uitwerking:

$\phi(1)=1$
$\phi(2)=1$
$\phi(3)=2$
$\phi(4)=2$
$\phi(5)=4$
$\phi(6)=2$
$\phi(7)=6$
$\phi(8)=4$
$\phi(9)=6$
$\phi(10)=4$

In de antwoorden van $\phi(n)$ zitten mooie patronen. Voor deze les is het alleen belangrijk om te weten wat $\phi(p)$ en $\phi(p\cdot q)$ is, waarbij zowel $p$ als $q$ priemgetallen zijn.

Opdracht 2:
a) Bereken $\phi(p)$ voor een aantal priemgetallen $p$ . Geef dan een formule voor $\phi(p)$ , waarbij je het antwoord uitdrukt in $p$ .
b) Bereken $\phi(2\cdot p)$ voor een aantal priemgetallen $p>2$ . Geef dan een formule voor $\phi(2\cdot p)$ , waarbij je het antwoord uitdrukt in $p$ .
c) Bereken $\phi(3\cdot p)$ voor een aantal priemgetallen $p>3$ . Geef dan een formule voor $\phi(3\cdot p)$ , waarbij je het antwoord uitdrukt in $p$ .
d) Probeer nu een algemeen formule te vinden voor $\phi(p\cdot q)$ voor verschillende priemgetallen $p$ en $q$ . Je kunt hierbij natuurlijk nog wat meer proberen.

Uitwerking a:

Voor een priemgetal $p$ geldt dat $\text{ ggd }(a,p)=1$ voor ieder getal $a<p$ . Dat geeft dus $\phi(p)=p-1$

Uitwerking b:

Bij het uitrekenen van een aantal voorbeelden ga je wellicht patronen zien:

$\phi(2\cdot 3) = 2 = \phi(3)$
$\phi(2\cdot 5) = 4 = \phi(5)$
$\phi(2\cdot 7) = 6 = \phi(7)$

Het antwoord lijkt dus ook hier $\phi(2\cdot p) = p-1$ te zijn. De reden is dat alle oneven getallen behalve $p$ kleiner dan $2p$ werken. Dat zijn er precies $p-1$ .

Uitwerking c:

Bij het uitrekenen van een aantal voorbeelden ga je wellicht patronen zien:

$\phi(3\cdot 5) = 8 = 2\cdot \phi(5)$
$\phi(3\cdot 7) = 12 = 2\cdot \phi(7)$
$\phi(3\cdot 11) = 20 =2\cdot \phi(11)$

Het antwoord lijkt hier dus $\phi(2\cdot p) = 2\cdot \phi(p)=2p-2$ te zijn. De reden is dat alle drievouden afvallen. Van de getallen die één meer dan een drievoud zijn, zijn er $p-1$ die ook geen factor $p$ hebben. Dat geldt ook voor de getallen die twee meer zijn dan een drievoud. Voor deze $2(p-1)$ getallen $m$ geldt dus $\text{ggd}(3p,m)=1$ .

Uitwerking d:

De formule is $\phi(p\cdot q)=(p-1)(q-1)$ . De reden is dat van de $pq-1$ tot en met $pq-1$ er $p-1$ deelbaar zijn door $q$ en $q-1$ deelbaar zijn door $p$ . Voor alle andere getallen $m$ geldt $\text{ggd}(pq,m)=1$ . Dat zijn er $\phi(p\cdot q)=pq-1-(p-1)-(q-1)=pq-p-q+1=(p-1)(q-1)=\phi(p)\cdot\phi(q)$ .

De formule $\phi(n)$ is voor ons heel nuttig, omdat Euler bewezen heeft dat $a^{\phi(n)} \text{ mod } n=1$ als $\text{ggd}(a,n)=1$ . Deze stelling die de stelling van Euler heet, zullen we in deze cursus niet bewijzen, maar alleen gebruiken.

Opdracht 3:
a) Controleer de formule van Euler door met je rekenmachine $5^{\phi(7)} \text{ mod } 7$ en $3^{\phi(8)} \text{ mod } 8$ .
b) Bereken ook $2^{\phi(12)} \text{ mod } 12$ . Leg uit waarom dit geen tegenspraak is voor de stelling van Euler.

Uitwerking a:

Als je het goed berekent hebt, krijg je $5^{\phi(7)} \text{ mod } 7=1$ en $3^{\phi(8)} \text{ mod } 8=1$ .

Uitwerking b:

$2^{\phi(12)} \text{ mod } 12=2^4 \text{ mod } 12=16\text{ mod } 12=4$
Dit is geen tegenspraak, omdat de stelling van Euler alleen geldt als $\text{ggd}(a,n)=1$ en dat is niet waar, omdat $\text{ggd}(2,12)=2$ .

Opdracht 4:
Maak de opdracht Euler’s Totient op CryptoHack. Je moet daarbij uitzoeken wat $\phi(857504083339712752489993810777\cdot 1029224947942998075080348647219$ is waarbij zowel 857504083339712752489993810777 als 1029224947942998075080348647219 priemgetallen zijn.

Hint:

We hebben in opdracht 2d geleerd dat $\phi(p\cdot q)=(p-1)(q-1)$ als $p$ en $q$ priemgetallen zijn.

Pagina's: 123

Cryptografie les 10: Diffie-Hellman

In de vorige les hebben we gezien dat we met XOR een bericht veilig kunnen versleutelen. Hiervoor moet je echter wel een zeer lange string van enen en nullen afgesproken hebben. In deze les gaan we zien hoe je zonder vooraf afgesproken string toch een geheime boodschap aan elkaar kan sturen. Hiervoor gaan we het zogenaam Diffie-Hellman protocol gebruiken. Dit maakt gebruik van het machtsverheffen van een grote klassen bij modulo rekenen. Daar gaan we op deze pagina daarom mee beginnen.

Modulair machtsverheffen

Als je modulo rekent, mag je op ieder moment een getal vervangen door een getal uit dezelfde moduloklassen. Zo hebben alle onderstaande sommen dezelfde uitkomst:

$13 \cdot 75 \text{ mod } 7$
$13 \cdot 5 \text{ mod } 7$
$6\cdot 5 \text{ mod } 7$

Deze truc kunnen we gebruiken door als we een grote som modulo een getal willen uitrekenen we ook steeds tussendoor de getallen kunnen verkleinen. Zo wordt $101\cdot 123\cdot 109 \text{ mod } 99$ na vereenvoudigen
$100\cdot 123\cdot 109 \text{ mod } 99 = 2\cdot 24\cdot 10\text{ mod } 99 = 480 \text{ mod } 99 = 84$ .

Opdracht 1:
a) Bereken uit je hoofd $14\cdot 27 \text{ mod } 11$ .
b) Bereken uit je hoofd $323572834723 \cdot 29387423 \cdot 23948123431 \text{ mod } 10$ .

Uitwerking a:

$14\cdot 27 \text{ mod } 11= 3\cdot 5 \text{ mod } 11 = 4$

Uitwerking b:

$323572834723 \cdot 29387423 \cdot 23948123431 \text{ mod } 10 = 3\cdot 3\cdot 1\text{ mod } 10 = 9$

Op de rekenmachine kun je ook modulo berekenen. Op de TI doe je dit met de Remainder-functie onder math->num->remainder (optie 0). Daarbij is remainder(5,2) hetzelfde als $5 \text{ mod } 2$ .
Op de CASIO (GR) kun je dit doen met OPTN -> NUMERIC -> pijltje naar rechts -> MOD.

De onderstaande opgave is te groot voor je rekenmachine om meteen uit te rekenen. Je kunt echter een paar slimme tussenstappen doen (op de manier uit opdracht 1) waarmee dat wel kan.

Opdracht 2:
Bereken $9^{256} \text{ mod } 103$ . Je mag een rekenmachine gebruiken, maar geen Python-programma.

Hint:

Bereken achtereenvolgens $9^2 \text{ mod } 103$ , $9^4 \text{ mod } 103$ , $9^8 \text{ mod } 103$ , $9^{16} \text{ mod } 103$ , enzovoorts. Hierbij kun je $9^{2n}\text{ mod } 103 = 9^n \cdot 9^n \text{ mod }103$ .

Uitwerking:

$9^2 \text{ mod } 103 = 9\cdot 9 \text{ mod 103} = 81$
$9^4 \text{ mod } 103 = 9^2\cdot 9^2 \text{ mod 103} = 81\cdot 81 \text{ mod 103} = 72$
$9^8 \text{ mod } 103 = 9^4\cdot 9^4 \text{ mod 103} = 72\cdot 72 \text{ mod 103} = 34$
$9^{16} \text{ mod } 103 = 9^8\cdot 9^8 \text{ mod 103} = 34\cdot 34 \text{ mod 103} = 23$
$9^{32} \text{ mod } 103 = 9^{16}\cdot 9^{16} \text{ mod 103} = 23\cdot 23 \text{ mod 103} = 14$
$9^{64} \text{ mod } 103 = 9^{32}\cdot 9^{32} \text{ mod 103} = 14\cdot 14 \text{ mod 103} = 93$
$9^{128} \text{ mod } 103 = 9^{64}\cdot 9^{64} \text{ mod 103} = 93\cdot 93 \text{ mod 103} = 100$
$9^{256} \text{ mod } 103 = 9^{128}\cdot 9^{128} \text{ mod 103} = 100\cdot 100 \text{ mod 103} = 9$

De methode die in de hint en uitwerking hierboven uitgevoerd wordt, kun je veralgemeniseren zodat hij voor iedere macht werkt. Daarbij schrijf je de macht eerst als een product van machten met een tweemacht als exponent. Dit kun je snel doen door 12 te schrijven als een som van tweemachten. Aangezien 12 gelijk is aan 8+4 geldt dus $3^{12} \text{ mod } 7 = 3^{8}\cdot 3^4 \text{ mod } 7$ . In het algemeen kun je de som van tweemachten vinden met behulp van de binaire schrijfwijze van 12 (1100 geeft dus aan dat $12 =8\cdot 1+4\cdot 1+2\cdot 0+1\cdot 0$ ).

Vervolgens reken je net als in opdracht 1 de machten uit met een tweemacht als exponent en vermenigvuldig je op het eind nog de juiste tweemachten. Dat ziet er bij $3^{12} \text{ mod } 7$ als volgt uit:

$3^{2} \text{ mod } 7 = 3\cdot 3 \text{ mod } 7 = 2$
$3^4 \text{ mod } 7 = 3^2\cdot 3^2 \text{ mod } 7 = 2\cdot 2 \text{ mod } 7 = 4$
$3^8 \text{ mod } 7 = 3^4\cdot 3^4 \text{ mod } 7 = 4\cdot 4 \text{ mod } 7 = 2$
$3^{12} \text{ mod } 7 = 3^8\cdot 3^4 \text{ mod } 7 = 2\cdot 4 \text{ mod } 7 = 1$

Opdracht 3:
a) Bereken met bovenstaand algoritme $7^{74} \text{ mod } 29$ . Je mag een rekenmachine gebruiken, maar geen Python-programma.
b) Waarom zul je met het bovenstaande algoritme wel $2^{1111111111111111111111777777755555333221} \text{ mod } 1111111112223333333344455566777777779999$ met Python kunnen uitrekenen, terwijl dit met herhaald vermenigvuldigen niet gaat?

Uitwerking a:

$7^{2} \text{ mod } 29 = 7\cdot 7 \text{ mod } 29 = 20$
$7^4 \text{ mod } 29 = 7^2\cdot 7^2 \text{ mod } 29 = 20\cdot 20 \text{ mod } 29 = 23$
$7^8 \text{ mod } 29 = 7^4\cdot 7^4 \text{ mod } 29 = 23\cdot 23 \text{ mod } 29 = 7$
$7^{16} \text{ mod } 29 = 7^8\cdot 7^8 \text{ mod } 29 = 7\cdot 7 \text{ mod } 29 = 20$
$7^{32} \text{ mod } 29 = 7^{16}\cdot 7^{16} \text{ mod } 29 = 20\cdot 20 \text{ mod } 29 = 23$
$7^{64} \text{ mod } 29 = 7^{32}\cdot 7^{32} \text{ mod } 29 = 23\cdot 23 \text{ mod } 29 = 7$
$7^{74} \text{ mod } 29 = 7^{64}\cdot 7^{8}\cdot 7^2\text{ mod } 29 = 7\cdot 7\cdot 20\text{ mod } 29 = 23$

Uitwerking b:

Het aantal keer dat je moet vermenigvuldigen is maximaal $2\cdot{}^2\!\text{log}(x)$ als $x$ de grootte van de exponent is. Dat zijn bij 1111111111111111111111777777755555333221 ongeveer 266 vermenigvuldigingen. Dat is goed te doen, terwijl 1111111111111111111111777777755555333221 keer vermenigvuldigen met 2 niet gaat lukken binnen realistische tijd.

De ingebouwde functie pow in Python rekent met het bovenstaande algoritme machten modulo een getal uit. Om $3^7\text{ mod } 37$ uit te rekenen, type je pow(3,7,37).

Opdracht 4:
Bereken $2^{1111111111111111111111777777755555333221} \text{ mod } 1111111112223333333344455566777777779999$

Kopieerbare versie van de getallen:

g = 2
exponent = 1111111111111111111111777777755555333221
moduloklasse = 1111111112223333333344455566777777779999

Uitwerking a:

Je kunt het volgende programma gebruiken:

print(pow(2,1111111111111111111111777777755555333221,1111111112223333333344455566777777779999))

Het antwoord is dus $2^{1111111111111111111111777777755555333221} \text{ mod } 1111111112223333333344455566777777779999 = 1021207380999906245135905479721960323317$

Bonusopdracht:
Schrijf een programma die zonder gebruik te maken van de pow-functie de som uit opdracht 4 berekent.

Hint 1:

Je wilt eigenlijk de exponent schrijven als een binair getal. Hier heb je in opdracht 12b van les 8 al een programma voor geschreven. Dit programma kun je als basis gebruiken.

Hint 2:

Als er een 1 staat op plaats $k$ van achteren in de binaire schrijfwijze van 1111111111111111111111777777755555333221 moet het antwoord vermenigvuldigd worden met een factor $2^{k}$ . Als er een 0 staat in de binaire schrijfwijze hoef je met niets te vermenigvuldigen.

Uitwerking:

Zie allereerst de hints hierboven. Bij iedere stap in het algoritme houden we bij wat $2^A\text{ mod } 1111111112223333333344455566777777779999$ is in de variabele macht. Bij de volgende stap kunnen we dan de nieuwe macht $2^{2A}$ berekenen met (macht*macht) % moduloklasse.
In het algoritme vermenigvuldigen we al deze machten die op een plek staan waar in de binaire schrijfwijze van de exponent 1111111111111111111111777777755555333221 een 1 staat.

g = 2
exponent = 1111111111111111111111777777755555333221
moduloklasse = 1111111112223333333344455566777777779999

antwoord = 1
macht = g
while exponent > 0:
    if exponent % 2 == 1:
        antwoord = antwoord * macht % moduloklasse
    macht = (macht * macht) % moduloklasse
    exponent //= 2
print(antwoord)

Het antwoord is dus $2^{1111111111111111111111777777755555333221} \text{ mod } 1111111112223333333344455566777777779999 = 1021207380999906245135905479721960323317$

Pagina's: 1234