[Centraal] Bèta 'huiswerk en vragen topic'

Ok zit hier met een probleempje

ik moet laten zien hoe een programma een rsa code decoderert (publieke sleutel encryptie)
je hebt dus:

plaintekst = C^d mod n

maar als die getallen gigantisch groot zijn, past dat natuurlijk niet in het geheugen
maar hoe is dat simpeler te doen, zit naar de getal theorie te kijken maar ik weet niet waar ik moet beginnen , en ik wil echt een 7 op wiskunde .
Waarom o waarom begin ik dan ook aan dit onderwerp als ng'er , ik kan uitleggen waarom je een brakke kop hebt na drinken maar dit gaat me echt te ver

Iig een duwtje in de goede richting plz?

quote:

Op maandag 10 april 2006 20:54 schreef the_jasper het volgende:
ik moet laten zien hoe een programma een rsa code decoderert (publieke sleutel encryptie)
(...)
Iig een duwtje in de goede richting plz?

Natuurlijk heb je al op de betreffende Wikipedia-pagina gekeken, en dan met name naar de verwijzing naar het "uitgebreid Euclidisch algoritme"...

Toch?

--edit--
Sorry, ik zie dat je alleen hoeft te decoderen. In dat geval wil je het verhaal over machtsverheffen door kwadrateren wel lezen denk ik. Helaas bevat de nederlandse variant van deze pagina geen inhoud, dus ik hoop dat je engels goed is. Mocht je er niet uitkomen, dan zien we je wel in dit topic

[ Bericht 26% gewijzigd door HenryHill op 10-04-2006 21:08:51 ]

Euclidisch algoritme heeft hier niets mee te maken. Je moet modulair machtsverheffen. Dat doe je als volgt.

Schrijf d binair op, dus d is een som van machten van 2. Reken nu C^(2^k) mod n uit tot en met de hoogste k die in deze schrijfwijze voorkomt. Dit doe je door telkens te kwadrateren en na het kwadrateren gelijk weer mod n reduceren. Dan is C^d mod n het product van geschikte C^(2^k), namelijk die tweemachten die in de binaire schrijfwijze voorkomen.

Euclidisch algorithme gaat uit van het berekenen van:
xa+yb=ggd(a,b)

Sorry dit snap ik ff niet

@thabit: zal het ff bekijken, thanx

Vanuit de google cache:
Mathematics of RSA encryption:

Exponentiation under a modulus is easier than exponentiation followed by a modulo operation. Let's face it, we're talking about taking very large numbers to very large powers here, and it would be totally easy to choke your computer.

So, for an 'easy' example, using numbers big enough to show off the method but small enough to write: Suppose we want to take 299 to the 153rd power, under a modulus of 355. The first thing we do is to note that 153 equals 128 + 16 + 8 + 1 (binary decomposition), and that therefore,

299^153 = 299^128 x 299^16 x 299^8 x 299^1.

Now, forgetting for the moment about the scary looking terms on the left, we can compute the one on the far right; it's 299, of course. Under the modulus, it's still 299. But knowing the one on the right, we can compute the one next to it: Doubling the powers by squaring the numbers, and applying the modulus to intermediate results, gives:


so

299^153 mod 355 = (151 x 16 x 146 x 299) mod 355

which looks a whole lot easier. Now, calculating the product and applying the modulus to intermediate results, we get:


so

299^153 mod 355 = 49.

And that is how you take a large number to a large power under a large modulus without causing your computer to choke. The constant application of the modulus operation to intermediate results prevents you from having to deal with any number larger than the square of the modulus in any case, and saves you from having to compute a number too big to fit in memory. On ordinary machines, you can't do this type of calculation in hardware registers as we are talking about (often) 1500- bit moduluses; but given any finite modulus, you do have an upperbound for the largest number you'll have to work with. You can code your routines for standard operations on that size number any way you like.

thanx beide
Dit is zeker een goed duwtje

Ik kan weer ff vooruit

T)he RSA is old and busted.
V)ette Elliptic Curves are new hotness.
P)lus Rijndael erbij.

