Autor Beitrag
annemaria 1404
Hält's aus hier
Beiträge: 7



BeitragVerfasst: Di 30.10.12 20:57 
Hallo,

ich verzweifle gerade an einer Aufgabe...
Ich soll mit Eclips eine Funktion Programmieren, die testet, ob die Zahl a quadratischer Rest der Restklasse m ist.

Kann mir diesbezüglich jemand helfen?
platzwart
ontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic starofftopic star
Beiträge: 1054
Erhaltene Danke: 78

Win 7, Ubuntu 9.10
Delphi 2007 Pro, C++, Qt
BeitragVerfasst: Di 30.10.12 22:02 
Wo genau ist das Problem. Und was bedeutet "Rest der Restklasse m"?

_________________
Wissenschaft schafft Wissenschaft, denn Wissenschaft ist Wissenschaft, die mit Wissen und Schaffen Wissen schafft. (myself)
annemaria 1404 Threadstarter
Hält's aus hier
Beiträge: 7



BeitragVerfasst: Mi 31.10.12 12:53 
user profile iconplatzwart hat folgendes geschrieben Zum zitierten Posting springen:
Wo genau ist das Problem. Und was bedeutet "Rest der Restklasse m"?


Das genau Problem besteht darin das ich die Restklassen mit Zettel und Stift bestimmen kann aber die Umsetzung in ein Programm bekomme ich nicht hin. Zum Mathematischen Hintergrund habe ich mal das Skript angehangen in dem die Aufgabe drin steht und alles erklärt ist (Seite 18 - 23).

Wie schon geschrieben verstehe ich den Hintergrund und kann es auch berechnen aber leider nicht auf Eclips übertragen.
Einloggen, um Attachments anzusehen!
Gammatester
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 328
Erhaltene Danke: 101



BeitragVerfasst: Mi 31.10.12 16:46 
Ich weiß zwar nicht was Eclips ist und was Du genau nicht übertragen, aber vielleicht helfen Dir die Pascal-Routinen aus meinem MPArith 1.23.24 weiter (die neue Version von vorgestern hat leicht geänderte Unitstruktur: modulare Arithmetik, GGT/KGV, Jacobi/Kronecker sind jetzt in in der neuen mp_modul).

Es sind dort sowohl Integer- als auch Langzahl-Funktionon zur Berechnung des Jacobi-Symbols vorhanden:
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
function  jacobi32(a,b: longint): integer;
  {-Compute the Jacobi/Legendre symbol (a|b), b: odd and > 2}

function  kronecker32(a,b: longint): integer;
  {-Compute the Kronecker symbol (a|b)}

function  mp_jacobi(const a,n: mp_int): integer;
  {-Compute the Jacobi/Legendre symbol (a|n), n: odd and > 2}

function  mp_jacobi_lm(a: longint; const n: mp_int): longint;
  {-Compute the Jacobi/Legendre symbol (a|n), n: odd and > 2}

function  mp_jacobi_ml(const a: mp_int; n: longint): longint;
  {-Compute the Jacobi/Legendre symbol (a|n), n: odd and > 2}

function  mp_kronecker(const a,n: mp_int): integer;
  {-Compute the Kronecker symbol (a|n)}

Auch viele Funktionen für modulare Qudratwurzeln (für Deine Seiten 21-23) sind in der Unit mp_numth implementiert.

Vielleicht hilfts weiter!
Gruß Gammatester
Mathematiker
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Quizmaster
Beiträge: 2611
Erhaltene Danke: 1400

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Fr 02.11.12 18:54 
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.
ausblenden 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<3or (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 = 3or (m8 = 5then res := -res;
       end;
       if x = 1 then begin jac:=res; exit end;
       temp:= x;
       x := y;
       y := temp;
       if (x mod 4 = 3and (y mod 4 = 3then 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
annemaria 1404 Threadstarter
Hält's aus hier
Beiträge: 7



BeitragVerfasst: Mo 05.11.12 14:23 
vielen Dank für eure Zahlreiche Hilfe
Das hat mir sehr geholfen!