/usr/share/doc/pari-gp/examples/rho.gp is in pari-gp 2.5.5-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 | rho1(n)=
{ my(x = 2,y = 5);
while(gcd(y-x,n) == 1,
x = (x^2+1)%n;
y = (y^2+1)%n; y = (y^2+1)%n
);
gcd(n, y-x);
}
rho2(n)=
{ my(m = rho1(n));
if (isprime(m), print(m), rho2(m));
if (isprime(n/m), print(n/m), rho2(n/m));
}
rho(n)=
{ my(m = factor(n,0));
print(m); m = m[,1]; n = m[#m];
if (!isprime(n), rho2(n));
}
rhobrent(n)=
{ my(x,y,x1,k,l,p,c,g);
x1 = x = y = 2;
k = l = p = 1;
c = 0;
while (1,
x=(x^2+1)%n; p=(p*(x1-x))%n;
c++;
if (c==20,
if (gcd(p,n)>1, break);
y = x; c = 0
);
k--;
if (!k,
if (gcd(p,n)>1, break);
x1 = x; k = l; l <<= 1;
for (j=1,k, x = (x^2+1)%n);
y = x; c = 0
)
);
until (g != 1,
y = (y^2+1)%n;
g = gcd(x1-y,n)
);
if (g==n, error("algorithm fails"));
g;
}
|