Dit is het antwoord op je vraag RealRico:

U is de spanning of het potentiaalverschil in V (volt) is, I de stroom in A (ampère) en R de weerstand in Ω (ohm) .

quote:

Op dinsdag 11 april 2006 11:58 schreef Mangoworks2002 het volgende:
Dit is het antwoord op je vraag RealRico:

U is de spanning of het potentiaalverschil in V (volt) is, I de stroom in A (ampère) en R de weerstand in Ω (ohm) .

Ja, dat snapt hij ook, maar hij wil die rare afkortingen weten.

Wat moet je daarmee Rico? Als je het principe snapt is het toch goed.

Iedereen kent de wet van Ohm wel.

U=I*R

R -> staat voor Resistant
I -> staat voor Influence
U -> staat voor .....

Weet iemand weer de U voor staat?

Resistant
Influence
U.....

quote:

Op dinsdag 11 april 2006 11:59 schreef MrBean het volgende:

[..]

Ja, dat snapt hij ook, maar hij wil die rare afkortingen weten.

Wat moet je daarmee Rico? Als je het principe snapt is het toch goed.

De jongens uit mijn klas moeten een soort enceclopedy maken over electro.

Onzin om daar afkortingen in te willen zien. Vroeger was het V=IR, nu wordt meestal U=IR gebruikt. R is weerstand, I is stroomsterkte en V is spanning.

Misschien een U omdat de V al op was (voor snelheid, v).
Of misschien werden in de tijd dat de spanning ontdekt werd alle wetenschappelijke werken nog in het Latijn geschreven? Het Latijn gebruikt dezelfde letter voor V en U.
Ik heb trouwens ook een beetje mijn twijfels over Influence.

quote:

Op dinsdag 11 april 2006 12:05 schreef nerd4sale het volgende:
Misschien een U omdat de V al op was (voor snelheid, v).
Of misschien werden in de tijd dat de spanning ontdekt werd alle wetenschappelijke werken nog in het Latijn geschreven? Het Latijn gebruikt dezelfde letter voor V en U.
Ik heb trouwens ook een beetje mijn twijfels over Influence.

hoofdletter V is een eenheid, in de formule staan enkel grootheden. U is de grootheid van V.

Ja, sommige afkortingen kun je wel op het Latijn terugvoeren, v voor v[elocitas], en de onbekende in de wiskunde x komt echter via het Spaans uit het Arabisch, van het woord sjaj (dat ding/iets betekent), uit de tijd dat de x nog als 'sj' werd uitgesproken in het Spaans (Denk aan Don Quixote). Dus het zijn vaak wel (ad-hoc) afkortingen, maar er is ook vaak genoeg niet zo’n direct verband (alhoewel die R weleens als afkorting gekozen zou kunnen zijn).

Verder zijn letters vaak genoeg ‘op’ in Natuurkunde, zoveel letters zijn er immers niet.

Misschien Usage?
Usage = Resistance * Influence?

quote:

Op dinsdag 11 april 2006 12:10 schreef Nekto het volgende:
Ja, sommige afkortingen kun je wel op het Latijn terugvoeren, v voor v[elocitas], en de onbekende in de wiskunde x komt echter via het Spaans uit het Arabisch, van het woord sjaj (dat ding/iets betekent), uit de tijd dat de x nog als 'sj' werd uitgesproken in het Spaans (Denk aan Don Quixote). Dus het zijn vaak wel (ad-hoc) afkortingen, maar er is ook vaak genoeg niet zo’n direct verband (alhoewel die R weleens als afkorting gekozen zou kunnen zijn).

Verder zijn letters vaak genoeg ‘op’ in Natuurkunde, zoveel letters zijn er immers niet.

Dan houden we het op:

Undifiend

quote:

Op dinsdag 11 april 2006 12:08 schreef rezjeh het volgende:

[..]

hoofdletter V is een eenheid, in de formule staan enkel grootheden. U is de grootheid van V.

