Karim Belabas on Wed, 28 Apr 2010 13:04:33 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Big number division bug?


* James Wanless [2010-04-28 12:41]:
> I don't know if PARI is intended to handle such big numbers, but:
> 
> ? (2^43112609+1)%(3*86225219*5259738299*5949540043)
> %1 = 0
> ? (2^43112609+1)%12482997260297
> %2 = 0
> ? (2^43112609+1)%453522086713962481
> %3 = 0
> ? (2^43112609+1)%(3*86225219*5259738299*5949540043*12482997260297*453522086713962481)
> %4 = 20781231343178972948687277924200040219405288340527425880342
> 
> [GMP-ECM shows the same problem, so I don't know if it could even be
> a bug in GMP???]

I do not see a problem there : your moduli are not coprime
( in fact, 453522086713962481 divides 3*86225219*5259738299*5949540043)
so you can't deduce that the result should be 0 by the CRT.

What result were you expecting ?

Cheers,

    K.B.

P.S: The result given is consistent with the output of
   N = 3*86225219*5259738299*5949540043*12482997260297*453522086713962481
   lift( Mod(2,N)^43112609 + 1 )
which handles only tiny integers.

--
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-bordeaux.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`