From: invalid@invalid.invalid   
      
   Sylvia Else  writes:   
   > Sometimes in an idle moment, I find myself wondering about possible   
   > ways to attack RSA. Spoiler alert, I haven't found one.   
   >   
   > But in passing, I found myself thinking about this:   
   >   
   > For the uninitiated, RSA is based on the fact that if p and q are   
   > large primes, then the product p*q is a large number that is   
   > computationally infeasible to factorise - which is to say, no one's   
   > found a way, though quantum computers offer a possibility.   
   >   
   > Let m be p * q, and n be (p-1)(q-1).   
      
   Conventional notation is n=pq. So this is a rather confusing way to put   
   it.   
      
   > Then RSA further depends on the fact that for any integer a, co-prime   
   > with m, a^n modulo m is 1. Since 2 will be co-prime with m, that means   
   > that 2^n modulo m is also 1. We can write that equivalently as   
   >   
   > 	2^n - 1 = k * m   
      
   In more conventional notation:   
      
      2^[(p-1)(q-1)] - 1 = kn   
      
   > where k is an unknown integer. Actually, there are an infinity of   
   > possible k, but we're interested in the lowest (ignoring the trivial   
   > case of k = 0).   
      
   There’s only one k, and it’s k = (2^[(p-1)(q-1)] - 1) / n.   
      
   For RSA-2048 that would give us log_2(k) =~ 2^2048. Even if you   
   converted the entire solar system into a computer, it’d be much too big   
   to represent.   
      
   --   
   https://www.greenend.org.uk/rjk/   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)