Springen naar inhoud

Regel machtsverheffen modulair rekenen



  • Log in om te kunnen reageren

#1

Beroemdheid

    Beroemdheid


  • >25 berichten
  • 56 berichten
  • Ervaren gebruiker

Geplaatst op 18 oktober 2012 - 16:31

Hallo :)

Ik kwam laatst op een bepaalde regel voor machtsverheffen bij modulair rekenen. Ik kon echter nergens vinden of deze regel ook daadwerkelijk klopt en daarom vraag ik het maar aan jullie.

LaTeX

(Excuses als de LaTeX mooier kon, daar heb ik geen ervaring mee)

Op de Wiki van modulair rekenen kwam ik wel iets tegen, maar dat vond ik niet erg helder en ik wist niet zeker of dat hierover ging. Zelf zou ik ook niet zo snel kunnen bedenken waarom dit zou zijn. Ik weet dat het geen bewijs is, maar ik kon geen voorbeelden vinden waarvoor het niet geldt.

Alvast bedankt,

Beroemdheid

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Westy

    Westy


  • >250 berichten
  • 578 berichten
  • Ervaren gebruiker

Geplaatst op 18 oktober 2012 - 18:22

Ik weet niet of het je wat vooruit helpt, maar op deze wiki-pagina staat het volgende:

given two integers a and b, the following two equations are equivalent:

Geplaatste afbeelding

Geplaatste afbeelding



helaas zonder referentie of bewijs. Ik denk dat hetgeen jij schrijft misschien wel kan herleid worden naar wat hierboven staat, maar dat is natuurlijk evenmin een bewijs...
---WAF!---

#3

*_gast_eezacque_*

  • Gast

Geplaatst op 18 oktober 2012 - 21:30

Het bewijs volgt rechtstreeks uit de definitie van mod, als je drie keer hard vloekt dan staat het op papier...

#4

Beroemdheid

    Beroemdheid


  • >25 berichten
  • 56 berichten
  • Ervaren gebruiker

Geplaatst op 20 oktober 2012 - 16:37

Bedankt allebei, maar ik zie het nog steeds niet. Voor B=1 is het logisch, maar daarna weet ik het niet. Kan iemand een richting geven waarin ik moet denken?

#5

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 20 oktober 2012 - 16:54

Pas herhaaldelijk toe dat er geldt: xy mod n = ((x mod n)(y mod n)) mod n. Dus bijvoorbeeld: x² mod n = ((x mod n)(x mod n)) mod n = ((x mod n)²) mod n
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.

#6

Beroemdheid

    Beroemdheid


  • >25 berichten
  • 56 berichten
  • Ervaren gebruiker

Geplaatst op 21 oktober 2012 - 13:47

Bedankt, ik geloof dat ik het nu snap :)

#7

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 21 oktober 2012 - 14:03

Okee :). Moet nu nog verantwoord worden dat xy mod n = (x mod n)(y mod) mod n. Zou je dat lukken, denk je?
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.

#8

Beroemdheid

    Beroemdheid


  • >25 berichten
  • 56 berichten
  • Ervaren gebruiker

Geplaatst op 21 oktober 2012 - 16:39

Dit is wat ik heb bedacht:
a = x mod N
b = y mod N
Dus:
a+c×N = x
b+d×N = y
c en d zijn dan natuurlijke getallen, maar die doen er niet toe.
x×y = (a+c×N)(b+d×N)
x×y = ab + adN + bcN + cdN^2
x×y = ab + N(ad + bc +cdN)
x×y mod N = ab + N(ad + bc +cdN) mod N
Omdat N(ad + bc +cdN) dus wordt vermenigvuldigd met N, is daarvan de rest 0:
x×y mod N = ab mod N
a en b staan bovenaan gedefinieerd:
x×y mod N = (x mod N)(y mod N) mod N

Klopt dit?

Veranderd door Beroemdheid, 21 oktober 2012 - 16:43


#9

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 21 oktober 2012 - 16:41

Klopt helemaal :).
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.

#10

Beroemdheid

    Beroemdheid


  • >25 berichten
  • 56 berichten
  • Ervaren gebruiker

Geplaatst op 21 oktober 2012 - 16:52

Oké, heel erg bedankt :)






Also tagged with one or more of these keywords: wiskunde

0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures