Re: fun RSA-like number

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

On Fri, Jun 08, 2007 at 11:17:28PM +0200, Alain SMEJKAL wrote:
> > I found this funny RSA challenge-like number:
> >
> > ?
> 2232910609332187886082982422994038035269933607980867743982829475969531575124
> 064916213584339209041654201264049086377750345171525039801
> 
> Hello all,
> 
> More than fun, this number can prove efficiency of GP scripts.
> Here, flags used with factorint indicates that internal Pollard-Brent Rho or
> SQUFOF algorithm is used for factorization.

SQUFOF is not used for this size.

> Using a classical Pollard-Brent Rho GP script implementation, factorization
> time can be largely reduced (maybe much more with gp2c).
> Thanks for this handy, reliable and fast software !
> 
> gp > for (i=1,100,y=factor(n))
> time = 3,234 ms.
> gp > for (i=1,100,y=factorint(n,11))
> time = 3,219 ms.
> gp > for (i=1,100,y=rhobrent(n))
> time = 79 ms.

rhobrent is only faster because it does not check the pseudo-primality of the
factors. Only 4 round of Pollard rho are needed, which is about a 
dozen squaring, maybe 60 if you use Pollard-Brent.

> > Another one, different in nature:
> >
> > ?
> 3153627868433467319941213011803229193910650395093119880070890986935182829794
> 577898323490044799996388232993633159912821646956999337547873980207
> 
> Here, Rho-Brent does not work and time can be saved using factorint
> restricted to ECM.
> However it is really funny to find so large factors so fast by ECM.

Actually it is simply very unlikely. If we get to control the odd, we
can 'find' much larger factors.  Try this one:

854052907557554874716441204433916311020596682548761872691500353741788893508429705941362695058736053698872868862445627304386258672079409589041995376010885393632150263526003879162163615651905190482081142185927148352249328997873682823395754046570770799547630707945990317370763405950725012777940864867419708980955854688659733271836605839677877064566507269592912955809510919134014535638890726991

Cheers,
Bill.