Don't click here unless you want to be banned.

## LSL Wiki : llModPow

HomePage :: PageIndex :: RecentChanges :: RecentlyCommented :: UserSettings :: You are crawl338.us.archive.org
integer llModPow(integer a, integer b, integer c)

Returns a raised to the b power, mod c. ( (a ^ b)%c ). b is capped at 0xFFFF (16 bits).

Note: This function delays the script for 1 second.

Q: So what is this actually useful for?
A: Weak RSA encryption--see the discussion in the Second Life Scripting Forum.

Hewee Zetkin wrote the 31 bit implementation of ModPow:

```// NOTE
// ----
// All funcitons beginning with the 'u_' prefix assume their arguments are
// non-negative integers in the range [0, 2^31-1].  Passing values outside
// this range results in unspecified behavior.
//
// All results from these functions will either also be in this range or
// will overflow into two integer words.  In the latter case, the least
// significant integer word will be in the above range (the sign bit will be
// zero).  This means that if 'msw' is the most significant integer word and
// 'lsw' is the least significant word, the full number is actually:
//     msw * 2^31 + lsw
// (notice 2^31, NOT 2^32).

integer SIGN_BIT_MASK = 0x80000000;

// Returns the full product of two unsigned integers.  The first (index 0)
// integer is the most significant integer of the product.  The second
// (index 1) integer is the least significant integer of the product.
list u_intProd(integer i1, integer i2)
{
integer i1Low = i1 & 0xFFFF;
integer i1High = i1 >> 16;
integer i2Low = i2 & 0xFFFF;
integer i2High = i2 >> 16;

//llOwnerSay("DEBUG - intProd: i1Low = "+(string)i1Low);
//llOwnerSay("DEBUG - intProd: i1High = "+(string)i1High);
//llOwnerSay("DEBUG - intProd: i2Low = "+(string)i2Low);
//llOwnerSay("DEBUG - intProd: i2High = "+(string)i2High);

integer lowLow = i1Low*i2Low;
integer lowHigh = i1Low*i2High;
integer highLow = i1High*i2Low;
integer highHigh = i1High*i2High;

integer lowLowMSW = (lowLow >> 31) & 0x1;
integer lowLowLSW = lowLow & ~SIGN_BIT_MASK;
integer lowHighMSW = (lowHigh >> 15) & 0xFFFF;
integer lowHighLSW = (lowHigh << 16) & ~SIGN_BIT_MASK;
integer highLowMSW = (highLow >> 15) & 0xFFFF;
integer highLowLSW = (highLow << 16) & ~SIGN_BIT_MASK;

//llOwnerSay("DEBUG - intProd: lowLowMSW = "+(string)lowLowMSW);
//llOwnerSay("DEBUG - intProd: lowLowLSW = "+(string)lowLowLSW);
//llOwnerSay("DEBUG - intProd: lowHighMSW = "+(string)lowHighMSW);
//llOwnerSay("DEBUG - intProd: lowHighLSW = "+(string)lowHighLSW);
//llOwnerSay("DEBUG - intProd: highLowMSW = "+(string)highLowMSW);
//llOwnerSay("DEBUG - intProd: highLowLSW = "+(string)highLowLSW);

integer msw = lowLowMSW+(highHigh<<1)+lowHighMSW+highLowMSW;

integer accum0 = lowLowLSW+lowHighLSW;
if (accum0 & SIGN_BIT_MASK)
{
accum0 = accum0 & ~SIGN_BIT_MASK;
++msw;
}

integer lsw = accum0+highLowLSW;
if (lsw & SIGN_BIT_MASK)
{
lsw = lsw & ~SIGN_BIT_MASK;
++msw;
}

//llOwnerSay("DEBUG - i1 = "+(string)i1);
//llOwnerSay("DEBUG - i2 = "+(string)i2);
//llOwnerSay("DEBUG - msw = "+(string)msw);
//llOwnerSay("DEBUG - lsw = "+(string)lsw);

return [ msw, lsw ];
}

// Returns the sum of a big number (product of integers) and a little number
// (integer).  The first (index 0) integer is the most significant integer
// of the sum, and the second (index 1) integer is the least significant
// integer of the sum.
list u_bigSum(integer msw1, integer lsw1, integer i2)
{
integer msw = msw1;
integer lsw = lsw1+i2;

if (lsw & SIGN_BIT_MASK)
{
lsw = lsw & ~SIGN_BIT_MASK;
++msw;
}

return [ msw, lsw ];
}

// Returns the modulo of a large dividend (product of two integers) and a
// small divisor (integer).
integer u_bigMod(integer dividendMSW, integer dividendLSW, integer divisor)
{
integer msw = dividendMSW%divisor;
integer lsw = dividendLSW%divisor;

//llOwnerSay("DEBUG - bigMod: dividendMSW = "+(string)dividendMSW);
//llOwnerSay("DEBUG - bigMod: dividendLSW = "+(string)dividendLSW);
//llOwnerSay("DEBUG - bigMod: divisor = "+(string)divisor);

// This might be slow, but it WILL finish.  Proof (assume msw > 0):
//     x = msw * 2^31 + lsw
//     x % y = (msw * 2^31) % y + lsw % y
//         = (msw % y) * (2^31 % y) + lsw % y
//     msw % y <= msw
//     lsw % y <= lsw
//     y <= 2^31 - 1
//     2^31 % y < 2^31 - 1
// thus:
//     (msw % y) * (2^31 % y) + lsw % y < msw * 2^31 + lsw
while (msw != 0)
{
//llOwnerSay("DEBUG - msw = "+(string)msw);

integer wsmod = (0x7FFFFFFF%divisor)+1;

list prod = u_intProd(wsmod, msw);
integer prodMSW = llList2Integer(prod, 0);
integer prodLSW = llList2Integer(prod, 1);

list sum = u_bigSum(prodMSW, prodLSW, lsw);
msw = llList2Integer(sum, 0)%divisor;
lsw = llList2Integer(sum, 1)%divisor;

//llOwnerSay("DEBUG - bigMod: msw = "+(string)msw);
//llOwnerSay("DEBUG - bigMod: lsw = "+(string)lsw);
}

return lsw;
}

// Returns (a*b)%c.
integer u_modProd(integer a, integer b, integer c)
{
list prod = u_intProd(a, b);
integer prodMSW = llList2Integer(prod, 0);
integer prodLSW = llList2Integer(prod, 1);

integer result =  u_bigMod(prodMSW, prodLSW, c);

//llOwnerSay("DEBUG modProd - a = "+(string)a);
//llOwnerSay("DEBUG modProd - b = "+(string)b);
//llOwnerSay("DEBUG modProd - c = "+(string)c);
//llOwnerSay("DEBUG modProd - prodMSW = "+(string)prodMSW);
//llOwnerSay("DEBUG modProd - prodLSW = "+(string)prodLSW);
//llOwnerSay("DEBUG modProd - result = "+(string)result);

return result;
}

// Returns (a^b)%c.
integer u_modPow(integer a, integer b, integer c)
{
integer result = 1;
integer currentPow = a;
integer exp = b;

while (exp != 0)
{
//llOwnerSay("DEBUG - modPow: exp = "+(string)exp);

if (exp & 0x1)
{
result = u_modProd(result, currentPow, c);
}

//llOwnerSay("DEBUG - modPow: currentPow = "+(string)currentPow);
//llOwnerSay("DEBUG - modPow: result = "+(string)result);

currentPow = u_modProd(currentPow, currentPow, c);
exp = exp >> 1;
}

return result;
}

default
{
touch_start(integer total_number)
{
integer N_TESTS = 10;

float startTime = llGetTime();

integer i;
for (i = 0; i < N_TESTS; ++i)
{
integer a = (integer)llFloor(llFrand(0x7FFFFFFF));
integer b = (integer)llFloor(llFrand(0x7FFFFFFF));
integer c = (integer)llFloor(llFrand(0x7FFFFFFF));

llOwnerSay("a = "+(string)a);
llOwnerSay("b = "+(string)b);
llOwnerSay("c = "+(string)c);

integer result = u_modPow(a, b, c);

llOwnerSay("(a^b)%c = "+(string)result);
}

float endTime = llGetTime();

float timeDiff = endTime - startTime;
float avgTime = timeDiff / N_TESTS;

llOwnerSay("Average execution time: "+(string)avgTime+" s");
}
}```

read his explaination here.

This article wasn't helpful for you? Maybe the related article at the LSL Portal is able to bring enlightenment.

Functions | Math
There is one comment on this page. [Display comments/form]