In response to Taneli Huuskonen [mailto:[EMAIL PROTECTED]] Sorry to inflict this crapto on you. I came up with the algorithm when I read Ariel Waissbein's post. Waissbein said... check if a number of size 2^1024, e.g. 2^(2^1024), is congruent to 1 modulo the public exponent n. Hence you at least need to store 2^1024 digits in your computer which is a more than a lot. I knew about generators of cyclic groups, but I was inspired by the need for a solution to 2^X = 1 mod N, and I thought of shift-and-add on least significant zero bits as a way of generating a covering of the bitmap of all ones. Talk about synchronicity... I wrote and posted, then I ran out for dinner (yes, you can flame me for not doing the literature search). Later, I read through the web links, and saw that the solution was identical to the one of de Velez that was torn apart by Rivest a day before (well, almost synchronous). I don't recall seeing de Velez's method explicitly discarding the low order one bits to conserve memory once they are not needed. His inspiration clearly comes from shift registers, so he could have defended his design by observing that he could discard low order bits, but he didn't, and he caved in to the experts. So I won't give him credit for that part, but he did come up with shift-and-add first. I violated the memory space constraint with the following snippet of code: > # complete the solution. > $b = $a * $n + 1; > $x = -1; > while ($b != 0) { > $b >>= 1; > $x++; > } It should be replaced with: # complete the solution. $x = $p; $b++; # this is a power of 2 while ($b != 1) { $b >>= 1; $x++; } Please look over the code again. I wrote it to refute the argument that you need to concurrently store all the digits for 2^X, which it doesn't, in deriving the number 'a', in aN + 1. The low order one bits of 2^X - 1 are discarded by a right shift after they have been computed and counted. At every step, the addition may produce a carry bit beyond the register, but shifting restores the sum within the bounds. > Sorry to be a wet blanket, but it should be "O(N) time". As > a factoring method, this is less efficient than trial division. Wait a second. I seem to have confused some folks about what the above algorithm accomplishes. It doesn't break RSA, it solves a problem in number theory. And it doesn't take O(N). At worst, the outer loop is once per bit of N (ie. log N) and the inner loop counts bits of N (again, log N). Ergo, the routine runs in time O(log N)^2. If in breaking RSA, some specific value of X is required other than the one that this routine finds, then yes, you'll need to keep shifting and adding to find ever larger values of 'a' and X. But I thought that this value of X is the order of 2, and that 2 is a generator of the cyclic group 1 (mod N). I will humbly accept your corrections in public, for the benefit of all. <shuts eyes tightly and braces for flogging> Robert Lacroix

- Pinoy math enthusiast finds fast way to decode RSA encr... Andre Delafontaine
- Re: Pinoy math enthusiast finds fast way to decode... Howard Lowndes
- Re: Pinoy math enthusiast finds fast way to decode... Stephen Clouse
- Re: Pinoy math enthusiast finds fast way to decode... Ariel Waissbein
- Re: Pinoy math enthusiast finds fast way to decode... Alan Day
- Re: Pinoy math enthusiast finds fast way to decode... Lacroix, Robert
- Re: Pinoy math enthusiast finds fast way to de... Taneli Huuskonen
- Re: Pinoy math enthusiast finds fast way to de... Padmapani S Ganti
- Re: Pinoy math enthusiast finds fast way t... Thomas Quinot
- Re: Pinoy math enthusiast finds fast way t... Markus Senoner

- Lacroix, Robert