Lösung - Restklassen 04
Modulares Potenzieren
54^16 mod 55 =
- 54^16 mod 55 = -1^16 mod 55 = 1
2^269 mod 19 =
- 2^269 mod 19 = 2^256 mod 19 * 2^13 mod 19
- 2^8 = 256, 256 mod 19 = 9
daher
- 2^256 mod 19 = 9^32 mod 19 = 5^16 mod 19 = 6^8 mod 19 = -2^4 mod 19 = 16 mod 19
- 2^13 mod 19 = 2^8 mod 19 * 2^5 mod 19 = 9 * 13 mod 19 = 3 mod 19
- (16 * 3) mod 19 = 48 mod 19 = 10
oder mittels Algorithmus (Square and Multiply)
26910 = 1000011012
x = 1 mod 19 1
1 x = 2*1 mod 19 2
0 x = 2^2 mod 19 4
0 x = 4^2 mod 19 16 (-3)
0 x = 16^2 mod 19 9 (auch -3^2 mod 19 = 9)
0 x = 9^2 mod 19 5
1 x = 2*5^2 mod 19 12 (-7)
1 x = 2*-7^2 mod 19 3
0 x = 3^2 mod 19 9
1 x = 2*9^2 mod 19 10
Lösung = 10
3^333 mod 15 =
- 3^333 mod 15 = 3^256 mod 15 * 3^77 mod 15 = 3^256 mod 15 * 3^64 mod 15 * 3^8 mod 15 * 3^5 mod 15
- 3^4 = 81, 81 mod 15 = 6
daher
- 3^256 mod 15 = 6^64 mod 15 = 6^32 mod 15 = ... = 6 mod 15
- 3^64 mod 15 = 6^16 mod 15 = 6 mod 15
- 3^8 mod 15 = 6^2 mod 15 = 6 mod 15
- 3^5 mod 15 = 6 mod 15 * 3 mod 15 = 3 mod 15
- (6 * 6 * 6 * 3) mod 15 = 36 mod 15 * 18 mod 15 = 18 mod 15 = 3
Kontrolle mit DERIVE:

[ Schliessen ]