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

[hermann@stamm-wilbrandt.de]

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 ...
>
> $ gp-2.13 -q
> ? \r RSA_numbers_factored
> ? [l,n,p,q]=rsa[1][1..4]
> [59, 71641520761751435455133616475667090434063332228247871795429,
> 200429218120815554269743635437, 357440504101388365610785389017]
> ? vecmax(factor(eulerphi(p)*eulerphi(q)))
> 5880369817360553
> ?
> ? [l,n,p,q]=rsa[2][1..4];
> ? vecmax(factor(eulerphi(p)*eulerphi(q)))
> 134611158882680922107
> ?
> ? [l,n,p,q]=rsa[3][1..4];
> ? m = vecmax(factor(eulerphi(p)*eulerphi(q)))
> 38273186726790856290328531
> ? print(#digits(n), " ", #digits(p), " ", #digits(q), " ", #digits(m))
> 100 50 50 26
> ?
There is a lower bound of 2*sqrtint(n) for p+q, which can be subtracted 
from n+1.
We do not know factor f = q/p > 1, with that factor bound is 
(1+f)/sqrt(f)*sqrt(n).

I did factor RSA-100 last night with this method.
It worked, but took more than 11 hours to compute, while msieve takes 
less than 2.5h on same CPU.

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.
?
? 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.
?


Regards,

Hermann.