Mod function in vb6 - Xtreme Visual Basic Talk

05-01-2008, 09:46 AM

Geoff Coulson Geoff Coulson is offline

Newcomer

Join Date: May 2006

Posts: 3

Mod function in vb6

Hi, Everybody,
The following code produces an overflow error:-

Print 30 ^ 19 Mod 391

I have managed to get the correct answer (310) by using:-

ans = 1
For i = 1 To 19
ans = (ans * 30) - 391 * Int((ans * 30) / 391)
Next i
Print ans

My two questions are:-
1). Is there a simpler way to do it?
2).Why can't vb's built-in mod function handle these numbers?
(The one in Liberty BASIC can).
I would appreciate any comments.
Thank you, Geoff

05-01-2008, 10:49 AM

Rockoon

Joseph Koss

* Guru *

Join Date: Aug 2003

Location: Unfashionable End

Posts: 3,615

I'm suspect that LibertyBasic is giving you erroneous answers.

Lets perform an experiment (you will have to do it because I do not have liberty basic)

Print (30 ^ 19 + 0) Mod 391
Print (30 ^ 19 + 1) Mod 391
Print (30 ^ 19 + 2) Mod 391

What are the outputs here?

(each value _should_ be one larger than the previous)

05-01-2008, 10:59 AM

Roger_Wgnr Roger_Wgnr is offline

CodeASaurus Hex

Forum Leader
* Expert *

Join Date: Jul 2006

Location: San Antonio TX

Posts: 2,427

I am not sure about the first question (my math is a bit rusty)
But I think I may understand the reason for the second one.
from the MSDN

Quote:

Usually, the data type of result is a Byte, Byte variant, Integer, Integer variant, Long, or Variant containing a Long, regardless of whether or not result is a whole number.

Notice that the the largest data type is a long. I may be incorrect in this but I also have Liberty Basic and while returns in VB6 ar generally a Long in Liberty they are a Double allowing for larger numeric values. the overflow you are getting I believe is in the 30 ^ 19 portion of the calculation.

