[ruby-core:48552] [ruby-trunk - Bug #7242][Open] Bignum mathematical accuracy regression in r31695

[ruby-core:48552] [ruby-trunk - Bug #7242][Open] Bignum mathematical accuracy regression in r31695

[mhall (Matthew Hall)]

Issue #7242 has been reported by mhall (Matthew Hall).

----------------------------------------
Bug #7242: Bignum mathematical accuracy regression in r31695
https://bugs.ruby-lang.org/issues/7242

Author: mhall (Matthew Hall)
Status: Open
Priority: Normal
Assignee: mrkn (Kenta Murata)
Category: 
Target version: 
ruby -v: ruby 1.9.3dev (2011-05-22 trunk 31695) [x86_64-linux]


We have some pure Ruby code which performs a DH (Diffie Hellman) cryptographic 
handshake.

If I upgrade to using the Ruby 1.9.3 interpreter instead of 1.9.2, the unit
tests around the code fail, because the client and server can no longer
compute matching secret keys. I would expect they could agree on matching keys
as the DH algorithm expects. The code worked fine since May 2007 on Ruby 1.8 
and 1.9 until the commit below was introduced.

Using svn-bisect, I was able to find that this commit from ruby-trunk in
between Ruby 1.9.2 (27656) and Ruby 1.9.3 (32500) causes the problem:

r31695 | mrkn | 2011-05-22 08:37:00 -0700 (Sun, 22 May 2011) | 4 lines

* bignum.c (dump_bignum, bigmul1_balance, big_split, biglsh_bang,
  bigrsh_bang, big_split3, bigmul1_toom3, bigmul0): implement Toom3 (Toom-Cook)
  multiplication.
* include/ruby/defines.h: add format prefixes for BDIGIT and BDIGIT_DBL.

Attached to this bug I have a simplified example test case which will pass 
without this commit, and fail with this commit present.

Since this commit covers some relatively complex mathematical algorithms I'd
appreciate some assistance in finding the root cause from the experts on how
bignum.c works. I think the bug is relatively serious because it could cause
inaccurate output for other mathematical code using Bignums since it was
introduced in mid-2011.

This ruby -v comes from ruby trunk SVN at revision 31695, where the failure 
begins to happen. I hand-re-compiled at the bisection points on trunk from
27655 through 32501 to identify the one which caused the problem.

$ ruby -v
ruby 1.9.3dev (2011-05-22 trunk 31695) [x86_64-linux]

C Compiler: gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3

configure params:

./configure \
--with-static-linked-ext \
--prefix=/usr/local/ruby192 \
--enable-shared \
--with-ruby-version=full


-- 
http://bugs.ruby-lang.org/

[ruby-core:48590] [ruby-trunk - Bug #7242][Assigned] Bignum mathematical accuracy regression in r31695

[mame (Yusuke Endoh)]

Issue #7242 has been updated by mame (Yusuke Endoh).

File toom3-bug.py.rb added
Status changed from Open to Assigned
Priority changed from Normal to Urgent
Target version set to 2.0.0

Hello,

2012/10/30, mhall (Matthew Hall) <mhall@mhcomputing.net>:
> Attached to this bug I have a simplified example test case which will pass 
> without this commit, and fail with this commit present.

Good catch!  I created a more simplified example.

    $ ruby toom3-bug.py.rb
    $ python toom3-bug.py.rb

Python seems to output the correct answer.
mrkn, could you check it out?

-- 
Yusuke Endoh <mame@tsg.ne.jp>
----------------------------------------
Bug #7242: Bignum mathematical accuracy regression in r31695
https://bugs.ruby-lang.org/issues/7242#change-31976

Author: mhall (Matthew Hall)
Status: Assigned
Priority: Urgent
Assignee: mrkn (Kenta Murata)
Category: 
Target version: 2.0.0
ruby -v: ruby 1.9.3dev (2011-05-22 trunk 31695) [x86_64-linux]


We have some pure Ruby code which performs a DH (Diffie Hellman) cryptographic 
handshake.

If I upgrade to using the Ruby 1.9.3 interpreter instead of 1.9.2, the unit
tests around the code fail, because the client and server can no longer
compute matching secret keys. I would expect they could agree on matching keys
as the DH algorithm expects. The code worked fine since May 2007 on Ruby 1.8 
and 1.9 until the commit below was introduced.

Using svn-bisect, I was able to find that this commit from ruby-trunk in
between Ruby 1.9.2 (27656) and Ruby 1.9.3 (32500) causes the problem:

r31695 | mrkn | 2011-05-22 08:37:00 -0700 (Sun, 22 May 2011) | 4 lines

* bignum.c (dump_bignum, bigmul1_balance, big_split, biglsh_bang,
  bigrsh_bang, big_split3, bigmul1_toom3, bigmul0): implement Toom3 (Toom-Cook)
  multiplication.
* include/ruby/defines.h: add format prefixes for BDIGIT and BDIGIT_DBL.

Attached to this bug I have a simplified example test case which will pass 
without this commit, and fail with this commit present.

Since this commit covers some relatively complex mathematical algorithms I'd
appreciate some assistance in finding the root cause from the experts on how
bignum.c works. I think the bug is relatively serious because it could cause
inaccurate output for other mathematical code using Bignums since it was
introduced in mid-2011.

This ruby -v comes from ruby trunk SVN at revision 31695, where the failure 
begins to happen. I hand-re-compiled at the bisection points on trunk from
27655 through 32501 to identify the one which caused the problem.

$ ruby -v
ruby 1.9.3dev (2011-05-22 trunk 31695) [x86_64-linux]

C Compiler: gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3

configure params:

./configure \
--with-static-linked-ext \
--prefix=/usr/local/ruby192 \
--enable-shared \
--with-ruby-version=full


-- 
http://bugs.ruby-lang.org/

[ruby-core:48816] [ruby-trunk - Bug #7242] Bignum mathematical accuracy regression in r31695

[mrkn (Kenta Murata)]

Issue #7242 has been updated by mrkn (Kenta Murata).

Category set to core

Although I'm trying to fix it for about two days, I found I need more time to find the direct causes of the bug.
I decide to disable Toom3 method until the bug is fixed.
----------------------------------------
Bug #7242: Bignum mathematical accuracy regression in r31695
https://bugs.ruby-lang.org/issues/7242#change-32305

Author: mhall (Matthew Hall)
Status: Assigned
Priority: Urgent
Assignee: mrkn (Kenta Murata)
Category: core
Target version: 2.0.0
ruby -v: ruby 1.9.3dev (2011-05-22 trunk 31695) [x86_64-linux]


We have some pure Ruby code which performs a DH (Diffie Hellman) cryptographic 
handshake.

If I upgrade to using the Ruby 1.9.3 interpreter instead of 1.9.2, the unit
tests around the code fail, because the client and server can no longer
compute matching secret keys. I would expect they could agree on matching keys
as the DH algorithm expects. The code worked fine since May 2007 on Ruby 1.8 
and 1.9 until the commit below was introduced.

Using svn-bisect, I was able to find that this commit from ruby-trunk in
between Ruby 1.9.2 (27656) and Ruby 1.9.3 (32500) causes the problem:

r31695 | mrkn | 2011-05-22 08:37:00 -0700 (Sun, 22 May 2011) | 4 lines

* bignum.c (dump_bignum, bigmul1_balance, big_split, biglsh_bang,
  bigrsh_bang, big_split3, bigmul1_toom3, bigmul0): implement Toom3 (Toom-Cook)
  multiplication.
* include/ruby/defines.h: add format prefixes for BDIGIT and BDIGIT_DBL.

Attached to this bug I have a simplified example test case which will pass 
without this commit, and fail with this commit present.

Since this commit covers some relatively complex mathematical algorithms I'd
appreciate some assistance in finding the root cause from the experts on how
bignum.c works. I think the bug is relatively serious because it could cause
inaccurate output for other mathematical code using Bignums since it was
introduced in mid-2011.

This ruby -v comes from ruby trunk SVN at revision 31695, where the failure 
begins to happen. I hand-re-compiled at the bisection points on trunk from
27655 through 32501 to identify the one which caused the problem.

$ ruby -v
ruby 1.9.3dev (2011-05-22 trunk 31695) [x86_64-linux]

C Compiler: gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3

configure params:

./configure \
--with-static-linked-ext \
--prefix=/usr/local/ruby192 \
--enable-shared \
--with-ruby-version=full


-- 
http://bugs.ruby-lang.org/

[ruby-core:48957] [ruby-trunk - Bug #7242] Bignum mathematical accuracy regression in r31695

[mhall (Matthew Hall)]

Issue #7242 has been updated by mhall (Matthew Hall).


I am curious, what can I do on my end to disable Toom3 in my own Ruby interpreter?
----------------------------------------
Bug #7242: Bignum mathematical accuracy regression in r31695
https://bugs.ruby-lang.org/issues/7242#change-32461

Author: mhall (Matthew Hall)
Status: Assigned
Priority: Urgent
Assignee: mrkn (Kenta Murata)
Category: core
Target version: 2.0.0
ruby -v: ruby 1.9.3dev (2011-05-22 trunk 31695) [x86_64-linux]


We have some pure Ruby code which performs a DH (Diffie Hellman) cryptographic 
handshake.

If I upgrade to using the Ruby 1.9.3 interpreter instead of 1.9.2, the unit
tests around the code fail, because the client and server can no longer
compute matching secret keys. I would expect they could agree on matching keys
as the DH algorithm expects. The code worked fine since May 2007 on Ruby 1.8 
and 1.9 until the commit below was introduced.

Using svn-bisect, I was able to find that this commit from ruby-trunk in
between Ruby 1.9.2 (27656) and Ruby 1.9.3 (32500) causes the problem:

r31695 | mrkn | 2011-05-22 08:37:00 -0700 (Sun, 22 May 2011) | 4 lines

* bignum.c (dump_bignum, bigmul1_balance, big_split, biglsh_bang,
  bigrsh_bang, big_split3, bigmul1_toom3, bigmul0): implement Toom3 (Toom-Cook)
  multiplication.
* include/ruby/defines.h: add format prefixes for BDIGIT and BDIGIT_DBL.

Attached to this bug I have a simplified example test case which will pass 
without this commit, and fail with this commit present.

Since this commit covers some relatively complex mathematical algorithms I'd
appreciate some assistance in finding the root cause from the experts on how
bignum.c works. I think the bug is relatively serious because it could cause
inaccurate output for other mathematical code using Bignums since it was
introduced in mid-2011.

This ruby -v comes from ruby trunk SVN at revision 31695, where the failure 
begins to happen. I hand-re-compiled at the bisection points on trunk from
27655 through 32501 to identify the one which caused the problem.

$ ruby -v
ruby 1.9.3dev (2011-05-22 trunk 31695) [x86_64-linux]

C Compiler: gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3

configure params:

./configure \
--with-static-linked-ext \
--prefix=/usr/local/ruby192 \
--enable-shared \
--with-ruby-version=full


-- 
http://bugs.ruby-lang.org/

[ruby-core:49020] [ruby-trunk - Bug #7242] Bignum mathematical accuracy regression in r31695

[phasis68 (Heesob Park)]

Issue #7242 has been updated by phasis68 (Heesob Park).


After some inspections, I found the cause of this bug.

One omission of bigtrunc made a different result for the minus Bignum value.

Here is a patch:

diff --git a/bignum.c b/bignum.c.new
index 305a63d..8cf6160 100644
--- a/bignum.c
+++ b/bignum.c.new
@@ -2501,7 +2501,7 @@ bigmul1_toom3(VALUE x, VALUE y)
     z2 = bigtrunc(bigadd(u2, u0, 0));

     /* z3 <- (z2 - z3) / 2 + 2 * z(inf) == (z2 - z3) / 2 + 2 * u4 */
-    z3 = bigadd(z2, z3, 0);
+    z3 = bigtrunc(bigadd(z2, z3, 0));
     bigrsh_bang(BDIGITS(z3), RBIGNUM_LEN(z3), 1);
     t = big_lshift(u4, 1); /* TODO: combining with next addition */
     z3 = bigtrunc(bigadd(z3, t, 1));

----------------------------------------
Bug #7242: Bignum mathematical accuracy regression in r31695
https://bugs.ruby-lang.org/issues/7242#change-32541

Author: mhall (Matthew Hall)
Status: Assigned
Priority: Urgent
Assignee: mrkn (Kenta Murata)
Category: core
Target version: 2.0.0
ruby -v: ruby 1.9.3dev (2011-05-22 trunk 31695) [x86_64-linux]


We have some pure Ruby code which performs a DH (Diffie Hellman) cryptographic 
handshake.

If I upgrade to using the Ruby 1.9.3 interpreter instead of 1.9.2, the unit
tests around the code fail, because the client and server can no longer
compute matching secret keys. I would expect they could agree on matching keys
as the DH algorithm expects. The code worked fine since May 2007 on Ruby 1.8 
and 1.9 until the commit below was introduced.

Using svn-bisect, I was able to find that this commit from ruby-trunk in
between Ruby 1.9.2 (27656) and Ruby 1.9.3 (32500) causes the problem:

r31695 | mrkn | 2011-05-22 08:37:00 -0700 (Sun, 22 May 2011) | 4 lines

* bignum.c (dump_bignum, bigmul1_balance, big_split, biglsh_bang,
  bigrsh_bang, big_split3, bigmul1_toom3, bigmul0): implement Toom3 (Toom-Cook)
  multiplication.
* include/ruby/defines.h: add format prefixes for BDIGIT and BDIGIT_DBL.

Attached to this bug I have a simplified example test case which will pass 
without this commit, and fail with this commit present.

Since this commit covers some relatively complex mathematical algorithms I'd
appreciate some assistance in finding the root cause from the experts on how
bignum.c works. I think the bug is relatively serious because it could cause
inaccurate output for other mathematical code using Bignums since it was
introduced in mid-2011.

This ruby -v comes from ruby trunk SVN at revision 31695, where the failure 
begins to happen. I hand-re-compiled at the bisection points on trunk from
27655 through 32501 to identify the one which caused the problem.

$ ruby -v
ruby 1.9.3dev (2011-05-22 trunk 31695) [x86_64-linux]

C Compiler: gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3

configure params:

./configure \
--with-static-linked-ext \
--prefix=/usr/local/ruby192 \
--enable-shared \
--with-ruby-version=full


-- 
http://bugs.ruby-lang.org/

[ruby-core:49083] [ruby-trunk - Bug #7242] Bignum mathematical accuracy regression in r31695

[mhall (Matthew Hall)]

Issue #7242 has been updated by mhall (Matthew Hall).


This patch appears to fix the issue for me. Could we try it on Bug 6974 to confirm the legitimacy of it?
----------------------------------------
Bug #7242: Bignum mathematical accuracy regression in r31695
https://bugs.ruby-lang.org/issues/7242#change-32610

Author: mhall (Matthew Hall)
Status: Assigned
Priority: Urgent
Assignee: mrkn (Kenta Murata)
Category: core
Target version: 2.0.0
ruby -v: ruby 1.9.3dev (2011-05-22 trunk 31695) [x86_64-linux]


We have some pure Ruby code which performs a DH (Diffie Hellman) cryptographic 
handshake.

If I upgrade to using the Ruby 1.9.3 interpreter instead of 1.9.2, the unit
tests around the code fail, because the client and server can no longer
compute matching secret keys. I would expect they could agree on matching keys
as the DH algorithm expects. The code worked fine since May 2007 on Ruby 1.8 
and 1.9 until the commit below was introduced.

Using svn-bisect, I was able to find that this commit from ruby-trunk in
between Ruby 1.9.2 (27656) and Ruby 1.9.3 (32500) causes the problem:

r31695 | mrkn | 2011-05-22 08:37:00 -0700 (Sun, 22 May 2011) | 4 lines

* bignum.c (dump_bignum, bigmul1_balance, big_split, biglsh_bang,
  bigrsh_bang, big_split3, bigmul1_toom3, bigmul0): implement Toom3 (Toom-Cook)
  multiplication.
* include/ruby/defines.h: add format prefixes for BDIGIT and BDIGIT_DBL.

Attached to this bug I have a simplified example test case which will pass 
without this commit, and fail with this commit present.

Since this commit covers some relatively complex mathematical algorithms I'd
appreciate some assistance in finding the root cause from the experts on how
bignum.c works. I think the bug is relatively serious because it could cause
inaccurate output for other mathematical code using Bignums since it was
introduced in mid-2011.

This ruby -v comes from ruby trunk SVN at revision 31695, where the failure 
begins to happen. I hand-re-compiled at the bisection points on trunk from
27655 through 32501 to identify the one which caused the problem.

$ ruby -v
ruby 1.9.3dev (2011-05-22 trunk 31695) [x86_64-linux]

C Compiler: gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3

configure params:

./configure \
--with-static-linked-ext \
--prefix=/usr/local/ruby192 \
--enable-shared \
--with-ruby-version=full


-- 
http://bugs.ruby-lang.org/

[ruby-core:49097] [ruby-trunk - Bug #7242] Bignum mathematical accuracy regression in r31695

[phasis68 (Heesob Park)]

Issue #7242 has been updated by phasis68 (Heesob Park).


I confirmed this patch also solves Bug 6974.
----------------------------------------
Bug #7242: Bignum mathematical accuracy regression in r31695
https://bugs.ruby-lang.org/issues/7242#change-32629

Author: mhall (Matthew Hall)
Status: Assigned
Priority: Urgent
Assignee: mrkn (Kenta Murata)
Category: core
Target version: 2.0.0
ruby -v: ruby 1.9.3dev (2011-05-22 trunk 31695) [x86_64-linux]


We have some pure Ruby code which performs a DH (Diffie Hellman) cryptographic 
handshake.

If I upgrade to using the Ruby 1.9.3 interpreter instead of 1.9.2, the unit
tests around the code fail, because the client and server can no longer
compute matching secret keys. I would expect they could agree on matching keys
as the DH algorithm expects. The code worked fine since May 2007 on Ruby 1.8 
and 1.9 until the commit below was introduced.

Using svn-bisect, I was able to find that this commit from ruby-trunk in
between Ruby 1.9.2 (27656) and Ruby 1.9.3 (32500) causes the problem:

r31695 | mrkn | 2011-05-22 08:37:00 -0700 (Sun, 22 May 2011) | 4 lines

* bignum.c (dump_bignum, bigmul1_balance, big_split, biglsh_bang,
  bigrsh_bang, big_split3, bigmul1_toom3, bigmul0): implement Toom3 (Toom-Cook)
  multiplication.
* include/ruby/defines.h: add format prefixes for BDIGIT and BDIGIT_DBL.

Attached to this bug I have a simplified example test case which will pass 
without this commit, and fail with this commit present.

Since this commit covers some relatively complex mathematical algorithms I'd
appreciate some assistance in finding the root cause from the experts on how
bignum.c works. I think the bug is relatively serious because it could cause
inaccurate output for other mathematical code using Bignums since it was
introduced in mid-2011.

This ruby -v comes from ruby trunk SVN at revision 31695, where the failure 
begins to happen. I hand-re-compiled at the bisection points on trunk from
27655 through 32501 to identify the one which caused the problem.

$ ruby -v
ruby 1.9.3dev (2011-05-22 trunk 31695) [x86_64-linux]

C Compiler: gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3

configure params:

./configure \
--with-static-linked-ext \
--prefix=/usr/local/ruby192 \
--enable-shared \
--with-ruby-version=full


-- 
http://bugs.ruby-lang.org/

[ruby-core:49099] [ruby-trunk - Bug #7242] Bignum mathematical accuracy regression in r31695

[mame (Yusuke Endoh)]

Issue #7242 has been updated by mame (Yusuke Endoh).


Awesome, thank you!  Mrkn, could you review phasis68's patch?

BTW: I think that he should have a commit bit.

-- 
Yusuke Endoh <mame@tsg.ne.jp>
----------------------------------------
Bug #7242: Bignum mathematical accuracy regression in r31695
https://bugs.ruby-lang.org/issues/7242#change-32631

Author: mhall (Matthew Hall)
Status: Assigned
Priority: Urgent
Assignee: mrkn (Kenta Murata)
Category: core
Target version: 2.0.0
ruby -v: ruby 1.9.3dev (2011-05-22 trunk 31695) [x86_64-linux]


We have some pure Ruby code which performs a DH (Diffie Hellman) cryptographic 
handshake.

If I upgrade to using the Ruby 1.9.3 interpreter instead of 1.9.2, the unit
tests around the code fail, because the client and server can no longer
compute matching secret keys. I would expect they could agree on matching keys
as the DH algorithm expects. The code worked fine since May 2007 on Ruby 1.8 
and 1.9 until the commit below was introduced.

Using svn-bisect, I was able to find that this commit from ruby-trunk in
between Ruby 1.9.2 (27656) and Ruby 1.9.3 (32500) causes the problem:

r31695 | mrkn | 2011-05-22 08:37:00 -0700 (Sun, 22 May 2011) | 4 lines

* bignum.c (dump_bignum, bigmul1_balance, big_split, biglsh_bang,
  bigrsh_bang, big_split3, bigmul1_toom3, bigmul0): implement Toom3 (Toom-Cook)
  multiplication.
* include/ruby/defines.h: add format prefixes for BDIGIT and BDIGIT_DBL.

Attached to this bug I have a simplified example test case which will pass 
without this commit, and fail with this commit present.

Since this commit covers some relatively complex mathematical algorithms I'd
appreciate some assistance in finding the root cause from the experts on how
bignum.c works. I think the bug is relatively serious because it could cause
inaccurate output for other mathematical code using Bignums since it was
introduced in mid-2011.

This ruby -v comes from ruby trunk SVN at revision 31695, where the failure 
begins to happen. I hand-re-compiled at the bisection points on trunk from
27655 through 32501 to identify the one which caused the problem.

$ ruby -v
ruby 1.9.3dev (2011-05-22 trunk 31695) [x86_64-linux]

C Compiler: gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3

configure params:

./configure \
--with-static-linked-ext \
--prefix=/usr/local/ruby192 \
--enable-shared \
--with-ruby-version=full


-- 
http://bugs.ruby-lang.org/

[ruby-core:49120] [ruby-trunk - Bug #7242][Open] Bignum mathematical accuracy regression in r31695

[mrkn (Kenta Murata)]

Issue #7242 has been updated by mrkn (Kenta Murata).

Status changed from Closed to Open
Priority changed from Urgent to High

reopen because the bug of bigmul1_toom3 hasn't fixed yet.
----------------------------------------
Bug #7242: Bignum mathematical accuracy regression in r31695
https://bugs.ruby-lang.org/issues/7242#change-32652

Author: mhall (Matthew Hall)
Status: Open
Priority: High
Assignee: mrkn (Kenta Murata)
Category: core
Target version: 2.0.0
ruby -v: ruby 1.9.3dev (2011-05-22 trunk 31695) [x86_64-linux]


We have some pure Ruby code which performs a DH (Diffie Hellman) cryptographic 
handshake.

If I upgrade to using the Ruby 1.9.3 interpreter instead of 1.9.2, the unit
tests around the code fail, because the client and server can no longer
compute matching secret keys. I would expect they could agree on matching keys
as the DH algorithm expects. The code worked fine since May 2007 on Ruby 1.8 
and 1.9 until the commit below was introduced.

Using svn-bisect, I was able to find that this commit from ruby-trunk in
between Ruby 1.9.2 (27656) and Ruby 1.9.3 (32500) causes the problem:

r31695 | mrkn | 2011-05-22 08:37:00 -0700 (Sun, 22 May 2011) | 4 lines

* bignum.c (dump_bignum, bigmul1_balance, big_split, biglsh_bang,
  bigrsh_bang, big_split3, bigmul1_toom3, bigmul0): implement Toom3 (Toom-Cook)
  multiplication.
* include/ruby/defines.h: add format prefixes for BDIGIT and BDIGIT_DBL.

Attached to this bug I have a simplified example test case which will pass 
without this commit, and fail with this commit present.

Since this commit covers some relatively complex mathematical algorithms I'd
appreciate some assistance in finding the root cause from the experts on how
bignum.c works. I think the bug is relatively serious because it could cause
inaccurate output for other mathematical code using Bignums since it was
introduced in mid-2011.

This ruby -v comes from ruby trunk SVN at revision 31695, where the failure 
begins to happen. I hand-re-compiled at the bisection points on trunk from
27655 through 32501 to identify the one which caused the problem.

$ ruby -v
ruby 1.9.3dev (2011-05-22 trunk 31695) [x86_64-linux]

C Compiler: gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3

configure params:

./configure \
--with-static-linked-ext \
--prefix=/usr/local/ruby192 \
--enable-shared \
--with-ruby-version=full


-- 
http://bugs.ruby-lang.org/

[ruby-core:49121] [ruby-trunk - Bug #7242] Bignum mathematical accuracy regression in r31695

[mrkn (Kenta Murata)]

Issue #7242 has been updated by mrkn (Kenta Murata).


Thank you for your contribution, Matthew and Heesob.
I will confirm your patch and apply it asap.

----------------------------------------
Bug #7242: Bignum mathematical accuracy regression in r31695
https://bugs.ruby-lang.org/issues/7242#change-32653

Author: mhall (Matthew Hall)
Status: Open
Priority: High
Assignee: mrkn (Kenta Murata)
Category: core
Target version: 2.0.0
ruby -v: ruby 1.9.3dev (2011-05-22 trunk 31695) [x86_64-linux]


We have some pure Ruby code which performs a DH (Diffie Hellman) cryptographic 
handshake.

If I upgrade to using the Ruby 1.9.3 interpreter instead of 1.9.2, the unit
tests around the code fail, because the client and server can no longer
compute matching secret keys. I would expect they could agree on matching keys
as the DH algorithm expects. The code worked fine since May 2007 on Ruby 1.8 
and 1.9 until the commit below was introduced.

Using svn-bisect, I was able to find that this commit from ruby-trunk in
between Ruby 1.9.2 (27656) and Ruby 1.9.3 (32500) causes the problem:

r31695 | mrkn | 2011-05-22 08:37:00 -0700 (Sun, 22 May 2011) | 4 lines

* bignum.c (dump_bignum, bigmul1_balance, big_split, biglsh_bang,
  bigrsh_bang, big_split3, bigmul1_toom3, bigmul0): implement Toom3 (Toom-Cook)
  multiplication.
* include/ruby/defines.h: add format prefixes for BDIGIT and BDIGIT_DBL.

Attached to this bug I have a simplified example test case which will pass 
without this commit, and fail with this commit present.

Since this commit covers some relatively complex mathematical algorithms I'd
appreciate some assistance in finding the root cause from the experts on how
bignum.c works. I think the bug is relatively serious because it could cause
inaccurate output for other mathematical code using Bignums since it was
introduced in mid-2011.

This ruby -v comes from ruby trunk SVN at revision 31695, where the failure 
begins to happen. I hand-re-compiled at the bisection points on trunk from
27655 through 32501 to identify the one which caused the problem.

$ ruby -v
ruby 1.9.3dev (2011-05-22 trunk 31695) [x86_64-linux]

C Compiler: gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3

configure params:

./configure \
--with-static-linked-ext \
--prefix=/usr/local/ruby192 \
--enable-shared \
--with-ruby-version=full


-- 
http://bugs.ruby-lang.org/

[ruby-core:49122] [ruby-trunk - Bug #7242] Bignum mathematical accuracy regression in r31695

[mrkn (Kenta Murata)]

Issue #7242 has been updated by mrkn (Kenta Murata).


Wrote by Yusuke Endoh:
> BTW: I think that he should have a commit bit.

I think so too.
He can confirm the calculation algorithms for large Bignum than me.

----------------------------------------
Bug #7242: Bignum mathematical accuracy regression in r31695
https://bugs.ruby-lang.org/issues/7242#change-32656

Author: mhall (Matthew Hall)
Status: Closed
Priority: High
Assignee: mrkn (Kenta Murata)
Category: core
Target version: 2.0.0
ruby -v: ruby 1.9.3dev (2011-05-22 trunk 31695) [x86_64-linux]


We have some pure Ruby code which performs a DH (Diffie Hellman) cryptographic 
handshake.

If I upgrade to using the Ruby 1.9.3 interpreter instead of 1.9.2, the unit
tests around the code fail, because the client and server can no longer
compute matching secret keys. I would expect they could agree on matching keys
as the DH algorithm expects. The code worked fine since May 2007 on Ruby 1.8 
and 1.9 until the commit below was introduced.

Using svn-bisect, I was able to find that this commit from ruby-trunk in
between Ruby 1.9.2 (27656) and Ruby 1.9.3 (32500) causes the problem:

r31695 | mrkn | 2011-05-22 08:37:00 -0700 (Sun, 22 May 2011) | 4 lines

* bignum.c (dump_bignum, bigmul1_balance, big_split, biglsh_bang,
  bigrsh_bang, big_split3, bigmul1_toom3, bigmul0): implement Toom3 (Toom-Cook)
  multiplication.
* include/ruby/defines.h: add format prefixes for BDIGIT and BDIGIT_DBL.

Attached to this bug I have a simplified example test case which will pass 
without this commit, and fail with this commit present.

Since this commit covers some relatively complex mathematical algorithms I'd
appreciate some assistance in finding the root cause from the experts on how
bignum.c works. I think the bug is relatively serious because it could cause
inaccurate output for other mathematical code using Bignums since it was
introduced in mid-2011.

This ruby -v comes from ruby trunk SVN at revision 31695, where the failure 
begins to happen. I hand-re-compiled at the bisection points on trunk from
27655 through 32501 to identify the one which caused the problem.

$ ruby -v
ruby 1.9.3dev (2011-05-22 trunk 31695) [x86_64-linux]

C Compiler: gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3

configure params:

./configure \
--with-static-linked-ext \
--prefix=/usr/local/ruby192 \
--enable-shared \
--with-ruby-version=full


-- 
http://bugs.ruby-lang.org/