[Vm-dev] BUG in Montgomery multiplication

David T. Lewis lewis at mail.msen.com
Sat Jun 4 18:07:59 UTC 2011


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



More information about the Vm-dev mailing list