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:

Potenzieren


[ Schliessen ]