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

[hermann@stamm-wilbrandt.de]

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.
? l
79
? n+1-(p-1)*eulerphi(q)
9447104136878167876008523981447380846704
? factor(n)
%20 =
[ 848184382919488993608481009313734808977 1]

[8598919753958678882400042972133646037727 1]

? ##
  ***   last result computed in 4min, 14,751 ms.
?



Regards,

Hermann.