From: sylvia@email.invalid   
      
   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). 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   
      
   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).   
      
   If we knew k, then that would give us n, or a factor of n (n is never   
   prime, it is at least divisible by 4). The method I came up with is to   
   start with a variable v initialised to m. Then repeatedly look for the   
   lowest zero bit in v, say bit i, and add m * 2^i to v. That will set   
   that bit, but not disturb any bits lower than i. So, just do this   
   repeatedly, until v is a continuous sequence of 1s.   
      
   But remember the spoiler alert. Outside of some very improbable cases,   
   for realistic values of m used in RSA, this will take longer than the   
   time remaining in the Universe to terminate.   
      
   I think it's reasonably obvious that if the algorithm terminates, it   
   will yield a value that is not greater than n. So here's the question:   
   Leaving aside concerns about the longevity of the Universe, can one be   
   sure that it will ever terminate?   
      
   Sylvia.   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)