Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

nightmare

Trainee

  • "nightmare" is male
  • "nightmare" started this thread

Posts: 81

Date of registration: Sep 28th 2009

1

Wednesday, October 21st 2009, 3:16pm

Modulo-Rechnungen...

Wir haben ja in der Übungsstunde folgende Aufgabe berechnet:
Berechnen Sie 25^500 in Z27 berechnet als Endergebnis hatten wir 22
Könnte einer von euch nochmal erklären wie wir auf die Zwischenschritte gekommen sind bei der aufgabe vorher Z 5 kann ich das ja nachvolziehen aber nicht bei Z 27

25^500= (-2)^500=2^500=)(2)^5)^100=32^100=5^100=((5)^2)^50=(25)^50=(-2)^50=2^50=((2^5)^10)=(32)^10=5^10=((5^2)^5)=(25)^5=(-2)^5=-32=-2*27+22=22
  • Send private message

pythong

Trainee

  • "pythong" is male

Posts: 112

Date of registration: Oct 23rd 2005

Location: Ehemals Preußisches Gebiet

Occupation: Ehemals Studentenquäler. I'm finally done with school!

2

Wednesday, October 21st 2009, 3:28pm

25^500
= (-2)^500 weil nur der Rest interessiert, und 25 hat in Z27 den gleichen Rest wie -2
=2^500 weil (-2)^500 = (-1)^500 * 2 ^500 und (-1)^a mit a gerade ist 1
=((2)^5)^100 weil die 500 aufgesplittet wurde
=32^100 weil 1<<5 = 32
=5^100 weil nur der Rest interessiert
=((5)^2)^50 weil aufgesplittet
=(25)^50 weil 5^2 = (2+3)^2 =(binom) 2^2 + 2*2*3 + 3^2 = 4 + 12 + 9 =25
=(-2)^50 weil der Rest interessiert, siehe oben
=2^50 weil hier auch -1^gerade Zahl = 1
=((2^5)^10) weil aufgesplittet
=(32)^10 weil 2*2*2*2*2 = 32
=5^10 weil 32 den gleichen Rest hat wie 5 in Z27
=((5^2)^5) weil und so weiter
=(25)^5 und so weiter
=(-2)^5 und so weiter
=-32 und -1^ungerade ist -1
=-2*27+22=22 weil 22 in Z27 den gleichen rest hat wie -32 und außerdem der entsprechende Repräsentant ist
don't ask me, google it
  • Send private message