PARI/GP Bug report logs - #1305
gp core() function: could do better?

Full log

🔗 View this message in rfc822 format

X-Loop: allomber@math.u-bordeaux.fr
From: allomber@math.u-bordeaux.fr (PARI/GP Bug Tracking System)
To: Kevin Buzzard <k.buzzard@imperial.ac.uk>
Subject: Bug#1305 acknowledged by developer
         (Re: Bug#1305: gp core() function: could do better?)
Message-ID: <handler.1305.D1305.133711604014023.notifdone@pari.math.u-bordeaux.fr>
In-Reply-To: <Pine.LNX.4.64.1203191057430.22497@crackerjack.ma.ic.ac.uk>
References: <20120515210713.GA13972@math.u-bordeaux1.fr> <Pine.LNX.4.64.1203191057430.22497@crackerjack.ma.ic.ac.uk>
X-PARI/GP-PR-Message: they-closed 1305
X-PARI/GP-PR-Package: pari-stable
X-PARI/GP-PR-Keywords: 
Reply-To: 1305@pari.math.u-bordeaux.fr

This is an automatic notification regarding your Bug report
#1305: gp core() function: could do better?,
which was filed against the pari-stable package.

It has been closed by one of the developers, namely
Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>.

Their explanation is attached below.  If this explanation is
unsatisfactory and you have not received a better one in a separate
message then please contact the developer, by replying to this email.

Bill Allombert
(administrator, PARI/GP bugs database)

Received: (at 1305-close) by pari.math.u-bordeaux.fr; 15 May 2012 21:07:20 +0000
From Karim.Belabas@math.u-bordeaux1.fr Tue May 15 23:07:20 2012
Received: from smail.math.u-bordeaux1.fr ([147.210.16.22])
	by pari.math.u-bordeaux1.fr with esmtp (Exim 4.72)
	(envelope-from <Karim.Belabas@math.u-bordeaux1.fr>)
	id 1SUOxk-0003e8-Ci
	for 1305-close@pari.math.u-bordeaux.fr; Tue, 15 May 2012 23:07:20 +0200
Received: from localhost (localhost.localdomain [127.0.0.1])
	by smail.math.u-bordeaux1.fr (Postfix) with ESMTP id 5D1D370C7E
	for <1305-close@pari.math.u-bordeaux.fr>; Tue, 15 May 2012 23:07:15 +0200 (CEST)
X-Virus-Scanned: amavisd-new at math.u-bordeaux1.fr
X-Spam-Flag: NO
X-Spam-Score: 0.811
X-Spam-Level: 
X-Spam-Status: No, score=0.811 required=6 tests=[BAYES_50=0.8,
	RCVD_IN_SORBS_DUL=0.001, RDNS_DYNAMIC=0.01] autolearn=disabled
Received: from smail.math.u-bordeaux1.fr ([127.0.0.1])
	by localhost (smail.math.u-bordeaux1.fr [127.0.0.1]) (amavisd-new, port 10024)
	with ESMTP id 4PtRHOZdcyvA; Tue, 15 May 2012 23:07:14 +0200 (CEST)
Received: from colibri.math.u-bordeaux1.fr (tal33-1-82-226-197-154.fbx.proxad.net [82.226.197.154])
	(using TLSv1 with cipher AES256-SHA (256/256 bits))
	(No client certificate requested)
	by smail.math.u-bordeaux1.fr (Postfix) with ESMTP id 7F7407079D;
	Tue, 15 May 2012 23:07:14 +0200 (CEST)
Received: from kb by colibri.math.u-bordeaux1.fr with local (Exim 4.77)
	(envelope-from <Karim.Belabas@math.u-bordeaux1.fr>)
	id 1SUOxd-0003do-El; Tue, 15 May 2012 23:07:13 +0200
Date: Tue, 15 May 2012 23:07:13 +0200
From: Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>
To: Kevin Buzzard <k.buzzard@imperial.ac.uk>,
	1305-close@pari.math.u-bordeaux.fr
Subject: Re: Bug#1305: gp core() function: could do better?
Message-ID: <20120515210713.GA13972@math.u-bordeaux1.fr>
References: <Pine.LNX.4.64.1203191057430.22497@crackerjack.ma.ic.ac.uk>
 <20120319121716.GA18235@math.u-bordeaux1.fr>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
In-Reply-To: <20120319121716.GA18235@math.u-bordeaux1.fr>
User-Agent: Mutt/1.5.21 (2010-09-15)
Content-Transfer-Encoding: quoted-printable

* Karim Belabas [2012-03-19 13:17]:
> Hi Kevin,
>=20
> * Kevin Buzzard [2012-03-19 12:37]:
> > [Sorry -- I should upgrade to 2.5.1, but I didn't yet, and I don't
> > see core mentioned in the changelog 2.5.0->2.5.1 so let me gamble
> > that this is still an issue]
> >=20
> > What do you think of this?
>=20
> No good :-)
>=20
> > (11:00) gp > isprime(10^1000+1)
> > %1 =3D 0
> > (11:00) gp > core(5*(10^1000+1)^2)
> > [gp now goes into a very long loop, presumably because it's trying
> > to factor (10^1000+1)^2?]
>=20
> Trying to factor 10^1000 + 1, rather.
>=20
> > I am not C++-savvy enough to know what the "core" function was doing
> > in 2.5.0, but in this particular case I can see a relatively simple
> > way of spotting the answer: if we use trial division or ECM or
> > whatever to find a few small factors, then could it be worth
> > checking to see if what we have left is a square?? If it is then
> > we're done. Presumably core() is not currently doing this...
>=20
> Currently core(n) is implemented via=20
>=20
>   F =3D factor(n);
>   weed_out_stuff_from(F);
>=20
> which is sub=ADoptimal for your example, even if factor() is trying to =
be
> clever.
>=20
> I'll try to come up with a nice generic implementation (as opposed to a
> quick hack starting from a full copy of the factoring engine + minor
> tweakings to hunt for square factors).

Done in master (testing branch 2.6.*)

(23:06) gp > core(5*(10^1000+1)^2)
time =3D 36 ms.
%1 =3D 5

Thanks for your feedback !


    K.B.
--=20
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP=
]
`

Send a report that this bug log contains spam.