[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