llModPow()

Anyone know what this does, it's in 1.6.2... /3/54/42679/1.html

It takes 3 integers a,b, and c. It returna a raised to the power of b, modulo c. Or: (a**b) % c.

Then it delays the script for 1 second.

(EDIT: Legith explains nicely why this is a useful library call)

most likely:

output = pow(input,some power) % some modulus.

but presumably using a more efficient algorithm.

if it has big integer support this allows for RSA encryption.

if not is still makes RSA of small keys easy.. but not strong encryption.

still rsa with smaller primes (ie 17+bit primes, allowing the transfer of 16 bit numbers) would be useful is some tasks. but I wouldn't have US$ or even large amounts of L$ dependent on any RSA encryption with primes < 1024 bits.

I have been waiting for just that type of function

Thank you all, both for the succinct explantion of what it does, and why it's useful.

Uh, we got llModPow so we could do RSA in LSL?
Why should anyone want to reinvent the wheel like that?
You either add full RSA support to LSL or you dont. This is just ridiculous.

A long long is only 64 bits if I recall, and I think an integer is 32 in LSL, so unless it's going to take a string for that argument...

Now if you've got 32 ints and some way to read the carry flag, you could use some bit shifting to maybe get the same effect...

Well RSA is basicly modpow

to encrypt:
C = (T^E) mod n
to decrypt:
T = (C^D) mod n

where C = crypt, T = plain, n is the product of primes, and E is the private part, and D is the public part.

private key has all values
public key contains n and D

all you are missing is a key generator.

But what you really want is something that can encrypt a string, not very very basic RSA (since all RSA in particular with small prime numbers) only gives you a complex substitution encryption. The reason it works is with large primes it is hard to computer the reverse substitution, and impossible to form the table when the table has 2^160 possible elements in the case of a SHA1 signed/encrypted with RSA. (and in reality there is normally some type of random number added in.)

(note input values to RSA of 0, and >= the smallest prime factor of n will not encrypt well)

On a side note... I'm quite sure I can implement a proper modpow function in LSL and have it run in well under a second on what this function accepts.. why is there a 1 second delay.. this is a very simple calculation for small numbers.

So let me get this straight... the only difference between using llModPow() and using llPow() and a little casting and a modulo is that llModPow() can presumably deal properly with intermediate values that overflow an integer? And this makes it possible to do RSA in SL? Is anyone actually going to make use of this? RSA already runs slowly in languages like C. Now someone's going to try to use this function for this very narrow purpose, and implement a likely stunted form of RSA in LSL? I'm sur ewe're not going to see large prime generation in LSL...

about right except this function wont even deal with large primes if you wanted it to. I don't think RSA in SL whuld be that bad to initiate communication that HAD to be secure.. But I can't say I've implemented RSA in SL.. or for that matter had time to log in since the update.

Well my conclusion is that their function dose work a little better than mine under some useful conditions.

I can't have both a, and c in my function allow full 32bit values, though I can get b to accept them.

However since when I limit functionality to 16bit values for a and c I can run is 0.4 seconds in LSL... I still fail to see why we have I'm stalled a full second, since in c the library calls for 'long long' must be notably faster than their lsl interpreter. (and if I had an unsigned long long type my code would accept 32bit values..

// int notllModPow(a, b, c);
// returns (a**b)%c
integer notllModPow(integer a,integer b,integer c){
    integer r;
    integer i;
    for(i=30;i>=0;i--){
        r = ((r%c)*(r%c))% c;     // (r**2) %c
        if(b & (1 << i)){         // if i'th bit of b is set
            r = ((r%c)*(a%c))% c; // (r*a) %c
        }
    }
    return r;
}

This call will work with any values so long as a, and b are positive, and c is <65536

This is a textbook example of how to calculate ModPow for large integer values.. and is designed to run in O(n) where n is the number of bits of b, in the above example I assume b has 31 bits, (since we have signed 32 bit integers this will be all positive values)

