1:

While ((temp1.Number[1] Mod 2) = 0)and(FGIntCompareAbs(temp1, zero) <> eq) Do Begin                    

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:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:

unit UBrentRho;

interface

uses FGInt;  //copyright 2000, Walied Othman

  function BrentRho(var A: TFGInt; var d: integer; var Z: TFGInt): string;

implementation

uses Forms, Math, SysUtils, Windows, ufaktor;
                                             //803143374682433343421987  8,05sec
                                         //Teiler = 23894352497 * 33612267785171

//------------------------------------------------------------------------------
  function BrentRho(var A: TFGInt; var d: integer; var Z: TFGInt): string;
  var
    okay: boolean;
    s: string;
    r, i, j, k, m: integer;
    time, t: cardinal; //Zeit-Messung Unit Windows
    xx, yy, tt, tmp, temp1, temp2, factorGGT, one: TFGInt;

  label neu;

  begin
    if(Length(A.Number) = 0)then
      exit;

    Base10StringToFGInt('0', xx);
    Base10StringToFGInt('0', yy);
    Base10StringToFGInt('0', temp1);
    Base10StringToFGInt('1', temp2);
    Base10StringToFGInt('1', factorGGT);
    Base10StringToFGInt('1', one);
    Base10StringToFGInt('0', tt);
    Base10StringToFGInt('0', tmp);
    result:='';
    time:= GetTickCount;;

    TRY

      FGIntRabinMiller(A, 3, okay);
      if(okay)then begin
        FGIntToBase10String(A, s);
        result:= format('%s', [s]);
        d:=0;
      end;
      WHILE not(okay)DO BEGIN
neu:
        d:=0;
        r:=1;
        m:=1024;

        while(FGIntCompareAbs(factorGGT, one) = eq)do begin

          FGIntCopy(yy, xx);        //xx = yy
          for i:=1 to r do begin
             FGIntSquare(yy, tt);
             FGIntAdd(tt, Z, tmp);
             FGIntMod(tmp, A, yy);  //yy = (yy²+1) mod A
          end;

          k:=0;
          j:= min(m, r);

          repeat

            for i:=j downto 1 do begin
               FGIntSquare(yy, tt);
               FGIntAdd(tt, Z, tmp);
               FGIntMod(tmp, A, yy);

               FGIntSub(xx, yy, temp1);    //temp1 = xx - yy
               FGIntAbs(temp1);
               FGIntMul(temp1, temp2, tt);
               FGIntMod(tt, A, temp2);     //temp2 = (temp1*temp2) mod A
            end;

            FGIntGCD(temp2, A, factorGGT);
            d:=d + 1;
            k:=k + m;

            if(d and 7 = 0)then begin
              t:= GetTickCount;
              Application.ProcessMessages;
              Form1.lblZeit.Caption:= Format('D: %d  time: %.1f sec', [d, (t - time)/1000]);
              if(abbruch)then begin
                Form1.Memo1.Lines.Add(Format('abgebrochen bei D: %d', [d]));
                exit;
              end;
            end;

          until((k >= r) or (FGIntCompareAbs(factorGGT, one) <> eq));

          r:= r shl 1;  //r:= r + r;

        end;

        if(FGIntCompareAbs(factorGGT, one) <> eq)then begin

          FGIntToBase10String(factorGGT, s);
          FGIntDiv(A, factorGGT, A);

          if(FGIntCompareAbs(A, one) = eq)then begin
            FGIntCopy(factorGGT, A);
            FGIntAdd(Z, one, Z);      //anderes Z versuchen !!
            Base10StringToFGInt('1', temp2);
            Base10StringToFGInt('1', factorGGT);
            goto neu;
          end else
            result:= format('%s%s * ', [result, s]);

          FGIntRabinMiller(A, 3, okay);
          if(okay)then begin
            FGIntToBase10String(A, s);
            result:= format('%s%s', [result, s]);
          end else
            Base10StringToFGInt('1', factorGGT);

        end;

      END;                         // 347068499990683866034691710961
                                   // = 98296514606911 * 3530832210873551
      FGIntToBase10String(Z, s);
      Form1.lblZeit.Caption:=
        Format('D: %d    Z: %s    time: %.2f sec   fertig!',
              [d, s, (GetTickCount - time)/1000]);

    FINALLY
      FGIntDestroy(xx);
      FGIntDestroy(yy);
      FGIntDestroy(temp1);
      FGIntDestroy(temp2);
      FGIntDestroy(factorGGT);
      FGIntDestroy(one);
      FGIntDestroy(tt);
      FGIntDestroy(tmp);
    END;
  end;    //BrentRhoTFGInt
//------------------------------------------------------------------------------

end.                    

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

var ...         
..., A, Zz: TFGInt;
begin
...
Base10StringToFGInt(k, A);
Base10StringToFGInt('1', Zz);   //besser noch Zz variabel wählbar über Eingabefeld
                                //beträchtliche Unterschiede in der Laufzeit 
k:= BrentRho(A, d, Zz);
...
memo1.lines.add('Teiler = '+k);
...
end;                    

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:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:

Test of MPArith V1.20.24 (31/32 bit) [mp_calc/pfdu]  (c) W.Ehrhardt 2006-2012
To exit the test program entering an empty expressions string.

Expression to factor: 18753145125348788607553275398558954818510418200
N=18753145125348788607553275398558954818510418200
    2 2344143140668598575944159424819869352313802275
    5 93765725626743943037766376992794774092552091
   19 4935038190881260159882440894357619689081689
SLim: 1073676289
PFD1: 4935038190881260159882440894357619689081689
PRIM: 4935038190881260159882440894357619689081689 - FALSE
Word: ................
PPow:
PP-1: .........................................................................
...........................................................................
WP+1: .........................................................................
...........................................
PRho: .........................................................................
...............................................................................
...............................................................................
...............................................................................
...............................................................................
...............................................................................
...............................................................................
...............................................................................
...............................................................................
...............................................................................
...............................................................................
...............................................................................
..............................................
ECM1: ................................................................
ECM2: .........................................................................
...........
PFD1: 3925732919637436942817
PRIM: 3925732919637436942817 - TRUE
PFD1: 1257099831268459831417
PRIM: 1257099831268459831417 - TRUE
2^3 * 5^2 * 19 * 1257099831268459831417 * 3925732919637436942817
Start: 18753145125348788607553275398558954818510418200
Check: 18753145125348788607553275398558954818510418200
 Time: 33.910s                    

1:
2:
3:
4:
5:
6:
7:
8:

var n: mp_int;
    s:array[0..255] of char;
begin
    mp_random_randomize;
    mp_init(n);
    strpcopy(s,bb);
    mp_read_radix(n,s,10);
...