Krypteringsmatematik
jag följer KTH's exempel
Om vi börjar med att hitta ?
därför
Vi löser konguerensen ???? med Euklides algoritm:
eller?
Således
eller?
?
Påståendet ser lite suspekt ut...
Skaft skrev:Påståendet ser lite suspekt ut...
Oj!
Således
eller?
Najj. Målet med att använda Euklides algoritm här är att skriva om 1 som en multipel av 40 plus en multipel av 17:
För om man har det, då gäller också att
vilket säger att talet 17b ligger ett helt antal steg om 40 ifrån talet 1. Därför är detta en lösning till din kongruens , och .
Skaft skrev:Najj. Målet med att använda Euklides algoritm här är att skriva om 1 som en multipel av 40 plus en multipel av 17:
För om man har det, då gäller också att
vilket säger att talet 17b ligger ett helt antal steg om 40 ifrån talet 1. Därför är detta en lösning till din kongruens , och .
Finns det ett smartare sätt och lösa det där på, än att göra Euklides fram-och-baklänges?
Inte som jag känner till, men det är väl en bra metod?
Skaft skrev:Inte som jag känner till, men det är väl en bra metod?
Men tänker om man ska fortsätta med det jag gjorde, vad gör jag för fel i mina uträkningar där?
Du går från 6-5*1 till 6-5(17-6*2). Då har du alltså bytt ut ettan mot (17-6*2), men den parentesen blir ju 17-12=5, inte ett. Det är alltså femman du ska byta mot detta, inte ettan:
.
Genom att hoppa tillbaka i algoritmen ytterligare ett hack kan du hitta ett uttryck för 6 och byta ut den på samma sätt.
Skaft skrev:Du går från 6-5*1 till 6-5(17-6*2). Då har du alltså bytt ut ettan mot (17-6*2), men den parentesen blir ju 17-12=5, inte ett. Det är alltså femman du ska byta mot detta, inte ettan:
.
Genom att hoppa tillbaka i algoritmen ytterligare ett hack kan du hitta ett uttryck för 6 och byta ut den på samma sätt.
Vänta.. vi gör om det från början:
=> 17 = 6*2+5
=> 6 = 5*1+1
Baklänges.
1 = 6-5*1
= 6 - (17-6*2) (= 6-5)
= (40-17*2)-5 (= 6-5)
= 6-5
1 = 1 - korrekt.
Visst?
Du går i cirklar. Det ser bra ut fram tills
1 = 6 - (17 - 6*2)
Sen bytte du bort *ena* sexan, och lät parentesen gå tillbaka till en femma, vilket den ju var i förra steget. Ta istället bort parentesen så du kan samla termerna:
1 = 6 - 17 + 6*2 = -17 + 3*6
Nu kan du byta ut sexan:
1 = -17 + 3*(40 - 17*2)