Springen naar inhoud

probleem met vergelijking


  • Log in om te kunnen reageren

#1


  • Gast

Geplaatst op 12 april 2004 - 13:12

ik wil de factor x berekenen in de volgende vergelijking


a*x=b mod N

a, b en N zijn bekend

hoe doe ik dit

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

#2

the bug

    the bug


  • >25 berichten
  • 82 berichten
  • Ervaren gebruiker

Geplaatst op 12 april 2004 - 14:14

mod zegt me niet veel ... :?:

zou het x = (1/a)*[b mod N]
kunnen zijn :shock:

#3

Draco

    Draco


  • >25 berichten
  • 67 berichten
  • Ervaren gebruiker

Geplaatst op 13 april 2004 - 10:33

Juij! Eindelijk eentje die ik weet en The Bug niet! :shock: *apetrots enal*

Ok, het is wel niet zo makkelijk om uit te leggen, maar eens je het door hebt is het niet zo moeilijk meer.

Eerst ga ik trachten uit te leggen hoe je gewoon een mod berekent.
Neem even het voorbeeld 13 = 19 (mod 3).
Wat doe je nu, je deelt zowel linker (13) als rechterlid (19) door de mod (3) en neemt daar de rest van. voor beide getallen is de rest 1, en klopt de gelijkheid (normaal is het gelijkaansteken bij zoiets drie streepjes ipv twee, mar die staat niet op mijn klavier :wink:).
Nog iets, als je met een negatief getal zit, moet je een aantal keer de mod bij uw negatief getal optellen, tot je aan een positief getal komt. vb: -8 (mod 5): -8+5=-3; -3+5=2 => -8 (mod 5) = 2.

Dit gezegd zijnde gaan we nu de inverse even van een mod uitleggen, die heb je namelijk ook nodig.
laten we even de inversen zoeken voor de mod 7. Wat is nu juist de bedoeling. Je schrijft alle getallen van 2 tot 6 naast elkaar op een blad papier. Dan probeer je voor elk van deze getallen een getal te zoeken dat je dan vermenigvuldigd met het getal waar je de inverse van zoekt. Als je dan voor het product de mod neemt (hier mod 7) moet die 1 geven. Het getal waarmee je vermenigvuldigd hebt is dan de inverse. Let wel, de inverse moet steeds binnen het interval [1,N] liggen, met N de mod (hier 7) en ieder getal in dit interval mag maar 1 keer gebruikt worden.
Even het voorbeeld uitwerken:
2  3  4  5  6  
 4  5  2  3  6
----------------
 8  15 8  15 36 (mod 7)
Dus de inverse van 2 is 4, de inverse van 3 is 5, de inverse van 4 is 2, enz. En dit allemaal voor mod 7.

En dan komen we nu aan je vergelijking.
a*x=b (mod N)
De eerste stap is b (mod N) en a (mod N) uitrekenen (zie eerste uitleg). De tweede stap is de a (of a' indien deze al vereenvoudigd geweest is)overbrengen naar het rechterlid. dan krijg je in het rechterlid a^-1. Dit is de inverse van a voor mod N dat je dan moet zoeken (zie tweede uitleg). En dan bekom je voor x een getal voor mod N.

Mss eens een vbtje uitwerken:
geg: 27*x+3=0 (mod 11)
gevr: x
opl: 1) 27 (mod 11) = 5
2) 5*x = -3 (mod 11)
3) -3 (mod 11) = 8
4) 5*x = 8 (mod 11)
5) x = 8*5^(-1) (mod 11)
6) de inverse van 5 (mod 11) = 9 (5*9=45; 45 (mod 11) = 1)
7) x = 8*9 (mod 11) = 72 (mod 11) = 6 (mod 11)

Ziezo, ik hoop dat het een beetje duidelijk is. Anders is mijn eerste zinnetje wel een beetje een afgang geweest :?:. Indien er nog vragen zijn, moet je ze maar stellen.

Greetz
Draco

#4


  • Gast

Geplaatst op 13 april 2004 - 14:50

en als ik nou het volgende neem

7*x=1 mod 192

x=7-Ļ*1 mod 192

dan moet ik dus de inverse van 7 voor modulo 192 zoeken...

dus 7 keer iets moet of 193 geven, of 192*2+1, 192*3+1.....

in dit voorbeeld ben je dan niet lang bezig maar met grotere getallen kan het wel even tijd kosten. is er niet een andere manier om er achter te komen dan eindeloos proberen?

#5

Draco

    Draco


  • >25 berichten
  • 67 berichten
  • Ervaren gebruiker

Geplaatst op 15 april 2004 - 10:25

ben je inderdaad wel een hele tijd zoet mee, maar je kan het makkelijk met een wiskundige software vinden zoals maple ofzo. Om het zo te zoeken lijkt het me inderdaad nogal moeilijk...
'k Ben toch al lang blij dat je mijn uitleg gesnapt hebt. Het was lang geleden dat ik me nuttig voelde :?: (just kidding :shock:)

Greetz
Draco

edit >> heb 't eens uitgerekend met maple en de inverse is 55. Eigenlijk valt het nog mee om het zonder maple te berekenen, aangezien je maar tot 2*192+1 moet zoeken om dit uit te komen.

#6

the bug

    the bug


  • >25 berichten
  • 82 berichten
  • Ervaren gebruiker

Geplaatst op 17 april 2004 - 17:08

Juij! Eindelijk eentje die ik weet en The Bug niet! :shock: *apetrots enal*
...
Greetz
Draco


ik voel me enorm gevleid Geplaatste afbeelding Draco

#7

Draco

    Draco


  • >25 berichten
  • 67 berichten
  • Ervaren gebruiker

Geplaatst op 18 april 2004 - 12:49

Sorry, ik kon het echt niet laten :shock:

Greetz
Draco





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures