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

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

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)

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

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 01:00 PM.

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.

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.

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

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.

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.

The ASP.NET 2.0 Anthology
101 Essential Tips, Tricks & Hacks - Free 156 Page Preview. Learn the most practical features and best approaches for ASP.NET. subscribe