[Vm-dev] BUG in Montgomery multiplication

[Nicolas Cellier]

Recent addition, montgomery multiplication, has a bug:
it fails to correctly take last carry into account...

You can see it with this example (if you have the Smalltalk mock up) :

| m mInv a b |
m := 15485863.
mInv := 256 - ((m bitAnd: 255) reciprocalModulo: 256).
a := 8826019 digitMontgomeryTimes: 8826019 modulo: m mInvModB: mInv.
b := 8826019 naiveMontgomeryTimes: 8826019 modulo: m mInvModB: mInv.
self assert: a = b

Correct result is given by naive mock up : 10626344
The primitive gives a wrong result.

I attach a correction for the LargeInteger plugin (and for the
Smalltalk mock up too).

Sorry for uncomplete tests.
Please, update VMMaker ASAP.

Nicolas
-------------- next part --------------
A non-text attachment was scrubbed...
Name: LargeIntegersPlugin-cdigitMontgomerylentimeslenmodulolenmInvModBinto.st
Type: application/octet-stream
Size: 2233 bytes
Desc: not available
Url : http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20110604/a7f21ae9/LargeIntegersPlugin-cdigitMontgomerylentimeslenmodulolenmInvModBinto.obj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Integer-digitMontgomeryTimesmodulomInvModB.st
Type: application/octet-stream
Size: 2196 bytes
Desc: not available
Url : http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20110604/a7f21ae9/Integer-digitMontgomeryTimesmodulomInvModB.obj