Go Back  Xtreme Visual Basic Talk > Legacy Visual Basic (VB 4/5/6) > General > Mod function in vb6


Reply
 
Thread Tools Display Modes
  #1  
Old 05-01-2008, 10:46 AM
Geoff Coulson Geoff Coulson is offline
Newcomer
 
Join Date: May 2006
Posts: 3
Post 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
Reply With Quote
  #2  
Old 05-01-2008, 11:49 AM
Rockoon's Avatar
Rockoon Rockoon is offline
Joseph Koss

* Guru *
 
Join Date: Aug 2003
Location: Unfashionable End
Posts: 3,615
Default

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)
Reply With Quote
  #3  
Old 05-01-2008, 11:59 AM
Roger_Wgnr's Avatar
Roger_Wgnr Roger_Wgnr is offline
CodeASaurus Hex

Forum Leader
* Expert *
 
Join Date: Jul 2006
Location: San Antonio TX
Posts: 2,427
Default

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
Reply With Quote
  #4  
Old 05-01-2008, 12:12 PM
Rockoon's Avatar
Rockoon Rockoon is offline
Joseph Koss

* Guru *
 
Join Date: Aug 2003
Location: Unfashionable End
Posts: 3,615
Default

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)
Reply With Quote
  #5  
Old 05-01-2008, 12:35 PM
Rockoon's Avatar
Rockoon Rockoon is offline
Joseph Koss

* Guru *
 
Join Date: Aug 2003
Location: Unfashionable End
Posts: 3,615
Default

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
Reply With Quote
  #6  
Old 05-01-2008, 12:54 PM
darkforcesjedi's Avatar
darkforcesjedi darkforcesjedi is offline
Trust me, I'm an

* Expert *
 
Join Date: Apr 2001
Location: In ur base, pwnin d00dz
Posts: 1,964
Default

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.
Reply With Quote
  #7  
Old 05-02-2008, 06:09 AM
Geoff Coulson Geoff Coulson is offline
Newcomer
 
Join Date: May 2006
Posts: 3
Default

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
Reply With Quote
  #8  
Old 05-02-2008, 06:32 AM
mkaras's Avatar
mkaras mkaras is offline
Ultimate Contributor

Retired Leader
* Expert *
 
Join Date: Mar 2004
Location: Beaverton, OR
Posts: 1,874
Default

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.
Reply With Quote
  #9  
Old 05-02-2008, 07:08 AM
darkforcesjedi's Avatar
darkforcesjedi darkforcesjedi is offline
Trust me, I'm an

* Expert *
 
Join Date: Apr 2001
Location: In ur base, pwnin d00dz
Posts: 1,964
Default

Quote:
Originally Posted by Geoff Coulson View Post
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
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.
Reply With Quote
  #10  
Old 03-20-2009, 10:47 PM
Alan1ar1s Alan1ar1s is offline
Freshman
 
Join Date: Mar 2009
Posts: 29
Default

Quote:
Originally Posted by darkforcesjedi View Post

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 10:54 PM.
Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off

Forum Jump

Advertisement:





Free Publications
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
Programmers Heaven C# School Book -Free 338 Page eBook
The Programmers Heaven C# School book covers the .NET framework and the C# language.
subscribe
Build Your Own ASP.NET 3.5 Web Site Using C# & VB, 3rd Edition - Free 219 Page Preview!
This comprehensive step-by-step guide will help get your database-driven ASP.NET web site up and running in no time..
subscribe
 
 
-->