Matematik

Euklids udvidede algoritme

30. december 2011 af lga1993 (Slettet) - Niveau: A-niveau

Hej forumlæsere.

Jeg er så småt begyndt på forarbejdet til min SRP og jeg har valgt at skrive om RSA kryptering. i forbindelse med dette emne skal jeg kunne bestemme positive hele tal der er løsning på følgende:

1 = 17*u - 60*v

I min bog står der at man skal bruge Euklids udvidede algoritme, men den uddyber ikke nok til at jeg kan forstå det.

Er der nogen der ved hvordan jeg bestemmer et sæt u og v der løser ligningen? Bemærk at u og v skal være positive hele tal ellers er det ubrugeligt ift. dekryptering.

Brugbart svar (1)

Svar #1
30. december 2011 af Andersen11 (Slettet)

Du kan læse mere om Euklids udvidede algoritme her http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

Svar #2
02. januar 2012 af lga1993 (Slettet)

Mange tak. Jeg har nu læst det hele og kan ikke se en algoritme til at bestemme positive hele tal som løsning, men har lært en algoritme som kan bestemme løsninger med alle mulige fortegn :p - Den løser desværre ikke mit problem.

Brugbart svar (0)

Svar #3
05. maj 2014 af SørenFr (Slettet)

Jeg tilføjer mit svar: Betragt $x \equiv -4 \ \text{mod} (17), \ \ x \equiv 3 \ \text{mod} (23)$ .

det ses klart at løsningerne til denne er $x=-4+17t, \ x=3+23s$ . vi substitere den første løsningen ind i den anden ligning og får

$-4+17t \equiv3 \ \text{mod} (23) \Rightarrow 17t \equiv 7 \ \text{mod} (23)$ .

dette er ækvivalent med ligningen

$17t \equiv 7 \ \text{mod} (23) \Rightarrow 40t \equiv 30 \ \text{mod} (23) \Rightarrow 4t=3 \ \text{mod} (23)$

det ses fra det sidste udtryk at t=18 , men denne løsning passer ikke med den første løsning, hvilket den meget gerne burde

Brugbart svar (0)

Svar #4
05. maj 2014 af Andersen11 (Slettet)

Det var da bedre, om du havde tilføjet dit svar i den tråd, du selv har kørende lige nu

https://www.studieportalen.dk/forums/thread.aspx?id=1475872

Prøv at holde diskussionen i én tråd istedet for at sprede det over flere tråde.

Brugbart svar (0)

Svar #5
05. maj 2014 af SørenFr (Slettet)

ups det var en fejl, ved ikke hvordan det skete

Skriv et svar til: Euklids udvidede algoritme

Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk? Klik her for at oprette en bruger.