En dan heb je nog het verschil tussen cursief en rechtop, een verschil dat het verschil maakt tussen V en V. Grootheden staan meestal cursief, eenheden rechtop. (F=m•a), maar F is Farad. Alhoewel je hier ook met vectoren en vette letters kunt werken. Enfin. De F wordt hoe dan ook als grootheid en eenheid gebruikt.)

http://en.wikipedia.org/wiki/Electrical_resistance

formule is V=R*I


opgelost..

quote:

Op dinsdag 11 april 2006 12:10 schreef Mangoworks2002 het volgende:
Misschien Usage?
Usage = Resistance * Influence?

Misschien Utter-nonsense = Rambling * Ill-informed?

quote:

Op dinsdag 11 april 2006 12:15 schreef Mangoworks2002 het volgende:
http://en.wikipedia.org/wiki/Electrical_resistance

formule is V=R*I


opgelost..

Maar, bij http://en.wikipedia.org/wiki/Ohm's_law staat dat ook U en E gebruikt worden.

Hoi ,

is dit goed wat ik hier doe?

-(-2p - 3q - (-2p - 3q - (-2p -3q) -2p - 3q ) -2p - 3q) =
-(-2p - 3q - (-2p - 3q + 2p + 3q -2p - 3q ) -2p - 3q) =
-(-2p - 3q + 2p + 3q - 2p - 3q + 2p + 3q -2p - 3q) =
2p - 3q + 2p + 3q - 2p - 3q + 2p + 3q -2p - 3q = 2p - 3q

quote:

Op dinsdag 11 april 2006 12:20 schreef I-1 het volgende:
Hoi ,

is dit goed wat ik hier doe?

-(-2p - 3q - (-2p - 3q - (-2p -3q) -2p - 3q ) -2p - 3q) =
-(-2p - 3q - (-2p - 3q + 2p + 3q -2p - 3q ) -2p - 3q) =
-(-2p - 3q + 2p + 3q - 2p - 3q + 2p + 3q -2p - 3q) =
2p - 3q + 2p + 3q - 2p - 3q + 2p + 3q -2p - 3q = 2p - 3q

Van regel 3 naar 4 vergeet je van de -3q +3q te maken en omgekeerd, waardoor je op 2p - 3q uitkomt, terwijl het volgens mij 2p + 3q is.

Zeg dat A = -2p - 3q, dan krijg je:
-(A - (A - (A) + A) + A) = -(A - (A) + A) = -A = 2p + 3q. (M.a.w. je kunt al veel eerder beginnen met vereenvoudigen, door tot het laatst te bewaren maak je het jezelf niet echt gemakkelijker).

Hoi,

Dus dit is em:

-(-2p - 3q - (-2p - 3q - (-2p -3q) -2p - 3q ) -2p - 3q) =
-(-2p - 3q - (-2p - 3q + 2p + 3q -2p - 3q ) -2p - 3q) =
-(-2p - 3q + 2p + 3q - 2p - 3q + 2p + 3q -2p - 3q) =
2p + 3q - 2p - 3q + 2p + 3q - 2p - 3q + 2p + 3q = 2p + 3q

quote:

Op dinsdag 11 april 2006 12:49 schreef I-1 het volgende:
Hoi,

Dus dit is em:

-(-2p - 3q - (-2p - 3q - (-2p -3q) -2p - 3q ) -2p - 3q) =
-(-2p - 3q - (-2p - 3q + 2p + 3q -2p - 3q ) -2p - 3q) =
-(-2p - 3q + 2p + 3q - 2p - 3q + 2p + 3q -2p - 3q) =
2p + 3q - 2p - 3q + 2p + 3q - 2p - 3q + 2p + 3q = 2p + 3q

Ja, maar ik zou dan dit doen:
-(-2p - 3q - (-2p - 3q - (-2p -3q) -2p - 3q ) -2p - 3q) =
-(-2p - 3q - (-2p - 3q + 2p + 3q -2p - 3q ) -2p - 3q) =
-(-2p - 3q - (-2p - 3q ) -2p - 3q)=
-(-2p - 3q + 2p + 3q -2p - 3q)=
-(-2p - 3q ) = 2p + 3q

Immers, je ziet al direct dat je kunt vereenvoudigen.