berechnung multiplikatives inverses

[andreas2505]

hallo,

ich bräuchte einen Algorithmus um aus zwei BigInteger-Werten und in einer Gruppe mit einer Primzahl p ein multiplikatives Inverses zu berechnen,
also z.B.

5x=1 in F13 (also F13 ist die Gruppe, also dann mod 13 rechnen) wäre ja 8
oder
14x =246 in F13 wäre ja 1

da gibts doch bestimmt schon was vorgefertigtes oder?

 

[Marco13]

Mehr oder weniger... AFAIR geht das mit dem Erweiterter euklidischer Algorithmus ? Wikipedia ... ist aber schon eine Weile her...

 

[andreas2505]

ja aber das ist nicht in einem ring, oder?

gibt es vielleicht auch schon einen java code dafür?

 

[Marcinek]

Der erweiterte Euklidische Algo berechnet das Inverse in einem Ring. Wo sonst wäre es interessant ein Inverses zu berechnen? ;D

 

[andreas2505]

aber ich finde überall nur was mit zwei variablen, es müssen aber 3 sein, weil ich ja nicht das inverse zu 1 berechnen kann.

z.B. muss ich 1/5 in F13 oder 246/14 in F13 berechnen!

Hat denn nicht mal wer nen alrorithmus am besten in java code (brauche es dringend, sonst kann ich nicht weitermachen)

 

[andreas2505]

ok, das Problem hat sich erledigt. Ich habe statt die Brüche zu dividieren einfach mit dem modInverse multipliziert. dachte nur am Anfang dass das nicht funktioniert, aber klappt!