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
probleem met vergelijking
Moderators: ArcherBarry, Fuzzwood
-
Anonymous
- Artikelen: 0
-
the bug
- Artikelen: 0
- Berichten: 82
- Lid geworden op: di 09 dec 2003, 13:44
Re: probleem met vergelijking
mod zegt me niet veel ... 
zou het x = (1/a)*
kunnen zijn
zou het x = (1/a)*
kunnen zijn
-
Draco
- Artikelen: 0
- Berichten: 67
- Lid geworden op: di 17 feb 2004, 21:27
Re: probleem met vergelijking
Juij! Eindelijk eentje die ik weet en The Bug niet! *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
).
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:
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
*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
).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)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
-
Anonymous
- Artikelen: 0
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?
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?
-
Draco
- Artikelen: 0
- Berichten: 67
- Lid geworden op: di 17 feb 2004, 21:27
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 )
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.
'k Ben toch al lang blij dat je mijn uitleg gesnapt hebt. Het was lang geleden dat ik me nuttig voelde
(just kidding )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.
-
the bug
- Artikelen: 0
- Berichten: 82
- Lid geworden op: di 09 dec 2003, 13:44
Re: probleem met vergelijking
Draco schreef:Juij! Eindelijk eentje die ik weet en The Bug niet!
...
Greetz
Draco
ik voel me enorm gevleid
Draco-
Draco
- Artikelen: 0
- Berichten: 67
- Lid geworden op: di 17 feb 2004, 21:27
Re: probleem met vergelijking
Sorry, ik kon het echt niet laten
Greetz
Draco
Greetz
Draco
