Matematik
Modulus beregning
06. september 2006 af
Scorp-D (Slettet)
Hej.
Jeg er i gang med en rapport omkring RSA og skal lave modulus på nogle tal men kan ikke helt få det til at hænge sammen.
sådan som jeg har forstået modulus så er det at det er resten efter man har divideret med det største hele tal, f.eks. så er 6 modulus 4 = 2, og 21 modulus 4 = 1
Problemet for mig kommer først når tallene bliver store som det her:
920^17 modulus 2773 = ???
Jeg ved at det skal give 948 men kan ikke selv beregne det, når jeg prøver gør jeg sådan:
920^17 divideret med 2773 = 8,738e46 =>
8,0e46 gange 2773 = 2,2184e50 =>
920^17 minus 2,2184e50 = 2,04821e49
Det er jo ikke det rigtige resultat jeg får.
Er der nogen som kan fortælle mig hvad jeg gør forkert ?
På forhånd tak.
Jeg er i gang med en rapport omkring RSA og skal lave modulus på nogle tal men kan ikke helt få det til at hænge sammen.
sådan som jeg har forstået modulus så er det at det er resten efter man har divideret med det største hele tal, f.eks. så er 6 modulus 4 = 2, og 21 modulus 4 = 1
Problemet for mig kommer først når tallene bliver store som det her:
920^17 modulus 2773 = ???
Jeg ved at det skal give 948 men kan ikke selv beregne det, når jeg prøver gør jeg sådan:
920^17 divideret med 2773 = 8,738e46 =>
8,0e46 gange 2773 = 2,2184e50 =>
920^17 minus 2,2184e50 = 2,04821e49
Det er jo ikke det rigtige resultat jeg får.
Er der nogen som kan fortælle mig hvad jeg gør forkert ?
På forhånd tak.
Svar #1
06. september 2006 af fixer (Slettet)
Fordi du regner det ud på lommeregner som kun kan regne med et begrænset antal betydende cifre. Derved går store mængder information tabt.
Svar #2
06. september 2006 af fixer (Slettet)
En simpel metode at gøre det i hånden er som følger:
Antag vi ved resten ved division af 920^n og 920^m med 2773 er henholdvis r1 og r2:
920^n = 2773*a + r1
920^m = 2773*b + r2
for nogle (ligegyldige) heltal a, b.
Så kan vi finde resten ved division af 920^(n+m) med 2773 idet
920^(n+m) =
920^n * 920^m =
(2773*a+r1)*(2773*b+r2) =
(2773²)ab + (2773)a*r2 + (2773)b*r1 + r1*r2 (*)
tydeligvis har resten r1*r2 ved division med 2773 hvis r1*r2 < 2773; hvis r1*r2 > 2773 er resten r1*r2 minus et multipla af 2773.
Ved at benytte denne fremgangsmåde kan opstilles en tabel over resterne ved division af potenser af 920 med 2773:
n | rest
--------
1 | 920
2 | 635
3 | 1870
4 | 1140
5 | 606
6 | 147
:
og vi behøver ikke forstætte. For da 920^17 = 920^6 * 920^6 * 920^5 har 920^17 ifølge (*) samme rest som 147*147*606 ved division med 2773, hvilket er 948.
Antag vi ved resten ved division af 920^n og 920^m med 2773 er henholdvis r1 og r2:
920^n = 2773*a + r1
920^m = 2773*b + r2
for nogle (ligegyldige) heltal a, b.
Så kan vi finde resten ved division af 920^(n+m) med 2773 idet
920^(n+m) =
920^n * 920^m =
(2773*a+r1)*(2773*b+r2) =
(2773²)ab + (2773)a*r2 + (2773)b*r1 + r1*r2 (*)
tydeligvis har resten r1*r2 ved division med 2773 hvis r1*r2 < 2773; hvis r1*r2 > 2773 er resten r1*r2 minus et multipla af 2773.
Ved at benytte denne fremgangsmåde kan opstilles en tabel over resterne ved division af potenser af 920 med 2773:
n | rest
--------
1 | 920
2 | 635
3 | 1870
4 | 1140
5 | 606
6 | 147
:
og vi behøver ikke forstætte. For da 920^17 = 920^6 * 920^6 * 920^5 har 920^17 ifølge (*) samme rest som 147*147*606 ved division med 2773, hvilket er 948.
Skriv et svar til: Modulus beregning
Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk?
Klik her for at oprette en bruger.