Fwd: Coppersmith's small root finding for modular polynomials

[John Cremona]

Am I right in thinking that this is in Sage?

John

---------- Forwarded message ----------
From: Max Alekseyev <max...@gmail.com>
Date: 2008/4/26
Subject: Coppersmith's small root finding for modular polynomials
To: pari-users <pari-...@list.cr.yp.to>

Hello!

I wonder whether Don Coppersmith's method for finding small root of
modular polynomial is implemented in PARI/GP?
If not, is there any third party implementations available?

Thanks,
Max

[mabshoff]

On Apr 26, 11:57 am, "John Cremona" <john.crem...@gmail.com> wrote:

Hi John,

> Am I right in thinking that this is in Sage?

Yes, I saw the email on the pari user's list and thought the same
thing. IIRC this was implemented by Martin Albrecht in Sage 2.11:

* Small roots method for polynomials mod N (N composite): Martin
Albrecht implemented Coppersmith's method for finding small roots
of univariate polynomials modulo N where N is composite.

More info on #2424. I figure it is best if you answer the email on the
pari user's list.

Cheers,

Michael

[John Cremona]

2008/4/26 mabshoff <Michael...@mathematik.uni-dortmund.de>:

>
>
>
> On Apr 26, 11:57 am, "John Cremona" <john.crem...@gmail.com> wrote:
>
> Hi John,
>
>
> > Am I right in thinking that this is in Sage?
>
> Yes, I saw the email on the pari user's list and thought the same
> thing. IIRC this was implemented by Martin Albrecht in Sage 2.11:
>
> * Small roots method for polynomials mod N (N composite): Martin
> Albrecht implemented Coppersmith's method for finding small roots
> of univariate polynomials modulo N where N is composite.
>
> More info on #2424. I figure it is best if you answer the email on the
> pari user's list.

I decided that was unnecessary as the question had already been
answered positively (gp has a function zncoppersmith which does this).

John

[Martin Albrecht]

On Saturday 26 April 2008, John Cremona wrote:
> Am I right in thinking that this is in Sage?
>
> John

Just for the archives: Yes, it is in Sage too:

http://trac.sagemath.org/sage_trac/ticket/2424

But as Pari has it too it seems we could just call that and be done.

Martin

--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_www: http://www.informatik.uni-bremen.de/~malb
_jab: martinr...@jabber.ccc.de