361 lines
6.6 KiB
Plaintext
361 lines
6.6 KiB
Plaintext
!
|
|
! Abgabe Gruppe:
|
|
! Jan Sinschek
|
|
! Benjamin Otto
|
|
! Anselm Foehr
|
|
!
|
|
! Programm:
|
|
! Autor: Anselm Foehr
|
|
! Beschreibung:
|
|
! Das Programm berechnet eine Primfaktorzerlegung nach dem einfachen
|
|
! Pollard-Rho-Verfahren.
|
|
! Gerechnet wird auf dem Datentyp BigInt, dieser kann 32 Ziffern lang
|
|
! werden.
|
|
!
|
|
! Benutzung:
|
|
! java Triangle/Compiler prime.tri
|
|
! java TAM/Interpreter obj.tam
|
|
! < Eingabe der zu faktorisierenden Zahl
|
|
! > Ausgabe des ersten Primfaktors
|
|
!
|
|
! WARNUNG: Extrem langsam fuer groessere Zahlen!
|
|
!
|
|
let
|
|
const MAXLENGTH ~ 32;
|
|
|
|
! big (unsigned) integer
|
|
type BigInt ~ record
|
|
digit : array 32 of Integer,
|
|
length : Integer
|
|
end;
|
|
|
|
! print a bigint to stdout
|
|
proc putbigint(x : BigInt) ~
|
|
let
|
|
var i : Integer
|
|
in begin
|
|
i := x.length - 1;
|
|
while i >= 0 do begin
|
|
putint(x.digit[i]);
|
|
i := i - 1;
|
|
end
|
|
end;
|
|
|
|
! return the absolute value of Integer x
|
|
func abs(x : Integer) : Integer ~
|
|
if x < 0 then 0-x
|
|
else x;
|
|
|
|
! create a BigInt from an Integer
|
|
proc int2bigint(i : Integer, var result : BigInt) ~
|
|
let
|
|
var tmp : Integer;
|
|
var j : Integer
|
|
in begin
|
|
j := 0;
|
|
tmp := abs(i);
|
|
result.length := 1;
|
|
|
|
if i = 0 then
|
|
result.digit[0] := 0
|
|
else;
|
|
|
|
while tmp > 0 do begin
|
|
result.digit[j] := tmp // 10;
|
|
tmp := tmp / 10;
|
|
j := j + 1;
|
|
end;
|
|
result.length := j;
|
|
end;
|
|
|
|
! result = x == 1
|
|
func beq1(x : BigInt) : Boolean ~
|
|
(x.length = 1) /\ (x.digit[0] = 1);
|
|
|
|
! result = x > 1
|
|
func bgt1(x : BigInt) : Boolean ~
|
|
(x.length > 1) \/ (x.digit[0] > 1);
|
|
|
|
! result = x > 0
|
|
func bgt0(x : BigInt) : Boolean ~
|
|
(x.length > 1) \/ (x.digit[0] \= 0);
|
|
|
|
! result = x == y
|
|
proc beq(x : BigInt, y : BigInt, var result : Boolean) ~
|
|
let
|
|
var i : Integer
|
|
in begin
|
|
if x.length \= y.length then
|
|
result := false
|
|
else begin
|
|
result := true;
|
|
i := x.length - 1;
|
|
while i >= 0 /\ result do begin
|
|
if x.digit[i] \= y.digit[i] then begin
|
|
result := false;
|
|
end else ;
|
|
i := i - 1;
|
|
end
|
|
end
|
|
end;
|
|
|
|
! result = x > y
|
|
proc bgt(x : BigInt, y : BigInt, var result : Boolean) ~
|
|
let
|
|
var i : Integer;
|
|
var check : Boolean
|
|
in begin
|
|
i := x.length - 1;
|
|
result := false;
|
|
|
|
if x.length > y.length then
|
|
result := true
|
|
else if x.length = y.length then begin
|
|
check := true;
|
|
while i >= 0 /\ check do begin
|
|
if x.digit[i] < y.digit[i] then begin
|
|
result := false;
|
|
check := false;
|
|
end else if x.digit[i] > y.digit[i] then begin
|
|
result := true;
|
|
check := false;
|
|
end else
|
|
i := i - 1;
|
|
end
|
|
end else result := false
|
|
end;
|
|
|
|
! result = x + y
|
|
proc badd(x : BigInt, y : BigInt, var result : BigInt) ~
|
|
let
|
|
var carry : Integer;
|
|
var t1: BigInt;
|
|
var t2: BigInt;
|
|
var i : Integer
|
|
in begin
|
|
carry := 0;
|
|
if x.length < y.length then begin
|
|
t2 := x;
|
|
t1 := y;
|
|
end else begin
|
|
t1 := x;
|
|
t2 := y;
|
|
end;
|
|
i := 0;
|
|
while i < t1.length do begin
|
|
result.digit[i] := (t1.digit[i] + t2.digit[i] + carry) // 10;
|
|
carry := (t1.digit[i] + t2.digit[i] + carry) / 10;
|
|
i := i + 1;
|
|
end;
|
|
if carry = 1 then begin
|
|
result.digit[i] := 1;
|
|
result.length := i + 1;
|
|
end else
|
|
result.length := i;
|
|
end;
|
|
|
|
! result = x + y * 10 ^ z
|
|
proc badd10(x : BigInt, y : BigInt, z : Integer, var result : BigInt) ~
|
|
let
|
|
var t1: BigInt;
|
|
var i : Integer
|
|
in begin
|
|
i := MAXLENGTH - 1;
|
|
t1 := y;
|
|
while (i - z) >= 0 do begin
|
|
t1.digit[i] := t1.digit[i - z];
|
|
i := i - 1;
|
|
end;
|
|
while i >= 0 do begin
|
|
t1.digit[i] := 0;
|
|
i := i - 1;
|
|
end;
|
|
t1.length := y.length + z;
|
|
badd(x, t1, var result);
|
|
end;
|
|
|
|
! result = |x - y|
|
|
proc bsub(x : BigInt, y : BigInt, var result : BigInt) ~
|
|
let
|
|
var carry : Integer;
|
|
var lastCarry : Integer;
|
|
var length: Integer;
|
|
var bool: Boolean;
|
|
var t1: BigInt;
|
|
var t2: BigInt;
|
|
var i : Integer
|
|
in begin
|
|
bgt(x, y, var bool);
|
|
if bool then begin
|
|
t1 := x;
|
|
t2 := y;
|
|
end else begin
|
|
t2 := x;
|
|
t1 := y;
|
|
end;
|
|
|
|
carry := 0;
|
|
if t1.length > t2.length then
|
|
length := t1.length
|
|
else
|
|
length := t2.length;
|
|
|
|
i := 0;
|
|
while i < length do begin
|
|
lastCarry := carry;
|
|
if t1.digit[i] < (t2.digit[i] + carry) then
|
|
carry := 1
|
|
else
|
|
carry := 0;
|
|
result.digit[i] := (10 * carry + t1.digit[i])
|
|
- (t2.digit[i] + lastCarry);
|
|
i := i + 1;
|
|
end;
|
|
while result.digit[i - 1] = 0 do
|
|
i := i - 1;
|
|
result.length := i;
|
|
end;
|
|
|
|
|
|
! result = x * (int)y
|
|
proc bimul(x : BigInt, y : Integer, var result : BigInt) ~
|
|
let
|
|
var tmp: BigInt;
|
|
var i : Integer
|
|
in begin
|
|
i := y;
|
|
result.length := 1;
|
|
result.digit[0] := 0;
|
|
while i > 0 do begin
|
|
badd(result, x, var tmp);
|
|
result := tmp;
|
|
i := i - 1;
|
|
end
|
|
end;
|
|
|
|
! result = x * y
|
|
proc bmul(x : BigInt, y : BigInt, var result : BigInt) ~
|
|
let
|
|
var tmp: BigInt;
|
|
var tmp2: BigInt;
|
|
var i : Integer
|
|
in begin
|
|
i := 0;
|
|
result.digit[0] := 0;
|
|
result.length := 1;
|
|
while i < y.length do begin
|
|
bimul(x, y.digit[i], var tmp);
|
|
badd10(x, tmp, i, var result);
|
|
i := i + 1;
|
|
end
|
|
end;
|
|
|
|
|
|
! result = x % y
|
|
proc bmod(x : BigInt, y : BigInt, var result : BigInt) ~
|
|
let
|
|
var tmp : BigInt;
|
|
var tmp2 : BigInt;
|
|
var bool : Boolean
|
|
in begin
|
|
result := x;
|
|
bgt(result, y, var bool);
|
|
while bool do begin
|
|
if result.length > (y.length + 1) then begin
|
|
bimul(y, 10, var tmp);
|
|
bsub(result, tmp, var tmp2);
|
|
result := tmp2;
|
|
end else begin
|
|
bsub(result, y, var tmp);
|
|
result := tmp;
|
|
end;
|
|
bgt(result, y, var bool);
|
|
end
|
|
end;
|
|
|
|
! result = gcd(x, y)
|
|
proc bgcd(x : BigInt, y : BigInt, var result : BigInt) ~
|
|
let
|
|
var bool : Boolean;
|
|
var a : BigInt;
|
|
var b : BigInt;
|
|
var tmp : BigInt
|
|
in begin
|
|
a := x; b := y;
|
|
beq(x, y, var bool);
|
|
while \ bool do begin
|
|
bgt(a, b, var bool);
|
|
if bool then begin
|
|
bsub(a, b, var tmp);
|
|
a := tmp;
|
|
end else begin
|
|
bsub(b, a, var tmp);
|
|
b := tmp;
|
|
end;
|
|
beq(a, b, var bool);
|
|
end;
|
|
result := a;
|
|
end;
|
|
|
|
! ireduzibles polynom fuer pollard-rho
|
|
proc f(x : BigInt, a : BigInt, n : BigInt, var result : BigInt) ~
|
|
let
|
|
var tmp : BigInt
|
|
in begin
|
|
bmul(x, x, var result);
|
|
badd(result, a, var tmp);
|
|
bmod(tmp, n, var result);
|
|
end;
|
|
|
|
! pollardrho verfahren
|
|
proc pollardrho(n : BigInt) ~
|
|
let
|
|
var x : BigInt;
|
|
var y : BigInt;
|
|
var d : BigInt;
|
|
var a : BigInt;
|
|
var tmp : BigInt;
|
|
var bool : Boolean;
|
|
var run : Boolean
|
|
in begin
|
|
int2bigint(1, var a);
|
|
int2bigint(2, var x);
|
|
int2bigint(2, var y);
|
|
int2bigint(1, var d);
|
|
run := true;
|
|
while beq1(d) /\ run do begin
|
|
f(x, a, n, var tmp);
|
|
x := tmp;
|
|
f(y, a, n, var tmp);
|
|
y := tmp;
|
|
f(y, a, n, var tmp);
|
|
y := tmp;
|
|
|
|
bsub(x, y, var tmp);
|
|
bgcd(tmp, n, var d);
|
|
|
|
put('.');
|
|
|
|
bgt(n, d, var bool);
|
|
if bgt1(d) /\ bool then begin
|
|
putbigint(d);
|
|
run := false
|
|
end else ;
|
|
beq(d, n, var bool);
|
|
if bool then begin
|
|
put('f');
|
|
run := false
|
|
end else ;
|
|
end
|
|
end;
|
|
|
|
|
|
var n : Integer;
|
|
var b1: BigInt
|
|
in begin
|
|
put('f');put('a');put('c');put('t');put('o');put('r');put(':');
|
|
getint(var n);
|
|
int2bigint(n,var b1);
|
|
pollardrho(b1);
|
|
end
|