Hallo,
ik heb een vraag. Ik heb wat problemen met de kleine stelling van fermat. Zou iemand mij kunnen helpen met de volgende vragen:
10^6 (mod 7)
6^126 (mod 127)
33^96 (mod 97)
57^100 (mod 101)
871^10000 (mod 9973)
Zou iemand mij hier uitleg over kunnen geven?
Alvast bedankt!
Cryptologie (kleine stelling van Fermat)
-
zeekomkommer
- Nieuw lid
- Berichten: 7
- Lid geworden op: 17 feb 2009, 19:35
Re: Cryptologie (kleine stelling van Fermat)
De kleine stelling van Fermat zegt:
als p een priemgetal is en n een positief geheel getal, dan is (n^p - n) deelbaar door p, ofwel:
)
)
)
Gebruik dit in je opgaven (alle opgaven zijn modulo een priemgetal).
Noot: alleen in de laatste opgave:
 = ((871^{28})*(871^{9972})) (mod 9973))
heb je nodig:
 (mod 9973) = 5801 (mod 9973))
als p een priemgetal is en n een positief geheel getal, dan is (n^p - n) deelbaar door p, ofwel:
Gebruik dit in je opgaven (alle opgaven zijn modulo een priemgetal).
Noot: alleen in de laatste opgave:
heb je nodig:
-
zeekomkommer
- Nieuw lid
- Berichten: 7
- Lid geworden op: 17 feb 2009, 19:35
Re: Cryptologie (kleine stelling van Fermat)
Dankjewel!
alleen hoe doe je dat bij een opgave zoals:
57^104 (mod 101)
alvast bedankt
alleen hoe doe je dat bij een opgave zoals:
57^104 (mod 101)
alvast bedankt
Re: Cryptologie (kleine stelling van Fermat)
Of de eerste, zou echt heel tof zijn! Of geldt het invullen van die formule ook?
Ik zit hier ook mee. Ik vermoed serieus dat we dezelfde studie doen...
Ik zit hier ook mee. Ik vermoed serieus dat we dezelfde studie doen...
Re: Cryptologie (kleine stelling van Fermat)
(1)
} \equiv 57^4 * 57^{100} \equiv 57^4 * 1 \equiv 57^4 (mod 101))
101 is een priemgetal, dus volgens de kleine stelling van Fermat geldt: 57^100 = 1 (mod 101)
Je splitst in dergelijke berekeningen steeds een zo groot mogelijk veelvoud van (p-1) af in de macht die je zoekt, zeg a*(p-1).
Er geldt dan:
+r} \equiv n^r * n^{a*(p-1)} \equiv n^r * \left(n^{(p-1)}\right)^a \equiv n^r * 1^a \equiv n^r * 1 \equiv n^r (mod p))
De macht n^r (met r<(p-1)) moet je dan nog wel bepalen.
In bovenstaand voorbeeld geldt:
p=101
n=57
m=104
a=1
r=4
(2)
57^2 = 3249 = 17 (mod 101)
57^4 = 57^2 * 57^2 = 17 * 17 = 289 = 87 (mod 101).
Dus 57^104 = 87 (mod 101)
(3)
De kleine stelling van Fermat geldt voor elk priemgetal p waarmee we modulo rekenen
(4)
Wellicht ten overvloede:
Om in het algemeen (dus m niet noodzakelijk een priemgetal)
)
snel te bepalen maak je (mod m) eerst een tabel met 2^n machten van a: begin met a^(2^0) = a^1, elke volgende regel in de tabel is het kwadraat van de vorige regel, bv n.a.v. je eerste post:
)
 \equiv (3 * 3) \equiv 9 \equiv 2 (mod 7))
 \equiv (2 * 2) \equiv 4 (mod 7))
 \equiv (4 * 4) \equiv 16 \equiv 2(mod 7))
Je krijgt zo (mod m) de machten a^1, a^2, a^4, a^8, a^16, a^32, etc
Herschrijf vervolgens a^b als product van deze machten (dus b als som van de exponenten) en bepaal daarvan de waarde (mod m) mbv de tabel:
bijvoorbeeld: 10^13 = 10^(8+4+1) = 10^8 * 10^4 * 10^1 = 2 * 4 * 3 = 24 = 3 (mod 7)
en
10^6 = 10^(4+2) = 10^4 * 10^2 = 4 * 2 = 8 = 1 (mod 7)
Dit laatste wisten we al dankzij Fermat.
101 is een priemgetal, dus volgens de kleine stelling van Fermat geldt: 57^100 = 1 (mod 101)
Je splitst in dergelijke berekeningen steeds een zo groot mogelijk veelvoud van (p-1) af in de macht die je zoekt, zeg a*(p-1).
Er geldt dan:
De macht n^r (met r<(p-1)) moet je dan nog wel bepalen.
In bovenstaand voorbeeld geldt:
p=101
n=57
m=104
a=1
r=4
(2)
57^2 = 3249 = 17 (mod 101)
57^4 = 57^2 * 57^2 = 17 * 17 = 289 = 87 (mod 101).
Dus 57^104 = 87 (mod 101)
(3)
De kleine stelling van Fermat geldt voor elk priemgetal p waarmee we modulo rekenen
(4)
Wellicht ten overvloede:
Om in het algemeen (dus m niet noodzakelijk een priemgetal)
snel te bepalen maak je (mod m) eerst een tabel met 2^n machten van a: begin met a^(2^0) = a^1, elke volgende regel in de tabel is het kwadraat van de vorige regel, bv n.a.v. je eerste post:
Je krijgt zo (mod m) de machten a^1, a^2, a^4, a^8, a^16, a^32, etc
Herschrijf vervolgens a^b als product van deze machten (dus b als som van de exponenten) en bepaal daarvan de waarde (mod m) mbv de tabel:
bijvoorbeeld: 10^13 = 10^(8+4+1) = 10^8 * 10^4 * 10^1 = 2 * 4 * 3 = 24 = 3 (mod 7)
en
10^6 = 10^(4+2) = 10^4 * 10^2 = 4 * 2 = 8 = 1 (mod 7)
Dit laatste wisten we al dankzij Fermat.