Cryptografie les 6: Algoritme van Euclides

In opdracht 3 van de vorige les probeerden we decryptiefuncties te vinden bij encryptiefuncties als $E(x)=(3x+5) \text{ mod } 26$ en $E(x)=5x \text{ mod } 26$ . Het doel van deze les is om een snellere manier te vinden om deze decryptiefuncties te bepalen. Hiervoor gaan we het algoritme van Euclides gebruiken. Dit is in eerste instantie een algoritme om de grootst gemene deler te bepalen, maar we gaan zien dat die ook voor andere vraagstukken nuttig is.

Delers

We beginnen met het begrip deler. We zeggen dat $a$ een deler is van $b$ als $\frac{b}{a}$ een geheel getal is.

Opdracht 1:
a) Is 5 een deler van 45?
b) Is 45 een deler van 5?
c) Is 17 een deler van 17?
d) Is 1 een deler van 3?
e) Is 12 een deler van 0?
f) Is 0 een deler van 12?

Uitwerking:

a) Ja, want $\frac{45}{5}=9$ en dat is geheel.
b) Nee, want $\frac{5}{45}=\frac{1}{9}$ is niet geheel.
c) Ja, want $\frac{17}{17}=1$ en dat is geheel.
d) Ja, want $\frac{3}{1}=3$ en dat is geheel.
e) Ja, want $\frac{0}{12}=0$ en dat is geheel.
f) nee, want $\frac{12}{0}$ kan niet.

Opdracht 2: (Bron: Project Euler probleem 1)
De lijst van alle positieve gehele getallen onder de 10 die veelvouden van 3 of 5 zijn, zijn 3, 5, 6 en 9. Deze getallen hebben een som van 23. Schrijf in Python een programma die de som van alle positieve gehele getallen onder de 1000 vindt die een veelvoud van 3 of 5 zijn.

Uitwerking:

In Python kunnen we met $b\%a==0$ controleren of $a$ een deler is van $b$ . Het onderstaande programma test dus voor ieder getal onder de 1000 of die een deler is van $a$ of $b$ en als dat het geval is, wordt die bij de uitkomst opgeteld.

som = 0
for n in range(1,1000):
    if n % 3 == 0 or n % 5 == 0:
        som += n
print(som)

Het antwoord is dan 233168.

Pagina's: 12345