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

Package: pari-stable; Maintainer for pari-stable is Aurel Page <aurel.page@normalesup.org>; Source for pari-stable is src:pari-stable.

Reported by: Kevin Buzzard <k.buzzard@imperial.ac.uk>

Date: Mon, 19 Mar 2012 11:18:16 UTC

Severity: normal

Done: Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>

Bug is archived. No further changes may be made.

Full log

🔗 View this message in rfc822 format

X-Loop: allomber@math.u-bordeaux.fr
Subject: Bug#1305: gp core() function: could do better?
Reply-To: Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>, 1305@pari.math.u-bordeaux.fr
Resent-From: Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>
Resent-To: bug-submit-list@pari.math.u-bordeaux.fr
Resent-CC: Karim.Belabas@math.u-bordeaux.fr
Resent-Date: Mon, 19 Mar 2012 12:18:09 UTC
Resent-Message-ID: <handler.1305.B1305.13321594425452@pari.math.u-bordeaux.fr>
Resent-Sender: allomber@math.u-bordeaux.fr
X-PARI/GP-PR-Message: report 1305
X-PARI/GP-PR-Package: pari-stable
X-PARI/GP-PR-Keywords: 
Received: via spool by 1305-submit@pari.math.u-bordeaux.fr id=B1305.13321594425452
          (code B ref 1305); Mon, 19 Mar 2012 12:18:09 UTC
Received: (at 1305) by pari.math.u-bordeaux.fr; 19 Mar 2012 12:17:22 +0000
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 1S9bWc-0001Pt-Iw
	for 1305@pari.math.u-bordeaux.fr; Mon, 19 Mar 2012 13:17:22 +0100
Received: from localhost (localhost.localdomain [127.0.0.1])
	by smail.math.u-bordeaux1.fr (Postfix) with ESMTP id 8793E713D1
	for <1305@pari.math.u-bordeaux.fr>; Mon, 19 Mar 2012 13:17:17 +0100 (CET)
X-Virus-Scanned: amavisd-new at math.u-bordeaux1.fr
X-Spam-Flag: NO
X-Spam-Score: 0.81
X-Spam-Level: 
X-Spam-Status: No, score=0.81 required=6 tests=[BAYES_50=0.8,
	RP_MATCHES_RCVD=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 JcHVFFN6Y8SF; Mon, 19 Mar 2012 13:17:16 +0100 (CET)
Received: from paridev.math.u-bordeaux1.fr (paridev.math.u-bordeaux1.fr [147.210.16.40])
	by smail.math.u-bordeaux1.fr (Postfix) with ESMTP id A430B711F1;
	Mon, 19 Mar 2012 13:17:16 +0100 (CET)
Received: from kb by paridev.math.u-bordeaux1.fr with local (Exim 4.72)
	(envelope-from <Karim.Belabas@math.u-bordeaux1.fr>)
	id 1S9bWW-0004kX-LC; Mon, 19 Mar 2012 13:17:16 +0100
Date: Mon, 19 Mar 2012 13:17:16 +0100
From: Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>
To: Kevin Buzzard <k.buzzard@imperial.ac.uk>, 1305@pari.math.u-bordeaux.fr
Message-ID: <20120319121716.GA18235@math.u-bordeaux1.fr>
References: <Pine.LNX.4.64.1203191057430.22497@crackerjack.ma.ic.ac.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
In-Reply-To: <Pine.LNX.4.64.1203191057430.22497@crackerjack.ma.ic.ac.uk>
User-Agent: Mutt/1.5.20 (2009-06-14)
Content-Transfer-Encoding: quoted-printable

Hi Kevin,

* 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]
> 
> What do you think of this?

No good :-)

> (11:00) gp > isprime(10^1000+1)
> %1 = 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?]

Trying to factor 10^1000 + 1, rather.

> 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...

Currently core(n) is implemented via 

  F = factor(n);
  weed_out_stuff_from(F);

which is sub­optimal for your example, even if factor() is trying to be
clever.

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).

Cheers,

    K.B.
--
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.

Bill Allombert <allomber@math.u-bordeaux.fr>. Last modified: Sat Aug 26 17:05:02 2023; Machine Name: pari

PARI/GP Bug tracking system

Debbugs is free software and licensed under the terms of the GNU Public License version 2. The current version can be obtained from https://bugs.debian.org/debbugs-source/.

Copyright © 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson, 2005-2017 Don Armstrong, and many other contributors.