Re: N S.T. isfact returns 0

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Fri, Nov 24, 2023 at 09:18:32PM -0800, Thomas D. Dean wrote:
> I was looking at foursquares-2.16.1.gp. In the function threesquares(n),
> isfact(n) is used to select the method of calculation. I think it always
> uses threesquares_fact(n,F).

The purpose of isfact is to check whether a number is "easy to factor".
I define "easy to factor" as follow:
N is "easy to factor" if all its distinct prime factors, except at most one, are smaller
than 2^20. (This implies that GP factor function will factor it very quickly).

Prime numbers and prime powers are always "easy to factor".
Every number smaller than 2^40 is easy to factor.
the smallest number which is not easy to factor is 1099532599387.

If you pick a random n-bit number, it has probability 1/(n*log(2))=1.44/n to be prime,
and probability at least 35.6/n to be "easy to factor".

> I checked isfact(a^2+b^2+c^2) up to a==b==c==100 and found nothing.

a^2+b^2+c^2 is always <= 2^40 in your range, so they are all "easy to factor".

Cheers,
Bill