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

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

On Wed, Jun 21, 2023 at 03:27:05PM +0200, hermann@stamm-wilbrandt.de wrote:
> On 2023-06-21 13:06, Andreas Enge wrote:
> > Do it the other way round:
> >    Mod(2,n)^(n+1).
> > This way, exponentiation happens directly in Z/nZ (by successive
> > squaring
> > and multiplying, each followed by a reduction modulo n), instead of
> > trying
> > to compute integers that may not fit into the universe.
> > 
> Thank you, that worked perfectly.
> 
> I am positively surprised of znlog() speed on big numbers (on i7-11850H CPU)
> ...
> 
> Knowing "n+1-(p-1)*(q-1)=p+q" allows to factor "n=p*q"
> https://en.wikipedia.org/wiki/Vieta%27s_formulas#Example
> (factoring of RSA-79 in 6:34min below, slower than 1.54min(msieve) and
> 4:15min(GP factor below))
> 
> https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/pari/RSA_numbers_factored.gp
> 
> $ gp-2.15 -q
> ? \r RSA_numbers_factored
> ? [l,n,p,q] = rsa[1][1..4];
> ? [l, n==p*q && (l==#digits(n)) || (l==#digits(n,2))]
> [59, 1]
> ? znlog(Mod(2, n)^(n+1), Mod(2, n))
> 557869722222203919880529024454
> ? ##
>   ***   last result computed in 6,047 ms.
> ? [l,n,p,q] = rsa[2][1..4];
> ? znlog(Mod(2, n)^(n+1), Mod(2, n))
> 9447104136878167876008523981447380846704
> ? ##
>   ***   last result computed in 6min, 33,579 ms.

You can speed up this by doing
addprimes([p,q])
so that znlog does not need to factor n.

But the cost of znlog is related to the largest prime factor of eulerphi(n),
not of n.

Cheers,
Bill.