Hallo,
Gammatesters Routinen sind für große Zahlen hervorragend geeignet, Dein Problem zu lösen.
Ich vermute, dass Du "Eclipse" für Java meinst.
Solltest Du nur kleine Zahlen bearbeiten wollen, dann genügt eine einfache Routine zur Berechnung des Legendre-Symbols (allgemein Jacobi-Symbol), z.B.
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26:
| function jac(x,y:integer):integer; var m8, temp, res: integer; begin if (y<3) or (not odd(y)) then begin jac:=0; exit end; res:=1; while true do begin x:=x mod y; if x=0 then begin jac:=0; exit end; while not odd(x) do begin x:=x div 2; m8:= y mod 8; if (m8 = 3) or (m8 = 5) then res := -res; end; if x = 1 then begin jac:=res; exit end; temp:= x; x := y; y := temp; if (x mod 4 = 3) and (y mod 4 = 3) then res:=-res; end; end; |
Nach Java musst Du es aber selbst übersetzen.
Sollst Du prüfen, ob a quadratischer Rest modulo p (p prim!) ist, dann ist jac(a,p) = 1.
Schwieriger wird es, wenn modulo n zu rechnen ist und n eine zusammengesetzte Zahl ist. Dann benötigst Du eine vollständige Primfaktorzerlegung von n. In der EE gibt es genügend Beispiele dazu.
Da aber in der Aufgabe
Zitat: |
Dabei kann auf eine Primzahlüberprüfung von m verzichtet werden. |
steht, genügt wohl die einfache Legendre-Symbol-Routine.
Unter
code.google.com/p/ma...1dd973d5db4069a31c19 gibt's auch einen Java-Text für das Legendre-Symbol.
Beste Grüße
Mathematiker
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein