[Vm-dev] BUG in Montgomery multiplication

[Nicolas Cellier]

Thanks !
There is now a test in trunk.

Nicolas

2011/6/4 David T. Lewis <lewis at mail.msen.com>:
>
> On Sat, Jun 04, 2011 at 12:29:37AM +0200, Nicolas Cellier wrote:
>>
>> 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
>
> Thanks,
>
> This is updated in VMMaker-dtl.239 (interpreter VM) and VMMaker.oscog-dtl.71
> (for Cog).
>
> Dave
>
>