Springen naar inhoud

Modulair rekenen met exponent


  • Log in om te kunnen reageren

#1

Jan Terhuijzen

    Jan Terhuijzen


  • 0 - 25 berichten
  • 9 berichten
  • Gebruiker

Geplaatst op 01 juli 2014 - 15:00

Ik zit met een vraagstuk, ik wil vooral weten of de oplossing überhaupt op deze manier uit te reken is.

 

Als ik dit heb:

C = Me mod n

 

C = uitkomst

M = ingevuld door "gebruiker" van formule (in dit geval 119)

e = 11

n = 899

 

En ik doe:

 

C = 11911 mod 899 = 595 

 

Is van het getal C (dus 595) dan weer het getal M te vinden? Dus is deze formule om te draaien zodat je weer 119 krijgt?

Of is dit onmogelijk?

Veranderd door Jan Terhuijzen, 01 juli 2014 - 15:01


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

#2

Th.B

    Th.B


  • >250 berichten
  • 523 berichten
  • Ervaren gebruiker

Geplaatst op 02 juli 2014 - 00:54

De vraag is (in woorden):

 

Gegeven de rest van een elfde macht bij deling door 899. Welke elfde macht is het dan? Je kunt dit niet zomaar uniek vaststellen.

 

Je kunt natuurlijk bewijzen waarom. Hint:

 -welke waarden kan C aannemen?

 -welke waarden kun je aan M toekennen? 

 -wat is je conclusie? Denk aan het Dirichletprincipe (als je er niet mee bekend bent, even google gebruiken).


#3

Jan Terhuijzen

    Jan Terhuijzen


  • 0 - 25 berichten
  • 9 berichten
  • Gebruiker

Geplaatst op 02 juli 2014 - 10:18

Dus als ik het goed begrijp:

 

De formule is C = Me mod n

Ik bedoel dus wel dat e en n een vast getal zijn, dus beter gezegd is de formule:

C = M11 mod 899

 

Als daaruit bijvoorbeeld C = 119 komt, is het dus niet mogelijk om M uit te rekenen? (Je hebt dus de formule, Alleen M weet je niet)

 

Dat is dus zo, omdat een modulo gewoon de rest is bij een deling? Dat getal kan dus bij heel veel verschillende delingen uitkomen.

 

Voorbeeld:

10 mod 2 geeft 0

10 mod 5 geeft 0

 

Je weet 2 en 5, en dat er 0 uit komt, maar je weet niet het getal 10. Je kunt dan gewoon nooit erachter komen of het 10 was, of een ander getal dat toevallig gedeeld door 5 of gedeeld door 2 een rest van 0 oplevert.


#4

Th.B

    Th.B


  • >250 berichten
  • 523 berichten
  • Ervaren gebruiker

Geplaatst op 02 juli 2014 - 11:21

Ik denk dat je het snapt, maar je verwoordt het wat ongelukkig in je voorbeeld. Je zet immers verschillende getallen op de plek van de 'mod', terwijl dat niet een van je onbekenden is. Dit is een beter voorbeeld (met ook nog een exponent erbij voor het idee):

 

122 mod 2 = 0

202 mod 2 = 0

 

M.a.w. elk tweevoud geeft uitkomst nul en elk tweevoud +1 geeft uitkomst 1. Er is dus geen unieke terugkoppeling mogelijk.

 

Waar komt deze vraag eigenlijk vandaan?


#5

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 02 juli 2014 - 14:49

LaTeX
Bij elke m is er een waarde e zodat geldt:
LaTeX
Je kunt deze waarde e voor alle m's (0 t/m 898) bepalen. De waarde e-1 in dus effectief de 1. Van alle e-1's kun je de least common multiple bepalen. Dit blijkt 420 te zijn.
Stel nu dat er een waarde f is waarvoor geldt:
LaTeX
dan:
LaTeX
De waarde voor f is 191.
LaTeX

#6

Jan Terhuijzen

    Jan Terhuijzen


  • 0 - 25 berichten
  • 9 berichten
  • Gebruiker

Geplaatst op 02 juli 2014 - 15:29

Waar komt deze vraag eigenlijk vandaan?

 

Uit de cryptografie. Iemand beweerde dat het terug te draaien is, maar dat is het dus niet. De geheime data M is niet meer te achterhalen.


#7

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 03 juli 2014 - 07:19

Iemand beweerde dat het terug te draaien is, maar dat is het dus niet.

Maar dat is het wel voor elke m in [0,898]. Zie mijn post.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures