Krypteringsmatematik

Påståendet $17 = 6*4 + 1$ ser lite suspekt ut...

Skaft skrev:

Påståendet $17 = 6*4 + 1$ ser lite suspekt ut...

Oj!

$40=17*2+6$
$17=6*2+5$
$6=5*1+1$

Således

$1=6-5*1$
$= 6-5*(17-6*2)$
$= -5*17+ 17*6$

eller?

$\Rightarrow 17*6 \mod_{55} = 47 \Rightarrow d = ?$

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:

$1 = 40a + 17b$

För om man har det, då gäller också att

$17b = 1 - 40a$

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 $17d \equiv 1 (\text{mod } 40)$, och $d=b$.

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:

$1 = 40a + 17b$

För om man har det, då gäller också att

$17b = 1 - 40a$

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 $17d \equiv 1 (\text{mod } 40)$, och $d=b$.

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:

$6 - 5\cdot 1 = 6 - 5 = 6 - (17-6\cdot 2) = -17 + 3\cdot 6$.

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:

$6 - 5\cdot 1 = 6 - 5 = 6 - (17-6\cdot 2) = -17 + 3\cdot 6$.

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:

$40 = 17*2+6$
=> 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)