probleem met vergelijking

Moderators: ArcherBarry, Fuzzwood

Reageer

probleem met vergelijking

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

Gebruikersavatar
Berichten: 82

Re: probleem met vergelijking

mod zegt me niet veel ... :?:

zou het x = (1/a)*

kunnen zijn :shock:

Berichten: 67

Re: probleem met vergelijking

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:

Code: Selecteer alles

 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

Re: probleem met vergelijking

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?

Berichten: 67

Re: probleem met vergelijking

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.

Gebruikersavatar
Berichten: 82

Re: probleem met vergelijking

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

...

Greetz

Draco


ik voel me enorm gevleid Afbeelding Draco

Berichten: 67

Re: probleem met vergelijking

Sorry, ik kon het echt niet laten :shock:

Greetz

Draco

Reageer