Modulair rekenen met exponent

Matrixrekenen, vectorruimten, groep-en ringstructuren, (lineaire) tranformaties.
Plaats reactie
webtest
Nieuw lid
Nieuw lid
Berichten: 1
Lid geworden op: 01 jul 2014, 20:11

Modulair rekenen met exponent

Bericht door webtest » 01 jul 2014, 20:18

Ik zit met een vraagstuk, ik wil vooral weten of de oplossing überhaupt op deze manier uit te rekenen is.

Als ik dit heb:


C = uitkomst
M = ingevuld door "gebruiker" van formule (in dit geval 119)
e = 11
n = 899

En ik doe:



Is van het getal C (dus 595) dan weer het getal M te vinden? Dus is deze formule om te draaien zodat je weer 119 krijgt?
Of is dit onmogelijk?

SafeX
Moderator
Moderator
Berichten: 14278
Lid geworden op: 29 dec 2005, 11:53

Re: Modulair rekenen met exponent

Bericht door SafeX » 01 jul 2014, 21:16

3^2=4 (mod 5)
3^6=4 (mod 5)

Dus wat bedoel je ...

David
Moderator
Moderator
Berichten: 4927
Lid geworden op: 14 mei 2009, 16:22

Re: Modulair rekenen met exponent

Bericht door David » 02 jul 2014, 13:29

Bedoel je:

Gegeven C, e en N in de congruentie , vind M?
Stap 1 van het oplossen van een probleem is te erkennen dat je een probleem hebt.
(Raffiek Torreman)

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

Re: Modulair rekenen met exponent

Bericht door arno » 02 jul 2014, 18:53

SafeX schreef:3^2=4 (mod 5)
3^6=4 (mod 5)

Dus wat bedoel je ...
Zie http://www.wetenschapsforum.nl/index.ph ... -exponent/
"Mathematics is a gigantic intellectual construction, very difficult, if not impossible, to view in its entirety." Armand Borel

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

Re: Modulair rekenen met exponent

Bericht door arie » 03 jul 2014, 09:28

webtest schreef: (vrij vertaald):

We hebben


en specifiek



Is hieruit het getal M te vinden? Dus is deze formule om te draaien zodat je weer M = 119 krijgt?
Of is dit onmogelijk?
Voor kleine waarden van n is M terug te vinden, voor grote waarden van n niet.
Dat wil zeggen: voor kleine waarden lukt dit met de hand, voor grote waarden zelfs niet met de computer.
Hier is het RSA encryptiesysteem op gebaseerd.

[1] Kleine waarden van n:
- mogelijkheid 1: In de link van arno gaan ze alle restklassen af (0 t/m 898), dat is voor kleine getallen goed te doen.
- mogelijkheid 2:
a) ontbind 899 in factoren: 899 = 29*31 (snel)
b) eulerphi(899) = eulerphi(29*31) = (29-1)*(31-1) = 840 (supersnel)
c) bepaal de inverse van 11 mod 840: 611 (snel via het uitgebreide algoritme van Euclides)
d) bepaal M = 595^611 mod 899 = 119 mod 899 (snel via modulair machtsverheffen)

[2] Middelgrote n: bijvoorbeeld n = 225814191023 (een getal van 12 cijfers)
Voorbeeld: M^123456789101 = 153613986672 mod 225814191023
- mogelijkheid 1: Alle restklassen afgaan met een computer zal nu al erg lang gaan duren.
- mogelijkheid 2:
a) Ontbinden in factoren (2 factoren van 6 cijfers) is met computer nog redelijk snel te doen.
b) c) d): nog steeds snel.
Dus met mogelijkheid 2 is M nog terug te vinden.

[3] Grote n: bijvoorbeeld een getal van 100 cijfers:
nu gaat ook ontbinding in factoren (methode 2) te lang duren.

Dus zolang niemand hele grote getallen zeer snel kan ontbinden is het RSA systeem veilig.

Plaats reactie