[Mono-bugs] [Bug 760434] New: BigInteger.Parse("1").ModInverse incorrectly throws ArithmeticException if modulus >0xFFFFFFFF

[bugzilla_noreply at novell.com]

https://bugzilla.novell.com/show_bug.cgi?id=760434

https://bugzilla.novell.com/show_bug.cgi?id=760434#c0


           Summary: BigInteger.Parse("1").ModInverse incorrectly throws
                    ArithmeticException if modulus >0xFFFFFFFF
    Classification: Mono
           Product: Mono: Class Libraries
           Version: 2.8.x
          Platform: 32bit
        OS/Version: Windows 7
            Status: NEW
          Severity: Major
          Priority: P5 - None
         Component: Mono.Security
        AssignedTo: frego at suse.com
        ReportedBy: andyrosa at digitalforces.com
         QAContact: mono-bugs at lists.ximian.com
          Found By: ---
           Blocker: ---


User-Agent:       Mozilla/5.0 (Windows NT 6.1) AppleWebKit/535.19 (KHTML, like
Gecko) Chrome/18.0.1025.168 Safari/535.19

i=ModInverse(x,p) is supposed to return i such that i*x (modulus p) is 1.
For i to exist, x and p have to be co-prime. Ie: gcd(x,p)=1.
In particular, ModInverse(1,p)=1 for all values of p>1.

In mono, the function BigInteger.ModInverse works for x=1 as long as
p<=0xFFFFFFFF.  For larger p's, it incorrectly throws ArithmeticException ("No
inverse!")




Reproducible: Always

Steps to Reproduce:
Open MonoDevelop on Windows 7/32, add a reference to Mono.Security.  Paste and
run this code:

using System;
using Mono.Math;//needs Mono.Security reference
namespace ModInverse
{
    class MainClass
    {
        public static void Main (string[] args)
        {
            Console.WriteLine
(BigInteger.Parse("1").ModInverse(BigInteger.Parse("4294967296")));
        }
    }
}

Actual Results:  
Unhandled Exception: System.ArithmeticException: No inverse!
  at Mono.Math.BigInteger+Kernel.modInverse (Mono.Math.BigInteger bi,
Mono.Math.
BigInteger modulus) [0x00106] in
C:\cygwin\tmp\monobuild\build\BUILD\mono-2.10.8
\mcs\class\Mono.Security\Mono.Math\BigInteger.cs:2364
  at Mono.Math.BigInteger.ModInverse (Mono.Math.BigInteger modulus) [0x00000]
in

C:\cygwin\tmp\monobuild\build\BUILD\mono-2.10.8\mcs\class\Mono.Security\Mono.Ma
th\BigInteger.cs:888

Expected Results:  
1


The error does not ocurr for p between 0 and 2^32-1.  The error does not seem
to ocurr for x!=1.

Here is a little more info on modInverse:

http://docs.oracle.com/javase/1.4.2/docs/api/java/math/BigInteger.html#modInverse(java.math.BigInteger)

-- 
Configure bugmail: https://bugzilla.novell.com/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the QA contact for the bug.