# What's wrong in this code ?

• Mar 19th 2010, 03:37 AM
Bacterius
What's wrong in this code ?
Hey all,
I've been trying to figure out for a whole evening what was wrong in the code I wrote to apply the extended euclidean algorithm on two coprime numbers in order to obtain the multiplicative inverse of \$\displaystyle a\$ modulo \$\displaystyle b\$. This is what I get (this is delphi, longword is the basic unsigned 32-bit integer) :

Code:

```function ModularInverse(a, b: Longword): Longword; Var  X, Y, lastX, lastY, temp, quotient: Longword; begin  X := 0;  Y := 1;  Lastx := 1;  Lasty := 0;  while b <> 0 do   begin   Quotient := A div B;   Temp := B;   B := A mod B;   A := Temp;   Temp := X;   X := Lastx - quotient * X;   Lastx := temp;   temp := y;   y := lasty - quotient * y;   lasty := temp;   end;  Result := X; end;```
But this code keeps failing on even basic inputs like the inverse of 15 modulo 19 ! The answer should be 14 but it just keeps answering either 4, either 10 or sometimes 19 or 0. What the hell is wrong with this ? This is really melting my brain down. I really feel like my computer can't add two numbers right ...

Thanks all :)
• Mar 19th 2010, 03:57 AM
CaptainBlack
Quote:

Originally Posted by Bacterius
Hey all,
I've been trying to figure out for a whole evening what was wrong in the code I wrote to apply the extended euclidean algorithm on two coprime numbers in order to obtain the multiplicative inverse of \$\displaystyle a\$ modulo \$\displaystyle b\$. This is what I get (this is delphi, longword is the basic unsigned 32-bit integer) :

Code:

```function ModularInverse(a, b: Longword): Longword; Var  X, Y, lastX, lastY, temp, quotient: Longword; begin  X := 0;  Y := 1;  Lastx := 1;  Lasty := 0;  while b <> 0 do   begin   Quotient := A div B;   Temp := B;   B := A mod B;   A := Temp;   Temp := X;   X := Lastx - quotient * X;   Lastx := temp;   temp := y;   y := lasty - quotient * y;   lasty := temp;   end;  Result := X; end;```
But this code keeps failing on even basic inputs like the inverse of 15 modulo 19 ! The answer should be 14 but it just keeps answering either 4, either 10 or sometimes 19 or 0. What the hell is wrong with this ? This is really melting my brain down. I really feel like my computer can't add two numbers right ...

Thanks all :)

Case sensitive?

CB
• Mar 19th 2010, 04:00 AM
Bacterius
Quote:

Originally Posted by CaptainBlack
Case sensitive?

CB

Hi Captain Black,
Delphi is not case-sensitive :/