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

[hermann@stamm-wilbrandt.de]

On 2023-06-21 18:00, Bill Allombert wrote:
> You can speed up this by doing
> addprimes([p,q])
> so that znlog does not need to factor n.
Only if knowing p and q, not when trying to factor n ;-)

> But the cost of znlog is related to the largest prime factor of 
> eulerphi(n),
> not of n.
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
?


Regards,

Hermann.