Hi All,
Does anyone have any issues with Nicolas' comments? On the surface his points look valid. I have not researched best practices for these algorithms so I am weary to want to change them, unless they fix a significant bug or performance problem.
But they are very nice examples of some very nice bit twiddling.
Thoughts?
Ron
-----Original Message----- From: squeak-dev-bounces@lists.squeakfoundation.org [mailto:squeak-dev-bounces@lists.squeakfoundation.org] On Behalf Of nicolas cellier Sent: Thursday, July 10, 2008 10:56 PM To: squeak-dev@lists.squeakfoundation.org Subject: [squeak-dev] DigitalSignatureAlgorithm cosmetic refactoring
Reading these classes, i see some possible cleaning:
ThirtyTwoBitRegister>>leftRotateBy: bits [...] bitCount _ bits \ 32. bitCount < 0 ifTrue: [bitCount _ bitCount + 32].
This second line is useless, bits \ 32 will be positive (not the case of (bits rem: 32) if bits negative).
=====> This is certainly true - Ron --------------------------------------------------
This algorithm could avoid duplicating lowBit:
DigitalSignatureAlgorithm>>logOfLargestPowerOfTwoDividing: aStrictlyPositiveInteger ^aStrictlyPositiveInteger lowBit - 1
======> By testing this I can see it is true, and a very beautiful algorithm by the way. I can't see the proof. Out of curiosity why is this true? - Ron --------------------------------------------------
DigitalSignatureAlgorithm>>inverseOf: x mod: n [...] v _ x. u _ n. k _ 0. [x even and: [n even and: [u > 0]]] whileTrue: [ "eliminate common factors of two" k _ k + 1. u _ u bitShift: -1. v _ v bitShift: -1].
This has not much sense. Should be [u even and: [v even]] whileTrue: [...]
Or even better: k := u lowBit min: v lowBit. u := u >> k. v := v >> k.
Or even better: (u even and: [v even]) ifTrue: [self error: 'no inverse'] because a pair of integers {a. b} satisying (2 * u) * a + ((2 * v) * b) = 1 will be hard to find...
(Algorithm uselessly repeat (n highBit * 2) bitShift: before obtaining luckily this 'no inverse' result)
=======> Looking at this it makes sense. It looks similar to the logofLargestPowerOfTwoDividing. Can you explain why this works. I see that it is using the lowest common even position to shift the values.
I don't think that this was a lucky hit of a no inverse since it is the result of the multiplication of two primes. Taken as a general algorithm this would be true. You have to wonder if these techniques should not be moved into a more general format and moved into an extension of Integer or ThirtyTwoBitRegister instead of being hidden within DSA.
Thanks,
Ron Teitelbaum
Nicolas, would you consider taking over the Cryptography Team? There hasn't been much progress here and we could use some new leadership.