The implementation of 'llModPow()' seems to be broken (now) anyway. I just filed a Bug Report.

Java test program:

import java.math.BigInteger;

class ModPowTestCase
{
   public static void main(String[] args)
   {
      test1();
      System.out.println();
      test2();
   }

   static void test1()
   {
      BigInteger a = new BigInteger("909312256");
      BigInteger b = new BigInteger("2");
      BigInteger c = new BigInteger("451963904");

      BigInteger result = a.modPow(b, c);

      System.out.println(a.toString()+".modPow("+b+", "+c+") = "+result);
   }

   static void test2()
   {
      long n = 909312256;
      long m = 451963904;

      long result = (n*n)%m;

      System.out.println("("+n+" * "+n+") % "+m+" = "+result);
   }
}

I feel llModPow is still broken... So, I wrote ModPow in C and LSL.
In my LSL code, there are some rules for a, b and c.
1) 0 <= a < c
2) 0 < b <= 0xFFFF
3) 0 < c <= 0x7FFFFFFF

// *********C code********** //
// a = iIn, b = iPow, c = iMod
unsigned __int32 _iModPow(unsigned __int32 iIn, unsigned __int16 iPow, unsigned __int32 iMod)
{
unsigned __int16 i = 0;
unsigned __int32 j = 0;
unsigned __int32 iOut = 0;
unsigned __int32 iOutTmpBuf = 0;
iOut = iIn;
for (i = 0; i < (iPow - 1); i++)
{
iOut %= iMod;
iOut *= iIn; // this may cause overflow // just for small iIn and iOut
/*
// alternation of iOut *= iIn; start // very slow... //
iOutTmpBuf = iOut;
iOut = 0;
for (j = 0; j < iIn; j++) // this loop is very slow
{
iOut += iOutTmpBuf;
iOut %= iMod;
}
// alternation of iOut *= iIn; end //
*/
}
iOut %= iMod;
// printf("i = %i\tiOut:%u\t(%8X)\n", i, iOut, iOut);
return iOut;
}

// ********LSL********* //
integer _iModPow(integer a, integer b, integer c)
// a = iIn, b = iPow, c = iMod
{
integer iErrFlag = FALSE; // TRUE: error FALSE: non-error
integer iUseAltFlag = FALSE; // TRUE: use alternation FALSE: use faster one
integer i = 0;
integer j = 0;
integer iOut = 0;
integer iTmpOutBuf = 0;
// size check start //
if (0 > b)
{
llOwnerSay("Pow by minus value!");
iOut = 0;
iErrFlag = TRUE;
}
else if (0xFFFF < b)
{
llOwnerSay("Key too large!");
iOut = 0;
iErrFlag = TRUE;
}
else if (0 == c)
{
llOwnerSay("mod by 0");
iOut = 0;
iErrFlag = TRUE;
}
else if (0 < c)
{
if (a >= c)
{
llOwnerSay("Input too large! (larger than mod)");
iOut = 0;
iErrFlag = TRUE;
}
}
else
{ // if c is minus value // (a <= 0x0000 FFFF, c >= 0x8000 0000) => (a < c)
llOwnerSay("Mod by minus value!");
iOut = 0;
iErrFlag = TRUE;
}
// size check end //
if (!(iErrFlag))
{
iOut = a;
for (i = 0; i < (b - 1); i++) // this maybe a long loop
{
iOut %= c;
if (!(iUseAltFlag))
{
iOut *= a; // this may cause overflow // use this if a and iOut is small enough
}
else
{ // alternation start // alt is very slow !!
iTmpOutBuf = iOut;
iOut = 0;
for (j = 0; j < a; j++) // this loop is very slow
{
iOut += iTmpOutBuf;
iOut %= c;
}
// alternation end //
}
}
iOut %= c;
}
return iOut;
}

Well, you're 3 years too late. That function was added in April of 05.

heehee. And he made that comment 04-14-2005, 03:25 AM

But TY anyways Johan, we needed a touch of levity that this little mistake brought to the forum today!!!