0 Daumen
784 Aufrufe


wie Ziehe ich die wurzel aus 37 mod 77 mit dem  Chinesischen Resetesatz?

also wie finde ich ein b für das gilt b2 mod 77 = 37 mod 77?


Also irgendwie zerlegt man ja zunächst 77 zu 7*11 aber ich bewege mich im kreis und weiß nicht wie ich irgendeine gleichung aufstellen kann in der form b mod 77= xyz mod 77


LG

Avatar von

1 Antwort

+1 Daumen

Der chinesische Restsatz liefert den Isomorphismus

f : Z/77ZZ/7Z×Z/11Z,x+(77)(x+(7),x+(11)) f: \mathbb{Z}/77\mathbb{Z} \to \mathbb{Z}/7\mathbb{Z} \times \mathbb{Z}/11\mathbb{Z}, \\x + (77) \mapsto (x + (7), x + (11))

Wenn 37=b2 37 = b^2 dann gilt auch f(37)=f(b2)=f(b)2 f (37)=f ( b^2) = f(b)^2 .

Es gilt f(37)=(2,4) f(37)=(2,4) , such also mal ein (x,y)Z/7Z×Z/11Z, (x,y)\in\mathbb{Z}/7\mathbb{Z} \times \mathbb{Z}/11\mathbb{Z}, mit (x,y)2=(x2,y2)=(2,4) (x,y)^2 = (x^2,y^2) =(2,4).

Berechne dann b=f1((x,y)) b = f^{-1}((x,y)) . Das entspricht dem Lösen des Systems:

bxmod  (7)bymod  (11) b \equiv x \mod (7)\\ b \equiv y \mod (11)

Falls du Fragen hast, gerne melden.

Avatar von 6,0 k

wäre das dann einfach

3b mod73 \equiv b \ mod 7

2b mod112 \equiv b \ mod 11

==>b79mod77==> b \equiv 79 mod 77

ist das einfach das ergebnis?

ich muss sagen ich verstehe dadruch immer noch nicht wo genau wie die wurzel gezogen wird

x=3, y=2 sind mögliche Werte. Beim b hast du dich verrechnet 79 = 2 mod 7 und nicht =3.

Rauskommen sollte 24 und es gilt 24237mod  (77) 24^2 \equiv 37 \mod (77)

Die Idee ist hier einfach das Wurzelziehen in kleinere Ringe zu verlagern (was dann evtl schneller geht)

Ein anderes Problem?

Stell deine Frage