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

[hermann@stamm-wilbrandt.de]

On 2023-06-22 07:30, hermann@stamm-wilbrandt.de wrote:
> On 2023-06-21 18:27, hermann@stamm-wilbrandt.de wrote:
> > That is cool, eulerphi(n) = eulerphi(p) * eulerphi(q) allows to
> > compute without factoring RSA-100. Largest prime factor of
> > eulerphi(RSA-100) is only 26-digit number, while p and q are 50-digit
> > numbers ...
...
> ? znlog(Mod(2, n)^(n+1-d2), Mod(2, n))
> 28775177062023928913461369238354205970422561872
> ? ##
>   ***   last result computed in 11h, 12min, 15,497 ms.
> ?
> ? fact(spq, pq) = { hspq=spq\2; s=sqrtint(hspq^2-pq); [hspq-s,hspq+s]; 
> }
> ? fact(28775177062023928913461369238354205970422561872 + d2, n) == [p, 
> q]
> 1
> ? ##
>   ***   last result computed in 0 ms.
> ?
RSA_numbers_factored.gp rsa vector contains prime factorizations for p-1 
and q-1
for RSA numbers up to RSA-220. 3rd column is number of decimal digits of 
biggest
prime factor of p or q. Grows too fast to be useful for factoring.

$ gp-2.15 -q
? \r RSA_numbers_factored
?
? for(i=1,#rsa,\
    if(#rsa[i]==6,\
      print(rsa[i][1], " ", #digits(rsa[i][2]), " ", 
#digits(max(vecmax(rsa[i][5]),vecmax(rsa[i][6]))))\
    )\
  )
59 59 16
79 79 21
100 100 26
110 110 50
120 120 34
129 129 63
130 130 39
140 140 52
150 150 53
155 155 69
160 160 43
170 170 83
576 174 40
180 180 79
190 190 75
640 193 79
200 200 92
210 210 82
704 212 79
220 220 58
?


Regards,

Hermann.