bob
Reputation
1,075
Top tag
Next privilege 2,000 Rep.
 Dec 11 awarded Necromancer Dec 4 awarded Quorum Nov 22 awarded Scholar Nov 22 accepted Efficient setup for a Montgomery multiplication Nov 14 comment Efficient setup for a Montgomery multiplication @mikeazo: I said you're correct and also +1'd your comment as it is indeed one way to solve the thing. But you know how it is in today's world: you spare every single bit that you can :D Also, the computation of $R^2 \mod N$ must be performed each time the modulus changes, so depending on the setting, this can happen often and might not be easily precomputed. Nov 14 revised Efficient setup for a Montgomery multiplication edited body Nov 14 comment Efficient setup for a Montgomery multiplication @mikeazo: This is one way to do it, of course. But it is not efficient as it requires a true multiplication mod $N$ whereas the purpose of Montgomery's multiplication was to be more efficient. Hence, although the cost for it gets lower with the number of Montgomery multiplications performed in this representation, one wants to reduce it if possible. Nov 14 comment Efficient setup for a Montgomery multiplication @B-Con: I'd say as much as Montgomery multiplication has: I'm not sure if there are many other settings where one wants to compute modular exponentiations with a modulus of 4096 bits :D Nov 14 revised Efficient setup for a Montgomery multiplication added 663 characters in body; edited title Nov 13 revised What does Maj and Ch mean in SHA-256 algorithm? typo in title Nov 13 suggested approved edit on What does Maj and Ch mean in SHA-256 algorithm? Nov 13 revised Montgomery Exponentiation - selecting input value R for a given BigInteger edited tags Nov 13 asked Efficient setup for a Montgomery multiplication Nov 9 comment Randomized algorithms and the one time pad If one think of the key as the whole set of pads, as described above, there is no problem at all provided you always pad the same message with the same pad. (The only problem is that "standard one-time pad" does not really specify what happens when you come to encrypt the same message twice.) The resulting scheme will be semantically secure, assuming the events from your dice are uniformly distributed. (I'm actually thinking of such truly random pads in the example scheme defined above.) Still, the resulting encryption algorithm is fully deterministic (not randomized/probabilistic). Nov 8 comment Randomized algorithms and the one time pad @PaŭloEbermann: Indeed, thank you. Nov 8 revised Randomized algorithms and the one time pad added 14 characters in body Nov 8 revised Randomized algorithms and the one time pad added 9 characters in body Nov 8 comment Randomized algorithms and the one time pad @John Deters: You're correct. This is why I stressed that one-time pad does not fit the framework. I'll change the wording accordingly. Thanks. Nov 8 comment Randomized algorithms and the one time pad @fgrieu: I fail to see what you mean by "difficult goal". A randomized algorithm can be used for any kind of goal. Although it is true that they are often the only known algorithms to efficiently solve some difficult problems, it is also not known that there cannot always be a deterministic algorithm solving the same problem at least as efficiently. Also, in your example, the randomized version for factorization you give is less efficient than the deterministic one. I guess this comes from the typical representation of an attacker as a probabilistic polynomial time algorithm. Nov 8 answered Randomized algorithms and the one time pad