Re: How to compute "Mod(2^(n+1), n)" for very big n?

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

On Thu, Jun 22, 2023 at 07:30:27AM +0200, hermann@stamm-wilbrandt.de wrote:
> Anyway, here is gp session (with definition of function "fact()" factoring
> given sum and product):
> 
> RSA_numbers_factored/pari:$ gp-2.15 -q
> ? \r RSA_numbers_factored
> ? [l,n,p,q] = rsa[3][1..4];
> ? [l, l==#digits(n) && n=p*q]
> [100, 1]
> ? d2 = 2 * sqrtint(n)
> 78041143710802531024579146678968742037810013800388
> ? #digits(p+q)
> 50
> ? #digits(p+q-d2)
> 47
> ? znlog(Mod(2, n)^(n+1-d2), Mod(2, n))
> 28775177062023928913461369238354205970422561872
> ? ##
>   ***   last result computed in 11h, 12min, 15,497 ms.

Well, if you do addprimes([p,q]) it only take 45 minutes.
so taking 10h30 to factor RSA100 is not that bad.

Cheers,
Bill.