I have not tried it (I am not sure if MOD will accept a double but you might try something like this

Code:

Dim InputNumber As Double
InputNumber = 30 ^ 19
Print InputNumber Mod 391

__________________
Code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live. ~Martin Golding
The user is a peripheral that types when you issue a read request. ~Peter Williams
MSDN Visual Basic .NET General FAQ

05-01-2008, 11:12 AM

Rockoon

Joseph Koss

* Guru *

Join Date: Aug 2003

Location: Unfashionable End

Posts: 3,615

The 30^19 part does not throw an overflow in VB6's immediate window.

Mod indeed is limited to a lefthand 32-bit Integer in VB6 (as well as most languages.) One of the issues here is that there is no hardware support for performing Mod on non-integer values, which is what the lefthand side of his expression evaluates to.

(Note: the lefthand side of his expression would require a 94 bit integer.. I suspect that Liberty Basic has hid the truth from him by not raising an error and simply doing "the best it can" which would have all 3 of my print statements returning the exact same value)

05-01-2008, 11:35 AM

Rockoon

Joseph Koss

* Guru *

Join Date: Aug 2003

Location: Unfashionable End

Posts: 3,615

I just cooked up this function, which agrees with Google for small values, but will still fail on a lefthand 30^19 because that number simply cannot be accurately represented in a Double.

Code:

Public Function Remainder(numerator As Double, denominator As Double) As Double
  ' Return the remainder of Numerator / Denominator
  Dim x As Double
  
  x = (numerator / denominator)
  x = x - Int(x)
  
  Remainder = x * denominator
  
End Function

05-01-2008, 11:54 AM

darkforcesjedi

Trust me, I'm an

* Expert *

Join Date: Apr 2001

Location: In ur base, pwnin d00dz

Posts: 1,961

30^19 is computed as a double in the immediate pane. He's doing modular exponentiation all wrong in the "workaround" anyway:

Code:

Public Function ModExp(base As Long, exponent As Long, modulus As Long)

    Dim product As Long
    Dim result As Long
    Dim power As Long
    
    power = 1
    product = base
    
    product = product Mod modulus

    result = IIf(exponent And power, product, 1)
    
    While power < exponent
        power = power * 2
        product = (product * product) Mod modulus
        If (exponent And power) Then result = (result * product) Mod modulus
    Wend
    
    ModExp = result
End Function

The above code requires 5 loop iterations instead of the 19 in the code posted earlier. The above may still generate an overflow depending on the value of the modulus and the base. You can add an On Error Resume Next, then compute `power*power Mod modulus` using doubles and converting back if that line raises an error.

Correctly computes 3^200000 mod 4 = 1 and 3^200001 mod 4 = 3, and you won't get an answer for 3^200000 from vb using any datatype.

__________________
To err is human; to debug, divine.

Last edited by darkforcesjedi; 05-01-2008 at 12:00 PM.

05-02-2008, 05:09 AM

Geoff Coulson Geoff Coulson is offline

Newcomer

Join Date: May 2006

Posts: 3

Thank you everyone for the help.

I have applied Rockoon's test of the accuracy of Liberty Basic. It passed.

Thank you darkforcesjedi. I shall enjoy studying your ModExp function (I have not come across IIf() before).
I was pleased to see that, using my current parameters, my own amateurish "workaround" produces the same result as your function.

For anyone who is wondering why I'm using such large exponents, I'm playing around with RSA cryptography.

Thanks again, Geoff

05-02-2008, 05:32 AM

mkaras

Ultimate Contributor

Retired Leader
* Expert *

Join Date: Mar 2004

Location: Beaverton, OR

Posts: 1,874

The mathematical description of various algorithms including cryptography may use numerical expressions like (30 ^ 19 Mod 391) but I can assure you that realized implementations of such algorithms do not compute with expressions of this type. Any type of real time communications system that uses a cryptography would never be able to keep up encrypting and decrypting the messages if it computed with numbers expressed in this manner.

05-02-2008, 06:08 AM

darkforcesjedi

Trust me, I'm an

* Expert *

Join Date: Apr 2001

Location: In ur base, pwnin d00dz

Posts: 1,961

Quote:

Originally Posted by Geoff Coulson

I figured that's what you were doing. I've posted examples of 32-bit and arbitrary precision RSA on these forums before. Some things you should take into account:

1. You never need to compute x^n. Imagine if x and n were 1024 bits, the result would be enormous and take an eternity to compute.
2. Any book that explains RSA will also give you the above exponentiation algorithm. x^19=x*x*x*x....=(x^16)*(x^2)*x=((((x^2)^2)^2)^2)*(x^2)*x. By repeatedly squaring x you can compute the result in log N time instead of N.

There's an error in the arbitrary precision code I posted (if you find it). All Carmichael numbers with smallest factors greater than 256 will pass the primality test, which may make it difficult to find an inverse given that the number is not prime. If it does find an inverse and you try to encrypt data that shares a common factor with the carmichael number, you won't necessarily get the original data when decrypting.

__________________
To err is human; to debug, divine.

#10

03-20-2009, 09:47 PM

Alan1ar1s

Freshman

Join Date: Mar 2009

Posts: 29

Quote:

Originally Posted by darkforcesjedi

Code:

Public Function ModExp(base As Long, exponent As Long, modulus As Long)

    Dim product As Long
    Dim result As Long
    Dim power As Long
    
    power = 1
    product = base
    
    product = product Mod modulus

    result = IIf(exponent And power, product, 1)
    
    While power < exponent
        power = power * 2
        product = (product * product) Mod modulus
        If (exponent And power) Then result = (result * product) Mod modulus
    Wend
    
    ModExp = result
End Function

Hello guys
I am trying to use the modular exponentiation in a program I am writing in VB6 about RSA, too.
I've tried to use all the piece of codes mentioned in this thread. In the above mentioned code I am having an Overflow message on the highlight sentence.

Quote:

Public Function Remainder(numerator As Double, denominator As Double) As Double
' Return the remainder of Numerator / Denominator
Dim x As Double

x = (numerator / denominator)
x = x - Int(x)

Remainder = x * denominator

End Function

Also in this piece of code posted by Rockoon, I did not understand what has to be entered in order to work the algorithm.

Please give me your lights.

Thanks

Last edited by Alan1ar1s; 03-20-2009 at 09:54 PM.