/usr/share/doc/pari-gp/examples/squfof.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 | \\ return one non-trivial divisor of n > 1 using Shanks's SQUFOF
squfof(n) =
{
if (isprime(n) || issquare(n, &n), return(n));
p = factor(n,0)[1,1];
if (p != n, return(p));
if (n%4==1,
D = n; d = sqrtint(D); b = (((d-1)\2) << 1) + 1
,
D = n << 2; d = sqrtint(D); b = (d\2) << 1
);
f = Qfb(1, b, (b^2-D)>>2);
l = sqrtint(d);
q = []; lq = 0; i = 0;
while (1,
i++;
f = qfbred(f, 3, D, d);
a = component(f, 1);
if (!(i%2) && issquare(a, &as),
j = 1;
while (j<=lq,
if (as == q[j], break);
j++
);
if (j > lq, break)
);
if (abs(a) <= l,
q = concat(q, abs(a));
print(q); lq++;
)
);
print("i = ", i); print(f);
bb = component(f, 2);
gs = gcd([as, bb, D]);
if (gs > 1, return (gs));
f = Qfb(as, -bb, as*component(f,3));
g = qfbred(f, 3, D, d);
b = component(g, 2);
until (b1 == b,
b1 = b; g = qfbred(g, 3, D, d);
b = component(g, 2);
);
a = abs(component(g, 1));
if (a % 2, a, a>>1);
}
|