Diskret matematik

i) så hvad ?

ii) ja da 6 og 29 er indbyrdes primiske. Brug Euklids udvidede algoritme eller  prøv dig frem. Med kun 27 elementer at teste er det overkommeligt

hov, mangler noget tekst.. så 3^61 er ækvivalent med x

Du kan udregne 3² mod 29  3³ mod 29 = (3² mod 29)*3 mod 29, 3⁴mod 29 = ( 3³ mod 29)*3 mod 29 eller mere generelt aⁱ⁺¹ mod n = (aⁱ mod n)*a mod n. Med så små tal er det nemt at gennemføre i et regneark. Der findes også en meget effektiv algoritme til at beregne det. Hvis du kender den, så brug den i stedet.

Har du nogle gode bud på iii og iv.. Har misset nogle sider og forelæsninger, som det sikkert nok fremgår

iii) Det forekommer mig noget meningsløst. Som jeg læser det er H de tal som kan skrives som 6^m hvor m er et lige tal. Dem findes der indlysende uendelige mange af

iv) Prøv dig frem i et regneark beregn x⁴ mod 29 for alle kandidater. Dem der giver resultatet 1 er muligheder. der er 2 hvor du vil få 1 men som ikke dur. Det er 1 og 18. De har ordenen 1 og 2

Hvad hedder algoritmen til besvarelse af opgave i. Kan umiddelbart ikke kende den ved at se på opgaven, men hvis du har et navn, kan jeg hurtigt lige læse op på fremgangsmåden.

På forhånd tak

Med forbehold: russisk bondealgoritme

har jeg umiddelbart hverken hørt eller læst om, men tak for svaret.

Her er en kort beskrivelse i psudoprogrameringssprog. Der skal findes x^e mod n

trin 0  indlæs x, e og n. y:=1        y vil til slut indeholde resultatet

trin 1 c: = e mod 2                                     finder mindst betydende ciffer i e i 2 tals systemet

trin 2   e::=   heltal(e/2(                              fjerner sidste ciffer i totals systemet

trin 3   Hvis  c= 1           y:= (y*x) mod n

trin 4: x: = x² mod n

Hvis e = o stop y = e^x mod n ellers gå til trin 1

Kan godt forstå du synes det virker meningsløst nu i iii), har nemlig skrevet forkert.

Der skulle stå: Betragt H = {6^m (invers element)|m hørende til Z}. Med begrundelse ønskes antal ele-

menter i H angivet