import { SecureRandom } from '../random/SecureRandom.js' ; var dbits ; var canary = 0xdeadbeefcafe ; var j_lm = ( ( canary & 0xffffff ) == 0xefcafe ) ; export function BigInteger ( a , b , c ) { if ( a != null ) { if ( "number" == typeof a ) { this . fromNumber ( a , b , c ) ; } else if ( b == null && "string" != typeof a ) { this . fromString ( a , 256 ) ; } else { this . fromString ( a , b ) ; } } } function nbi ( ) { return new BigInteger ( null ) ; } function am1 ( i , x , w , j , c , n ) { while ( -- n >= 0 ) { var v = x * this [ i ++ ] + w [ j ] + c ; c = Math . floor ( v / 0x4000000 ) ; w [ j ++ ] = v & 0x3ffffff ; } return c ; } function am2 ( i , x , w , j , c , n ) { var xl = x & 0x7fff , xh = x >> 15 ; while ( -- n >= 0 ) { var l = this [ i ] & 0x7fff ; var h = this [ i ++ ] >> 15 ; var m = xh * l + h * xl ; l = xl * l + ( ( m & 0x7fff ) << 15 ) + w [ j ] + ( c & 0x3fffffff ) ; c = ( l >>> 30 ) + ( m >>> 15 ) + xh * h + ( c >>> 30 ) ; w [ j ++ ] = l & 0x3fffffff ; } return c ; } function am3 ( i , x , w , j , c , n ) { var xl = x & 0x3fff , xh = x >> 14 ; while ( -- n >= 0 ) { var l = this [ i ] & 0x3fff ; var h = this [ i ++ ] >> 14 ; var m = xh * l + h * xl ; l = xl * l + ( ( m & 0x3fff ) << 14 ) + w [ j ] + c ; c = ( l >> 28 ) + ( m >> 14 ) + xh * h ; w [ j ++ ] = l & 0xfffffff ; } return c ; } if ( j_lm && ( typeof navigator === "object" && navigator . appName == "Microsoft Internet Explorer" ) ) { BigInteger . prototype . am = am2 ; dbits = 30 ; } else if ( j_lm && ( typeof navigator === "object" && navigator . appName != "Netscape" ) ) { BigInteger . prototype . am = am1 ; dbits = 26 ; } else { BigInteger . prototype . am = am3 ; dbits = 28 ; } BigInteger . prototype . DB = dbits ; BigInteger . prototype . DM = ( ( 1 << dbits ) - 1 ) ; BigInteger . prototype . DV = ( 1 << dbits ) ; var BI_FP = 52 ; BigInteger . prototype . FV = Math . pow ( 2 , BI_FP ) ; BigInteger . prototype . F1 = BI_FP - dbits ; BigInteger . prototype . F2 = 2 * dbits - BI_FP ; var BI_RM = "0123456789abcdefghijklmnopqrstuvwxyz" ; var BI_RC = new Array ( ) ; var rr , vv ; rr = "0" . charCodeAt ( 0 ) ; for ( vv = 0 ; vv <= 9 ; ++ vv ) BI_RC [ rr ++ ] = vv ; rr = "a" . charCodeAt ( 0 ) ; for ( vv = 10 ; vv < 36 ; ++ vv ) BI_RC [ rr ++ ] = vv ; rr = "A" . charCodeAt ( 0 ) ; for ( vv = 10 ; vv < 36 ; ++ vv ) BI_RC [ rr ++ ] = vv ; function int2char ( n ) { return BI_RM . charAt ( n ) ; } function intAt ( s , i ) { var c = BI_RC [ s . charCodeAt ( i ) ] ; return ( c == null ) ? - 1 : c ; } function bnpCopyTo ( r ) { for ( var i = this . t - 1 ; i >= 0 ; -- i ) r [ i ] = this [ i ] ; r . t = this . t ; r . s = this . s ; } function bnpFromInt ( x ) { this . t = 1 ; this . s = ( x < 0 ) ? - 1 : 0 ; if ( x > 0 ) { this [ 0 ] = x ; } else if ( x < - 1 ) { this [ 0 ] = x + DV ; } else { this . t = 0 ; } } function nbv ( i ) { var r = nbi ( ) ; r . fromInt ( i ) ; return r ; } function bnpFromString ( s , b ) { var k ; if ( b == 16 ) { k = 4 ; } else if ( b == 8 ) { k = 3 ; } else if ( b == 256 ) { k = 8 ; } else if ( b == 2 ) { k = 1 ; } else if ( b == 32 ) { k = 5 ; } else if ( b == 4 ) { k = 2 ; } else { this . fromRadix ( s , b ) ; return ; } this . t = 0 ; this . s = 0 ; var i = s . length , mi = false , sh = 0 ; while ( -- i >= 0 ) { var x = ( k == 8 ) ? s [ i ] & 0xff : intAt ( s , i ) ; if ( x < 0 ) { if ( s . charAt ( i ) == "-" ) mi = true ; continue ; } mi = false ; if ( sh == 0 ) { this [ this . t ++ ] = x ; } else if ( sh + k > this . DB ) { this [ this . t - 1 ] |= ( x & ( ( 1 << ( this . DB - sh ) ) - 1 ) ) << sh ; this [ this . t ++ ] = ( x >> ( this . DB - sh ) ) ; } else { this [ this . t - 1 ] |= x << sh ; } sh += k ; if ( sh >= this . DB ) sh -= this . DB ; } if ( k == 8 && ( s [ 0 ] & 0x80 ) != 0 ) { this . s = - 1 ; if ( sh > 0 ) this [ this . t - 1 ] |= ( ( 1 << ( this . DB - sh ) ) - 1 ) << sh ; } this . clamp ( ) ; if ( mi ) BigInteger . ZERO . subTo ( this , this ) ; } function bnpClamp ( ) { var c = this . s & this . DM ; while ( this . t > 0 && this [ this . t - 1 ] == c ) -- this . t ; } function bnToString ( b ) { if ( this . s < 0 ) return "-" + this . negate ( ) . toString ( b ) ; var k ; if ( b == 16 ) { k = 4 ; } else if ( b == 8 ) { k = 3 ; } else if ( b == 2 ) { k = 1 ; } else if ( b == 32 ) { k = 5 ; } else if ( b == 4 ) { k = 2 ; } else { return this . toRadix ( b ) ; } var km = ( 1 << k ) - 1 , d , m = false , r = "" , i = this . t ; var p = this . DB - ( i * this . DB ) % k ; if ( i -- > 0 ) { if ( p < this . DB && ( d = this [ i ] >> p ) > 0 ) { m = true ; r = int2char ( d ) ; } while ( i >= 0 ) { if ( p < k ) { d = ( this [ i ] & ( ( 1 << p ) - 1 ) ) << ( k - p ) ; d |= this [ -- i ] >> ( p += this . DB - k ) ; } else { d = ( this [ i ] >> ( p -= k ) ) & km ; if ( p <= 0 ) { p += this . DB ; -- i ; } } if ( d > 0 ) m = true ; if ( m ) r += int2char ( d ) ; } } return m ? r : "0" ; } function bnNegate ( ) { var r = nbi ( ) ; BigInteger . ZERO . subTo ( this , r ) ; return r ; } function bnAbs ( ) { return ( this . s < 0 ) ? this . negate ( ) : this ; } function bnCompareTo ( a ) { var r = this . s - a . s ; if ( r != 0 ) return r ; var i = this . t ; r = i - a . t ; if ( r != 0 ) return ( this . s < 0 ) ? - r : r ; while ( -- i >= 0 ) if ( ( r = this [ i ] - a [ i ] ) != 0 ) return r ; return 0 ; } function nbits ( x ) { var r = 1 , t ; if ( ( t = x >>> 16 ) != 0 ) { x = t ; r += 16 ; } if ( ( t = x >> 8 ) != 0 ) { x = t ; r += 8 ; } if ( ( t = x >> 4 ) != 0 ) { x = t ; r += 4 ; } if ( ( t = x >> 2 ) != 0 ) { x = t ; r += 2 ; } if ( ( t = x >> 1 ) != 0 ) { x = t ; r += 1 ; } return r ; } function bnBitLength ( ) { if ( this . t <= 0 ) return 0 ; return this . DB * ( this . t - 1 ) + nbits ( this [ this . t - 1 ] ^ ( this . s & this . DM ) ) ; } function bnpDLShiftTo ( n , r ) { var i ; for ( i = this . t - 1 ; i >= 0 ; -- i ) r [ i + n ] = this [ i ] ; for ( i = n - 1 ; i >= 0 ; -- i ) r [ i ] = 0 ; r . t = this . t + n ; r . s = this . s ; } function bnpDRShiftTo ( n , r ) { for ( var i = n ; i < this . t ; ++ i ) r [ i - n ] = this [ i ] ; r . t = Math . max ( this . t - n , 0 ) ; r . s = this . s ; } function bnpLShiftTo ( n , r ) { var bs = n % this . DB ; var cbs = this . DB - bs ; var bm = ( 1 << cbs ) - 1 ; var ds = Math . floor ( n / this . DB ) , c = ( this . s << bs ) & this . DM , i ; for ( i = this . t - 1 ; i >= 0 ; -- i ) { r [ i + ds + 1 ] = ( this [ i ] >> cbs ) | c ; c = ( this [ i ] & bm ) << bs ; } for ( i = ds - 1 ; i >= 0 ; -- i ) r [ i ] = 0 ; r [ ds ] = c ; r . t = this . t + ds + 1 ; r . s = this . s ; r . clamp ( ) ; } function bnpRShiftTo ( n , r ) { r . s = this . s ; var ds = Math . floor ( n / this . DB ) ; if ( ds >= this . t ) { r . t = 0 ; return ; } var bs = n % this . DB ; var cbs = this . DB - bs ; var bm = ( 1 << bs ) - 1 ; r [ 0 ] = this [ ds ] >> bs ; for ( var i = ds + 1 ; i < this . t ; ++ i ) { r [ i - ds - 1 ] |= ( this [ i ] & bm ) << cbs ; r [ i - ds ] = this [ i ] >> bs ; } if ( bs > 0 ) r [ this . t - ds - 1 ] |= ( this . s & bm ) << cbs ; r . t = this . t - ds ; r . clamp ( ) ; } function bnpSubTo ( a , r ) { var i = 0 , c = 0 , m = Math . min ( a . t , this . t ) ; while ( i < m ) { c += this [ i ] - a [ i ] ; r [ i ++ ] = c & this . DM ; c >>= this . DB ; } if ( a . t < this . t ) { c -= a . s ; while ( i < this . t ) { c += this [ i ] ; r [ i ++ ] = c & this . DM ; c >>= this . DB ; } c += this . s ; } else { c += this . s ; while ( i < a . t ) { c -= a [ i ] ; r [ i ++ ] = c & this . DM ; c >>= this . DB ; } c -= a . s ; } r . s = ( c < 0 ) ? - 1 : 0 ; if ( c < - 1 ) { r [ i ++ ] = this . DV + c ; } else if ( c > 0 ) r [ i ++ ] = c ; r . t = i ; r . clamp ( ) ; } function bnpMultiplyTo ( a , r ) { var x = this . abs ( ) , y = a . abs ( ) ; var i = x . t ; r . t = i + y . t ; while ( -- i >= 0 ) r [ i ] = 0 ; for ( i = 0 ; i < y . t ; ++ i ) r [ i + x . t ] = x . am ( 0 , y [ i ] , r , i , 0 , x . t ) ; r . s = 0 ; r . clamp ( ) ; if ( this . s != a . s ) BigInteger . ZERO . subTo ( r , r ) ; } function bnpSquareTo ( r ) { var x = this . abs ( ) ; var i = r . t = 2 * x . t ; while ( -- i >= 0 ) r [ i ] = 0 ; for ( i = 0 ; i < x . t - 1 ; ++ i ) { var c = x . am ( i , x [ i ] , r , 2 * i , 0 , 1 ) ; if ( ( r [ i + x . t ] += x . am ( i + 1 , 2 * x [ i ] , r , 2 * i + 1 , c , x . t - i - 1 ) ) >= x . DV ) { r [ i + x . t ] -= x . DV ; r [ i + x . t + 1 ] = 1 ; } } if ( r . t > 0 ) r [ r . t - 1 ] += x . am ( i , x [ i ] , r , 2 * i , 0 , 1 ) ; r . s = 0 ; r . clamp ( ) ; } function bnpDivRemTo ( m , q , r ) { var pm = m . abs ( ) ; if ( pm . t <= 0 ) return ; var pt = this . abs ( ) ; if ( pt . t < pm . t ) { if ( q != null ) q . fromInt ( 0 ) ; if ( r != null ) this . copyTo ( r ) ; return ; } if ( r == null ) r = nbi ( ) ; var y = nbi ( ) , ts = this . s , ms = m . s ; var nsh = this . DB - nbits ( pm [ pm . t - 1 ] ) ; if ( nsh > 0 ) { pm . lShiftTo ( nsh , y ) ; pt . lShiftTo ( nsh , r ) ; } else { pm . copyTo ( y ) ; pt . copyTo ( r ) ; } var ys = y . t ; var y0 = y [ ys - 1 ] ; if ( y0 == 0 ) return ; var yt = y0 * ( 1 << this . F1 ) + ( ( ys > 1 ) ? y [ ys - 2 ] >> this . F2 : 0 ) ; var d1 = this . FV / yt , d2 = ( 1 << this . F1 ) / yt , e = 1 << this . F2 ; var i = r . t , j = i - ys , t = ( q == null ) ? nbi ( ) : q ; y . dlShiftTo ( j , t ) ; if ( r . compareTo ( t ) >= 0 ) { r [ r . t ++ ] = 1 ; r . subTo ( t , r ) ; } BigInteger . ONE . dlShiftTo ( ys , t ) ; t . subTo ( y , y ) ; while ( y . t < ys ) y [ y . t ++ ] = 0 ; while ( -- j >= 0 ) { var qd = ( r [ -- i ] == y0 ) ? this . DM : Math . floor ( r [ i ] * d1 + ( r [ i - 1 ] + e ) * d2 ) ; if ( ( r [ i ] += y . am ( 0 , qd , r , j , 0 , ys ) ) < qd ) { y . dlShiftTo ( j , t ) ; r . subTo ( t , r ) ; while ( r [ i ] < -- qd ) r . subTo ( t , r ) ; } } if ( q != null ) { r . drShiftTo ( ys , q ) ; if ( ts != ms ) BigInteger . ZERO . subTo ( q , q ) ; } r . t = ys ; r . clamp ( ) ; if ( nsh > 0 ) r . rShiftTo ( nsh , r ) ; if ( ts < 0 ) BigInteger . ZERO . subTo ( r , r ) ; } function bnMod ( a ) { var r = nbi ( ) ; this . abs ( ) . divRemTo ( a , null , r ) ; if ( this . s < 0 && r . compareTo ( BigInteger . ZERO ) > 0 ) a . subTo ( r , r ) ; return r ; } function Classic ( m ) { this . m = m ; } function cConvert ( x ) { if ( x . s < 0 || x . compareTo ( this . m ) >= 0 ) { return x . mod ( this . m ) ; } else { return x ; } } function cRevert ( x ) { return x ; } function cReduce ( x ) { x . divRemTo ( this . m , null , x ) ; } function cMulTo ( x , y , r ) { x . multiplyTo ( y , r ) ; this . reduce ( r ) ; } function cSqrTo ( x , r ) { x . squareTo ( r ) ; this . reduce ( r ) ; } Classic . prototype . convert = cConvert ; Classic . prototype . revert = cRevert ; Classic . prototype . reduce = cReduce ; Classic . prototype . mulTo = cMulTo ; Classic . prototype . sqrTo = cSqrTo ; function bnpInvDigit ( ) { if ( this . t < 1 ) return 0 ; var x = this [ 0 ] ; if ( ( x & 1 ) == 0 ) return 0 ; var y = x & 3 ; y = ( y * ( 2 - ( x & 0xf ) * y ) ) & 0xf ; y = ( y * ( 2 - ( x & 0xff ) * y ) ) & 0xff ; y = ( y * ( 2 - ( ( ( x & 0xffff ) * y ) & 0xffff ) ) ) & 0xffff ; y = ( y * ( 2 - x * y % this . DV ) ) % this . DV ; return ( y > 0 ) ? this . DV - y : - y ; } function Montgomery ( m ) { this . m = m ; this . mp = m . invDigit ( ) ; this . mpl = this . mp & 0x7fff ; this . mph = this . mp >> 15 ; this . um = ( 1 << ( m . DB - 15 ) ) - 1 ; this . mt2 = 2 * m . t ; } function montConvert ( x ) { var r = nbi ( ) ; x . abs ( ) . dlShiftTo ( this . m . t , r ) ; r . divRemTo ( this . m , null , r ) ; if ( x . s < 0 && r . compareTo ( BigInteger . ZERO ) > 0 ) this . m . subTo ( r , r ) ; return r ; } function montRevert ( x ) { var r = nbi ( ) ; x . copyTo ( r ) ; this . reduce ( r ) ; return r ; } function montReduce ( x ) { while ( x . t <= this . mt2 ) x [ x . t ++ ] = 0 ; for ( var i = 0 ; i < this . m . t ; ++ i ) { var j = x [ i ] & 0x7fff ; var u0 = ( j * this . mpl + ( ( ( j * this . mph + ( x [ i ] >> 15 ) * this . mpl ) & this . um ) << 15 ) ) & x . DM ; j = i + this . m . t ; x [ j ] += this . m . am ( 0 , u0 , x , i , 0 , this . m . t ) ; while ( x [ j ] >= x . DV ) { x [ j ] -= x . DV ; x [ ++ j ] ++ ; } } x . clamp ( ) ; x . drShiftTo ( this . m . t , x ) ; if ( x . compareTo ( this . m ) >= 0 ) x . subTo ( this . m , x ) ; } function montSqrTo ( x , r ) { x . squareTo ( r ) ; this . reduce ( r ) ; } function montMulTo ( x , y , r ) { x . multiplyTo ( y , r ) ; this . reduce ( r ) ; } Montgomery . prototype . convert = montConvert ; Montgomery . prototype . revert = montRevert ; Montgomery . prototype . reduce = montReduce ; Montgomery . prototype . mulTo = montMulTo ; Montgomery . prototype . sqrTo = montSqrTo ; function bnpIsEven ( ) { return ( ( this . t > 0 ) ? ( this [ 0 ] & 1 ) : this . s ) == 0 ; } function bnpExp ( e , z ) { if ( e > 0xffffffff || e < 1 ) return BigInteger . ONE ; var r = nbi ( ) , r2 = nbi ( ) , g = z . convert ( this ) , i = nbits ( e ) - 1 ; g . copyTo ( r ) ; while ( -- i >= 0 ) { z . sqrTo ( r , r2 ) ; if ( ( e & ( 1 << i ) ) > 0 ) { z . mulTo ( r2 , g , r ) ; } else { var t = r ; r = r2 ; r2 = t ; } } return z . revert ( r ) ; } function bnModPowInt ( e , m ) { var z ; if ( e < 256 || m . isEven ( ) ) z = new Classic ( m ) ; else z = new Montgomery ( m ) ; return this . exp ( e , z ) ; } BigInteger . prototype . copyTo = bnpCopyTo ; BigInteger . prototype . fromInt = bnpFromInt ; BigInteger . prototype . fromString = bnpFromString ; BigInteger . prototype . clamp = bnpClamp ; BigInteger . prototype . dlShiftTo = bnpDLShiftTo ; BigInteger . prototype . drShiftTo = bnpDRShiftTo ; BigInteger . prototype . lShiftTo = bnpLShiftTo ; BigInteger . prototype . rShiftTo = bnpRShiftTo ; BigInteger . prototype . subTo = bnpSubTo ; BigInteger . prototype . multiplyTo = bnpMultiplyTo ; BigInteger . prototype . squareTo = bnpSquareTo ; BigInteger . prototype . divRemTo = bnpDivRemTo ; BigInteger . prototype . invDigit = bnpInvDigit ; BigInteger . prototype . isEven = bnpIsEven ; BigInteger . prototype . exp = bnpExp ; BigInteger . prototype . toString = bnToString ; BigInteger . prototype . negate = bnNegate ; BigInteger . prototype . abs = bnAbs ; BigInteger . prototype . compareTo = bnCompareTo ; BigInteger . prototype . bitLength = bnBitLength ; BigInteger . prototype . mod = bnMod ; BigInteger . prototype . modPowInt = bnModPowInt ; BigInteger . ZERO = nbv ( 0 ) ; BigInteger . ONE = nbv ( 1 ) ; function bnClone ( ) { var r = nbi ( ) ; this . copyTo ( r ) ; return r ; } function bnIntValue ( ) { if ( this . s < 0 ) { if ( this . t == 1 ) { return this [ 0 ] - this . DV ; } else if ( this . t == 0 ) return - 1 ; } else if ( this . t == 1 ) { return this [ 0 ] ; } else if ( this . t == 0 ) return 0 ; return ( ( this [ 1 ] & ( ( 1 << ( 32 - this . DB ) ) - 1 ) ) << this . DB ) | this [ 0 ] ; } function bnByteValue ( ) { return ( this . t == 0 ) ? this . s : ( this [ 0 ] << 24 ) >> 24 ; } function bnShortValue ( ) { return ( this . t == 0 ) ? this . s : ( this [ 0 ] << 16 ) >> 16 ; } function bnpChunkSize ( r ) { return Math . floor ( Math . LN2 * this . DB / Math . log ( r ) ) ; } function bnSigNum ( ) { if ( this . s < 0 ) { return - 1 ; } else if ( this . t <= 0 || ( this . t == 1 && this [ 0 ] <= 0 ) ) { return 0 ; } else { return 1 ; } } function bnpToRadix ( b ) { if ( b == null ) b = 10 ; if ( this . signum ( ) == 0 || b < 2 || b > 36 ) return "0" ; var cs = this . chunkSize ( b ) ; var a = Math . pow ( b , cs ) ; var d = nbv ( a ) , y = nbi ( ) , z = nbi ( ) , r = "" ; this . divRemTo ( d , y , z ) ; while ( y . signum ( ) > 0 ) { r = ( a + z . intValue ( ) ) . toString ( b ) . substr ( 1 ) + r ; y . divRemTo ( d , y , z ) ; } return z . intValue ( ) . toString ( b ) + r ; } function bnpFromRadix ( s , b ) { this . fromInt ( 0 ) ; if ( b == null ) b = 10 ; var cs = this . chunkSize ( b ) ; var d = Math . pow ( b , cs ) , mi = false , j = 0 , w = 0 ; for ( var i = 0 ; i < s . length ; ++ i ) { var x = intAt ( s , i ) ; if ( x < 0 ) { if ( s . charAt ( i ) == "-" && this . signum ( ) == 0 ) mi = true ; continue ; } w = b * w + x ; if ( ++ j >= cs ) { this . dMultiply ( d ) ; this . dAddOffset ( w , 0 ) ; j = 0 ; w = 0 ; } } if ( j > 0 ) { this . dMultiply ( Math . pow ( b , j ) ) ; this . dAddOffset ( w , 0 ) ; } if ( mi ) BigInteger . ZERO . subTo ( this , this ) ; } function bnpFromNumber ( a , b , c ) { if ( "number" == typeof b ) { if ( a < 2 ) { this . fromInt ( 1 ) ; } else { this . fromNumber ( a , c ) ; if ( ! this . testBit ( a - 1 ) ) { this . bitwiseTo ( BigInteger . ONE . shiftLeft ( a - 1 ) , op_or , this ) ; } if ( this . isEven ( ) ) this . dAddOffset ( 1 , 0 ) ; while ( ! this . isProbablePrime ( b ) ) { this . dAddOffset ( 2 , 0 ) ; if ( this . bitLength ( ) > a ) this . subTo ( BigInteger . ONE . shiftLeft ( a - 1 ) , this ) ; } } } else { var x = new Array ( ) , t = a & 7 ; x . length = ( a >> 3 ) + 1 ; b . nextBytes ( x ) ; if ( t > 0 ) x [ 0 ] &= ( ( 1 << t ) - 1 ) ; else x [ 0 ] = 0 ; this . fromString ( x , 256 ) ; } } function bnToByteArray ( ) { var i = this . t , r = new Array ( ) ; r [ 0 ] = this . s ; var p = this . DB - ( i * this . DB ) % 8 , d , k = 0 ; if ( i -- > 0 ) { if ( p < this . DB && ( d = this [ i ] >> p ) != ( this . s & this . DM ) >> p ) { r [ k ++ ] = d | ( this . s << ( this . DB - p ) ) ; } while ( i >= 0 ) { if ( p < 8 ) { d = ( this [ i ] & ( ( 1 << p ) - 1 ) ) << ( 8 - p ) ; d |= this [ -- i ] >> ( p += this . DB - 8 ) ; } else { d = ( this [ i ] >> ( p -= 8 ) ) & 0xff ; if ( p <= 0 ) { p += this . DB ; -- i ; } } if ( ( d & 0x80 ) != 0 ) d |= - 256 ; if ( k == 0 && ( this . s & 0x80 ) != ( d & 0x80 ) ) ++ k ; if ( k > 0 || d != this . s ) r [ k ++ ] = d ; } } return r ; } function bnEquals ( a ) { return ( this . compareTo ( a ) == 0 ) ; } function bnMin ( a ) { return ( this . compareTo ( a ) < 0 ) ? this : a ; } function bnMax ( a ) { return ( this . compareTo ( a ) > 0 ) ? this : a ; } function bnpBitwiseTo ( a , op , r ) { var i , f , m = Math . min ( a . t , this . t ) ; for ( i = 0 ; i < m ; ++ i ) r [ i ] = op ( this [ i ] , a [ i ] ) ; if ( a . t < this . t ) { f = a . s & this . DM ; for ( i = m ; i < this . t ; ++ i ) r [ i ] = op ( this [ i ] , f ) ; r . t = this . t ; } else { f = this . s & this . DM ; for ( i = m ; i < a . t ; ++ i ) r [ i ] = op ( f , a [ i ] ) ; r . t = a . t ; } r . s = op ( this . s , a . s ) ; r . clamp ( ) ; } function op_and ( x , y ) { return x & y ; } function bnAnd ( a ) { var r = nbi ( ) ; this . bitwiseTo ( a , op_and , r ) ; return r ; } function op_or ( x , y ) { return x | y ; } function bnOr ( a ) { var r = nbi ( ) ; this . bitwiseTo ( a , op_or , r ) ; return r ; } function op_xor ( x , y ) { return x ^ y ; } function bnXor ( a ) { var r = nbi ( ) ; this . bitwiseTo ( a , op_xor , r ) ; return r ; } function op_andnot ( x , y ) { return x & ~ y ; } function bnAndNot ( a ) { var r = nbi ( ) ; this . bitwiseTo ( a , op_andnot , r ) ; return r ; } function bnNot ( ) { var r = nbi ( ) ; for ( var i = 0 ; i < this . t ; ++ i ) r [ i ] = this . DM & ~ this [ i ] ; r . t = this . t ; r . s = ~ this . s ; return r ; } function bnShiftLeft ( n ) { var r = nbi ( ) ; if ( n < 0 ) this . rShiftTo ( - n , r ) ; else this . lShiftTo ( n , r ) ; return r ; } function bnShiftRight ( n ) { var r = nbi ( ) ; if ( n < 0 ) this . lShiftTo ( - n , r ) ; else this . rShiftTo ( n , r ) ; return r ; } function lbit ( x ) { if ( x == 0 ) return - 1 ; var r = 0 ; if ( ( x & 0xffff ) == 0 ) { x >>= 16 ; r += 16 ; } if ( ( x & 0xff ) == 0 ) { x >>= 8 ; r += 8 ; } if ( ( x & 0xf ) == 0 ) { x >>= 4 ; r += 4 ; } if ( ( x & 3 ) == 0 ) { x >>= 2 ; r += 2 ; } if ( ( x & 1 ) == 0 ) ++ r ; return r ; } function bnGetLowestSetBit ( ) { for ( var i = 0 ; i < this . t ; ++ i ) if ( this [ i ] != 0 ) return i * this . DB + lbit ( this [ i ] ) ; if ( this . s < 0 ) return this . t * this . DB ; return - 1 ; } function cbit ( x ) { var r = 0 ; while ( x != 0 ) { x &= x - 1 ; ++ r ; } return r ; } function bnBitCount ( ) { var r = 0 , x = this . s & this . DM ; for ( var i = 0 ; i < this . t ; ++ i ) r += cbit ( this [ i ] ^ x ) ; return r ; } function bnTestBit ( n ) { var j = Math . floor ( n / this . DB ) ; if ( j >= this . t ) return ( this . s != 0 ) ; return ( ( this [ j ] & ( 1 << ( n % this . DB ) ) ) != 0 ) ; } function bnpChangeBit ( n , op ) { var r = BigInteger . ONE . shiftLeft ( n ) ; this . bitwiseTo ( r , op , r ) ; return r ; } function bnSetBit ( n ) { return this . changeBit ( n , op_or ) ; } function bnClearBit ( n ) { return this . changeBit ( n , op_andnot ) ; } function bnFlipBit ( n ) { return this . changeBit ( n , op_xor ) ; } function bnpAddTo ( a , r ) { var i = 0 , c = 0 , m = Math . min ( a . t , this . t ) ; while ( i < m ) { c += this [ i ] + a [ i ] ; r [ i ++ ] = c & this . DM ; c >>= this . DB ; } if ( a . t < this . t ) { c += a . s ; while ( i < this . t ) { c += this [ i ] ; r [ i ++ ] = c & this . DM ; c >>= this . DB ; } c += this . s ; } else { c += this . s ; while ( i < a . t ) { c += a [ i ] ; r [ i ++ ] = c & this . DM ; c >>= this . DB ; } c += a . s ; } r . s = ( c < 0 ) ? - 1 : 0 ; if ( c > 0 ) { r [ i ++ ] = c ; } else if ( c < - 1 ) r [ i ++ ] = this . DV + c ; r . t = i ; r . clamp ( ) ; } function bnAdd ( a ) { var r = nbi ( ) ; this . addTo ( a , r ) ; return r ; } function bnSubtract ( a ) { var r = nbi ( ) ; this . subTo ( a , r ) ; return r ; } function bnMultiply ( a ) { var r = nbi ( ) ; this . multiplyTo ( a , r ) ; return r ; } function bnSquare ( ) { var r = nbi ( ) ; this . squareTo ( r ) ; return r ; } function bnDivide ( a ) { var r = nbi ( ) ; this . divRemTo ( a , r , null ) ; return r ; } function bnRemainder ( a ) { var r = nbi ( ) ; this . divRemTo ( a , null , r ) ; return r ; } function bnDivideAndRemainder ( a ) { var q = nbi ( ) , r = nbi ( ) ; this . divRemTo ( a , q , r ) ; return new Array ( q , r ) ; } function bnpDMultiply ( n ) { this [ this . t ] = this . am ( 0 , n - 1 , this , 0 , 0 , this . t ) ; ++ this . t ; this . clamp ( ) ; } function bnpDAddOffset ( n , w ) { if ( n == 0 ) return ; while ( this . t <= w ) this [ this . t ++ ] = 0 ; this [ w ] += n ; while ( this [ w ] >= this . DV ) { this [ w ] -= this . DV ; if ( ++ w >= this . t ) this [ this . t ++ ] = 0 ; ++ this [ w ] ; } } function NullExp ( ) { } function nNop ( x ) { return x ; } function nMulTo ( x , y , r ) { x . multiplyTo ( y , r ) ; } function nSqrTo ( x , r ) { x . squareTo ( r ) ; } NullExp . prototype . convert = nNop ; NullExp . prototype . revert = nNop ; NullExp . prototype . mulTo = nMulTo ; NullExp . prototype . sqrTo = nSqrTo ; function bnPow ( e ) { return this . exp ( e , new NullExp ( ) ) ; } function bnpMultiplyLowerTo ( a , n , r ) { var i = Math . min ( this . t + a . t , n ) ; r . s = 0 ; r . t = i ; while ( i > 0 ) r [ -- i ] = 0 ; var j ; for ( j = r . t - this . t ; i < j ; ++ i ) r [ i + this . t ] = this . am ( 0 , a [ i ] , r , i , 0 , this . t ) ; for ( j = Math . min ( a . t , n ) ; i < j ; ++ i ) this . am ( 0 , a [ i ] , r , i , 0 , n - i ) ; r . clamp ( ) ; } function bnpMultiplyUpperTo ( a , n , r ) { -- n ; var i = r . t = this . t + a . t - n ; r . s = 0 ; while ( -- i >= 0 ) r [ i ] = 0 ; for ( i = Math . max ( n - this . t , 0 ) ; i < a . t ; ++ i ) r [ this . t + i - n ] = this . am ( n - i , a [ i ] , r , 0 , 0 , this . t + i - n ) ; r . clamp ( ) ; r . drShiftTo ( 1 , r ) ; } function Barrett ( m ) { this . r2 = nbi ( ) ; this . q3 = nbi ( ) ; BigInteger . ONE . dlShiftTo ( 2 * m . t , this . r2 ) ; this . mu = this . r2 . divide ( m ) ; this . m = m ; } function barrettConvert ( x ) { if ( x . s < 0 || x . t > 2 * this . m . t ) { return x . mod ( this . m ) ; } else if ( x . compareTo ( this . m ) < 0 ) { return x ; } else { var r = nbi ( ) ; x . copyTo ( r ) ; this . reduce ( r ) ; return r ; } } function barrettRevert ( x ) { return x ; } function barrettReduce ( x ) { x . drShiftTo ( this . m . t - 1 , this . r2 ) ; if ( x . t > this . m . t + 1 ) { x . t = this . m . t + 1 ; x . clamp ( ) ; } this . mu . multiplyUpperTo ( this . r2 , this . m . t + 1 , this . q3 ) ; this . m . multiplyLowerTo ( this . q3 , this . m . t + 1 , this . r2 ) ; while ( x . compareTo ( this . r2 ) < 0 ) x . dAddOffset ( 1 , this . m . t + 1 ) ; x . subTo ( this . r2 , x ) ; while ( x . compareTo ( this . m ) >= 0 ) x . subTo ( this . m , x ) ; } function barrettSqrTo ( x , r ) { x . squareTo ( r ) ; this . reduce ( r ) ; } function barrettMulTo ( x , y , r ) { x . multiplyTo ( y , r ) ; this . reduce ( r ) ; } Barrett . prototype . convert = barrettConvert ; Barrett . prototype . revert = barrettRevert ; Barrett . prototype . reduce = barrettReduce ; Barrett . prototype . mulTo = barrettMulTo ; Barrett . prototype . sqrTo = barrettSqrTo ; function bnModPow ( e , m ) { var xHex = this . toString ( 16 ) ; var eHex = e . toString ( 16 ) ; var mHex = m . toString ( 16 ) ; var result = powMod ( str2bigInt ( xHex , 16 ) , str2bigInt ( eHex , 16 ) , str2bigInt ( mHex , 16 ) ) ; return new BigInteger ( bigInt2str ( result , 16 ) , 16 ) ; } function bnGCD ( a ) { var x = ( this . s < 0 ) ? this . negate ( ) : this . clone ( ) ; var y = ( a . s < 0 ) ? a . negate ( ) : a . clone ( ) ; if ( x . compareTo ( y ) < 0 ) { var t = x ; x = y ; y = t ; } var i = x . getLowestSetBit ( ) , g = y . getLowestSetBit ( ) ; if ( g < 0 ) return x ; if ( i < g ) g = i ; if ( g > 0 ) { x . rShiftTo ( g , x ) ; y . rShiftTo ( g , y ) ; } while ( x . signum ( ) > 0 ) { if ( ( i = x . getLowestSetBit ( ) ) > 0 ) x . rShiftTo ( i , x ) ; if ( ( i = y . getLowestSetBit ( ) ) > 0 ) y . rShiftTo ( i , y ) ; if ( x . compareTo ( y ) >= 0 ) { x . subTo ( y , x ) ; x . rShiftTo ( 1 , x ) ; } else { y . subTo ( x , y ) ; y . rShiftTo ( 1 , y ) ; } } if ( g > 0 ) y . lShiftTo ( g , y ) ; return y ; } function bnpModInt ( n ) { if ( n <= 0 ) return 0 ; var d = this . DV % n , r = ( this . s < 0 ) ? n - 1 : 0 ; if ( this . t > 0 ) { if ( d == 0 ) { r = this [ 0 ] % n ; } else { for ( var i = this . t - 1 ; i >= 0 ; -- i ) r = ( d * r + this [ i ] ) % n ; } } return r ; } function bnModInverse ( m ) { var ac = m . isEven ( ) ; if ( ( this . isEven ( ) && ac ) || m . signum ( ) == 0 ) return BigInteger . ZERO ; var u = m . clone ( ) , v = this . clone ( ) ; var a = nbv ( 1 ) , b = nbv ( 0 ) , c = nbv ( 0 ) , d = nbv ( 1 ) ; while ( u . signum ( ) != 0 ) { while ( u . isEven ( ) ) { u . rShiftTo ( 1 , u ) ; if ( ac ) { if ( ! a . isEven ( ) || ! b . isEven ( ) ) { a . addTo ( this , a ) ; b . subTo ( m , b ) ; } a . rShiftTo ( 1 , a ) ; } else if ( ! b . isEven ( ) ) b . subTo ( m , b ) ; b . rShiftTo ( 1 , b ) ; } while ( v . isEven ( ) ) { v . rShiftTo ( 1 , v ) ; if ( ac ) { if ( ! c . isEven ( ) || ! d . isEven ( ) ) { c . addTo ( this , c ) ; d . subTo ( m , d ) ; } c . rShiftTo ( 1 , c ) ; } else if ( ! d . isEven ( ) ) d . subTo ( m , d ) ; d . rShiftTo ( 1 , d ) ; } if ( u . compareTo ( v ) >= 0 ) { u . subTo ( v , u ) ; if ( ac ) a . subTo ( c , a ) ; b . subTo ( d , b ) ; } else { v . subTo ( u , v ) ; if ( ac ) c . subTo ( a , c ) ; d . subTo ( b , d ) ; } } if ( v . compareTo ( BigInteger . ONE ) != 0 ) return BigInteger . ZERO ; if ( d . compareTo ( m ) >= 0 ) return d . subtract ( m ) ; if ( d . signum ( ) < 0 ) d . addTo ( m , d ) ; else return d ; if ( d . signum ( ) < 0 ) return d . add ( m ) ; else return d ; } var lowprimes = [ 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 , 109 , 113 , 127 , 131 , 137 , 139 , 149 , 151 , 157 , 163 , 167 , 173 , 179 , 181 , 191 , 193 , 197 , 199 , 211 , 223 , 227 , 229 , 233 , 239 , 241 , 251 , 257 , 263 , 269 , 271 , 277 , 281 , 283 , 293 , 307 , 311 , 313 , 317 , 331 , 337 , 347 , 349 , 353 , 359 , 367 , 373 , 379 , 383 , 389 , 397 , 401 , 409 , 419 , 421 , 431 , 433 , 439 , 443 , 449 , 457 , 461 , 463 , 467 , 479 , 487 , 491 , 499 , 503 , 509 , 521 , 523 , 541 , 547 , 557 , 563 , 569 , 571 , 577 , 587 , 593 , 599 , 601 , 607 , 613 , 617 , 619 , 631 , 641 , 643 , 647 , 653 , 659 , 661 , 673 , 677 , 683 , 691 , 701 , 709 , 719 , 727 , 733 , 739 , 743 , 751 , 757 , 761 , 769 , 773 , 787 , 797 , 809 , 811 , 821 , 823 , 827 , 829 , 839 , 853 , 857 , 859 , 863 , 877 , 881 , 883 , 887 , 907 , 911 , 919 , 929 , 937 , 941 , 947 , 953 , 967 , 971 , 977 , 983 , 991 , 997 ] ; var lplim = ( 1 << 26 ) / lowprimes [ lowprimes . length - 1 ] ; function bnIsProbablePrime ( t ) { var i , x = this . abs ( ) ; if ( x . t == 1 && x [ 0 ] <= lowprimes [ lowprimes . length - 1 ] ) { for ( i = 0 ; i < lowprimes . length ; ++ i ) if ( x [ 0 ] == lowprimes [ i ] ) return true ; return false ; } if ( x . isEven ( ) ) return false ; i = 1 ; while ( i < lowprimes . length ) { var m = lowprimes [ i ] , j = i + 1 ; while ( j < lowprimes . length && m < lplim ) m *= lowprimes [ j ++ ] ; m = x . modInt ( m ) ; while ( i < j ) if ( m % lowprimes [ i ++ ] == 0 ) return false ; } return x . millerRabin ( t ) ; } function bnpMillerRabin ( t ) { var n1 = this . subtract ( BigInteger . ONE ) ; var k = n1 . getLowestSetBit ( ) ; if ( k <= 0 ) return false ; var r = n1 . shiftRight ( k ) ; t = ( t + 1 ) >> 1 ; if ( t > lowprimes . length ) t = lowprimes . length ; var a = nbi ( ) ; for ( var i = 0 ; i < t ; ++ i ) { a . fromInt ( lowprimes [ Math . floor ( Math . random ( ) * lowprimes . length ) ] ) ; var y = a . modPow ( r , this ) ; if ( y . compareTo ( BigInteger . ONE ) != 0 && y . compareTo ( n1 ) != 0 ) { var j = 1 ; while ( j ++ < k && y . compareTo ( n1 ) != 0 ) { y = y . modPowInt ( 2 , this ) ; if ( y . compareTo ( BigInteger . ONE ) == 0 ) return false ; } if ( y . compareTo ( n1 ) != 0 ) return false ; } } return true ; } BigInteger . prototype . chunkSize = bnpChunkSize ; BigInteger . prototype . toRadix = bnpToRadix ; BigInteger . prototype . fromRadix = bnpFromRadix ; BigInteger . prototype . fromNumber = bnpFromNumber ; BigInteger . prototype . bitwiseTo = bnpBitwiseTo ; BigInteger . prototype . changeBit = bnpChangeBit ; BigInteger . prototype . addTo = bnpAddTo ; BigInteger . prototype . dMultiply = bnpDMultiply ; BigInteger . prototype . dAddOffset = bnpDAddOffset ; BigInteger . prototype . multiplyLowerTo = bnpMultiplyLowerTo ; BigInteger . prototype . multiplyUpperTo = bnpMultiplyUpperTo ; BigInteger . prototype . modInt = bnpModInt ; BigInteger . prototype . millerRabin = bnpMillerRabin ; BigInteger . prototype . clone = bnClone ; BigInteger . prototype . intValue = bnIntValue ; BigInteger . prototype . byteValue = bnByteValue ; BigInteger . prototype . shortValue = bnShortValue ; BigInteger . prototype . signum = bnSigNum ; BigInteger . prototype . toByteArray = bnToByteArray ; BigInteger . prototype . equals = bnEquals ; BigInteger . prototype . min = bnMin ; BigInteger . prototype . max = bnMax ; BigInteger . prototype . and = bnAnd ; BigInteger . prototype . or = bnOr ; BigInteger . prototype . xor = bnXor ; BigInteger . prototype . andNot = bnAndNot ; BigInteger . prototype . not = bnNot ; BigInteger . prototype . shiftLeft = bnShiftLeft ; BigInteger . prototype . shiftRight = bnShiftRight ; BigInteger . prototype . getLowestSetBit = bnGetLowestSetBit ; BigInteger . prototype . bitCount = bnBitCount ; BigInteger . prototype . testBit = bnTestBit ; BigInteger . prototype . setBit = bnSetBit ; BigInteger . prototype . clearBit = bnClearBit ; BigInteger . prototype . flipBit = bnFlipBit ; BigInteger . prototype . add = bnAdd ; BigInteger . prototype . subtract = bnSubtract ; BigInteger . prototype . multiply = bnMultiply ; BigInteger . prototype . divide = bnDivide ; BigInteger . prototype . remainder = bnRemainder ; BigInteger . prototype . divideAndRemainder = bnDivideAndRemainder ; BigInteger . prototype . modPow = bnModPow ; BigInteger . prototype . modInverse = bnModInverse ; BigInteger . prototype . pow = bnPow ; BigInteger . prototype . gcd = bnGCD ; BigInteger . prototype . isProbablePrime = bnIsProbablePrime ; BigInteger . prototype . square = bnSquare ; export function parseBigInt ( str , r ) { return new BigInteger ( str , r ) ; } function linebrk ( s , n ) { var ret = "" ; var i = 0 ; while ( i + n < s . length ) { ret += s . substring ( i , i + n ) + "\n" ; i += n ; } return ret + s . substring ( i , s . length ) ; } function byte2Hex ( b ) { if ( b < 0x10 ) { return "0" + b . toString ( 16 ) ; } else { return b . toString ( 16 ) ; } } function pkcs1pad2 ( s , n ) { if ( n < s . length + 11 ) { alert ( "Message too long for RSA" ) ; return null ; } var ba = new Array ( ) ; var i = s . length - 1 ; while ( i >= 0 && n > 0 ) { var c = s . charCodeAt ( i -- ) ; if ( c < 128 ) { ba [ -- n ] = c ; } else if ( ( c > 127 ) && ( c < 2048 ) ) { ba [ -- n ] = ( c & 63 ) | 128 ; ba [ -- n ] = ( c >> 6 ) | 192 ; } else { ba [ -- n ] = ( c & 63 ) | 128 ; ba [ -- n ] = ( ( c >> 6 ) & 63 ) | 128 ; ba [ -- n ] = ( c >> 12 ) | 224 ; } } ba [ -- n ] = 0 ; var rng = new SecureRandom ( ) ; var x = new Array ( ) ; while ( n > 2 ) { x [ 0 ] = 0 ; while ( x [ 0 ] == 0 ) rng . nextBytes ( x ) ; ba [ -- n ] = x [ 0 ] ; } ba [ -- n ] = 2 ; ba [ -- n ] = 0 ; return new BigInteger ( ba ) ; } export function RSAKey ( ) { this . n = null ; this . e = 0 ; this . d = null ; this . p = null ; this . q = null ; this . dmp1 = null ; this . dmq1 = null ; this . coeff = null ; } function RSASetPublic ( N , E ) { if ( N != null && E != null && N . length > 0 && E . length > 0 ) { this . n = parseBigInt ( N , 16 ) ; this . e = parseInt ( E , 16 ) ; } else { alert ( "Invalid RSA public key" ) ; } } function RSADoPublic ( x ) { return x . modPowInt ( this . e , this . n ) ; } function RSAEncrypt ( text ) { var m = pkcs1pad2 ( text , ( this . n . bitLength ( ) + 7 ) >> 3 ) ; if ( m == null ) return null ; var c = this . doPublic ( m ) ; if ( c == null ) return null ; var h = c . toString ( 16 ) ; if ( ( h . length & 1 ) == 0 ) return h ; else return "0" + h ; } RSAKey . prototype . doPublic = RSADoPublic ; RSAKey . prototype . setPublic = RSASetPublic ; RSAKey . prototype . encrypt = RSAEncrypt ; function pkcs1unpad2 ( d , n ) { var b = d . toByteArray ( ) ; var i = 0 ; while ( i < b . length && b [ i ] == 0 ) ++ i ; if ( b . length - i != n - 1 || b [ i ] != 2 ) { return null ; } ++ i ; while ( b [ i ] != 0 ) if ( ++ i >= b . length ) return null ; var ret = "" ; while ( ++ i < b . length ) { var c = b [ i ] & 255 ; if ( c < 128 ) { ret += String . fromCharCode ( c ) ; } else if ( ( c > 191 ) && ( c < 224 ) ) { ret += String . fromCharCode ( ( ( c & 31 ) << 6 ) | ( b [ i + 1 ] & 63 ) ) ; ++ i ; } else { ret += String . fromCharCode ( ( ( c & 15 ) << 12 ) | ( ( b [ i + 1 ] & 63 ) << 6 ) | ( b [ i + 2 ] & 63 ) ) ; i += 2 ; } } return ret ; } function RSASetPrivate ( N , E , D ) { if ( N != null && E != null && N . length > 0 && E . length > 0 ) { this . n = parseBigInt ( N , 16 ) ; this . e = parseInt ( E , 16 ) ; this . d = parseBigInt ( D , 16 ) ; } else { alert ( "Invalid RSA private key" ) ; } } function RSASetPrivateEx ( N , E , D , P , Q , DP , DQ , C ) { if ( N != null && E != null && N . length > 0 && E . length > 0 ) { this . n = parseBigInt ( N , 16 ) ; this . e = parseInt ( E , 16 ) ; this . d = parseBigInt ( D , 16 ) ; this . p = parseBigInt ( P , 16 ) ; this . q = parseBigInt ( Q , 16 ) ; this . dmp1 = parseBigInt ( DP , 16 ) ; this . dmq1 = parseBigInt ( DQ , 16 ) ; this . coeff = parseBigInt ( C , 16 ) ; } else { alert ( "Invalid RSA private key" ) ; } } function RSAGenerate ( B , E ) { var rng = new SecureRandom ( ) ; var qs = B >> 1 ; this . e = parseInt ( E , 16 ) ; var ee = new BigInteger ( E , 16 ) ; for ( ; ; ) { for ( ; ; ) { this . p = new BigInteger ( B - qs , 10 , rng ) ; if ( this . p . subtract ( BigInteger . ONE ) . gcd ( ee ) . compareTo ( BigInteger . ONE ) == 0 ) break ; } for ( ; ; ) { this . q = new BigInteger ( qs , 10 , rng ) ; if ( this . q . subtract ( BigInteger . ONE ) . gcd ( ee ) . compareTo ( BigInteger . ONE ) == 0 ) break ; } if ( this . p . compareTo ( this . q ) <= 0 ) { var t = this . p ; this . p = this . q ; this . q = t ; } var p1 = this . p . subtract ( BigInteger . ONE ) ; var q1 = this . q . subtract ( BigInteger . ONE ) ; var phi = p1 . multiply ( q1 ) ; if ( phi . gcd ( ee ) . compareTo ( BigInteger . ONE ) == 0 ) { this . n = this . p . multiply ( this . q ) ; this . d = ee . modInverse ( phi ) ; this . dmp1 = this . d . mod ( p1 ) ; this . dmq1 = this . d . mod ( q1 ) ; this . coeff = this . q . modInverse ( this . p ) ; break ; } } } function RSADoPrivate ( x ) { if ( this . p == null || this . q == null ) { return x . modPow ( this . d , this . n ) ; } var xp = x . mod ( this . p ) . modPow ( this . dmp1 , this . p ) ; var xq = x . mod ( this . q ) . modPow ( this . dmq1 , this . q ) ; while ( xp . compareTo ( xq ) < 0 ) xp = xp . add ( this . p ) ; return xp . subtract ( xq ) . multiply ( this . coeff ) . mod ( this . p ) . multiply ( this . q ) . add ( xq ) ; } function RSADecrypt ( ctext ) { var c = parseBigInt ( ctext , 16 ) ; var m = this . doPrivate ( c ) ; if ( m == null ) return null ; return pkcs1unpad2 ( m , ( this . n . bitLength ( ) + 7 ) >> 3 ) ; } RSAKey . prototype . doPrivate = RSADoPrivate ; RSAKey . prototype . setPrivate = RSASetPrivate ; RSAKey . prototype . setPrivateEx = RSASetPrivateEx ; RSAKey . prototype . generate = RSAGenerate ; RSAKey . prototype . decrypt = RSADecrypt ; var bpe = 0 ; var mask = 0 ; var radix = mask + 1 ; const digitsStr = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_=!@#$%^&*()[]{}|;:,.<>/?`~ \\\'\"+-' ; for ( bpe = 0 ; ( 1 << ( bpe + 1 ) ) > ( 1 << bpe ) ; bpe ++ ) ; bpe >>= 1 ; mask = ( 1 << bpe ) - 1 ; radix = mask + 1 ; const one = int2bigInt ( 1 , 1 , 1 ) ; var t = new Array ( 0 ) ; var ss = t ; var s0 = t ; var s1 = t ; var s2 = t ; var s3 = t ; var s4 = t ; var s5 = t ; var s6 = t ; var s7 = t ; var T = t ; var sa = t ; var mr_x1 = t ; var mr_r = t ; var mr_a = t ; var eg_v = t ; var eg_u = t ; var eg_A = t ; var eg_B = t ; var eg_C = t ; var eg_D = t ; var md_q1 = t ; var md_q2 = t ; var md_q3 = t ; var md_r = t ; var md_r1 = t ; var md_r2 = t ; var md_tt = t ; var primes = t ; var pows = t ; var s_i = t ; var s_i2 = t ; var s_R = t ; var s_rm = t ; var s_q = t ; var s_n1 = t ; var s_a = t ; var s_r2 = t ; var s_n = t ; var s_b = t ; var s_d = t ; var s_x1 = t ; var s_x2 = t ; var s_aa = t ; var rpprb = t ; function findPrimes ( n ) { var i , s , p , ans ; s = new Array ( n ) ; for ( i = 0 ; i < n ; i ++ ) s [ i ] = 0 ; s [ 0 ] = 2 ; p = 0 ; for ( ; s [ p ] < n ; ) { for ( i = s [ p ] * s [ p ] ; i < n ; i += s [ p ] ) s [ i ] = 1 ; p ++ ; s [ p ] = s [ p - 1 ] + 1 ; for ( ; s [ p ] < n && s [ s [ p ] ] ; s [ p ] ++ ) ; } ans = new Array ( p ) ; for ( i = 0 ; i < p ; i ++ ) ans [ i ] = s [ i ] ; return ans ; } function millerRabinInt ( x , b ) { if ( mr_x1 . length != x . length ) { mr_x1 = dup ( x ) ; mr_r = dup ( x ) ; mr_a = dup ( x ) ; } copyInt_ ( mr_a , b ) ; return millerRabin ( x , mr_a ) ; } function millerRabin ( x , b ) { var i , j , k , s ; if ( mr_x1 . length != x . length ) { mr_x1 = dup ( x ) ; mr_r = dup ( x ) ; mr_a = dup ( x ) ; } copy_ ( mr_a , b ) ; copy_ ( mr_r , x ) ; copy_ ( mr_x1 , x ) ; addInt_ ( mr_r , - 1 ) ; addInt_ ( mr_x1 , - 1 ) ; k = 0 ; for ( i = 0 ; i < mr_r . length ; i ++ ) for ( j = 1 ; j < mask ; j <<= 1 ) if ( x [ i ] & j ) { s = ( k < mr_r . length + bpe ? k : 0 ) ; i = mr_r . length ; j = mask ; } else { k ++ ; } if ( s ) { rightShift_ ( mr_r , s ) ; } powMod_ ( mr_a , mr_r , x ) ; if ( ! equalsInt ( mr_a , 1 ) && ! equals ( mr_a , mr_x1 ) ) { j = 1 ; while ( j <= s - 1 && ! equals ( mr_a , mr_x1 ) ) { squareMod_ ( mr_a , x ) ; if ( equalsInt ( mr_a , 1 ) ) { return 0 ; } j ++ ; } if ( ! equals ( mr_a , mr_x1 ) ) { return 0 ; } } return 1 ; } function bitSize ( x ) { var j , z , w ; for ( j = x . length - 1 ; ( x [ j ] == 0 ) && ( j > 0 ) ; j -- ) ; for ( z = 0 , w = x [ j ] ; w ; ( w >>= 1 ) , z ++ ) ; z += bpe * j ; return z ; } function expand ( x , n ) { var ans = int2bigInt ( 0 , ( x . length > n ? x . length : n ) * bpe , 0 ) ; copy_ ( ans , x ) ; return ans ; } function randTruePrime ( k ) { var ans = int2bigInt ( 0 , k , 0 ) ; randTruePrime_ ( ans , k ) ; return trim ( ans , 1 ) ; } function randProbPrime ( k ) { if ( k >= 600 ) return randProbPrimeRounds ( k , 2 ) ; if ( k >= 550 ) return randProbPrimeRounds ( k , 4 ) ; if ( k >= 500 ) return randProbPrimeRounds ( k , 5 ) ; if ( k >= 400 ) return randProbPrimeRounds ( k , 6 ) ; if ( k >= 350 ) return randProbPrimeRounds ( k , 7 ) ; if ( k >= 300 ) return randProbPrimeRounds ( k , 9 ) ; if ( k >= 250 ) return randProbPrimeRounds ( k , 12 ) ; if ( k >= 200 ) return randProbPrimeRounds ( k , 15 ) ; if ( k >= 150 ) return randProbPrimeRounds ( k , 18 ) ; if ( k >= 100 ) return randProbPrimeRounds ( k , 27 ) ; return randProbPrimeRounds ( k , 40 ) ; } function randProbPrimeRounds ( k , n ) { var ans , i , divisible , B ; B = 30000 ; ans = int2bigInt ( 0 , k , 0 ) ; if ( primes . length == 0 ) { primes = findPrimes ( 30000 ) ; } if ( rpprb . length != ans . length ) { rpprb = dup ( ans ) ; } for ( ; ; ) { randBigInt_ ( ans , k , 0 ) ; ans [ 0 ] |= 1 ; divisible = 0 ; for ( i = 0 ; ( i < primes . length ) && ( primes [ i ] <= B ) ; i ++ ) if ( modInt ( ans , primes [ i ] ) == 0 && ! equalsInt ( ans , primes [ i ] ) ) { divisible = 1 ; break ; } for ( i = 0 ; i < n && ! divisible ; i ++ ) { randBigInt_ ( rpprb , k , 0 ) ; while ( ! greater ( ans , rpprb ) ) randBigInt_ ( rpprb , k , 0 ) ; if ( ! millerRabin ( ans , rpprb ) ) { divisible = 1 ; } } if ( ! divisible ) { return ans ; } } } function mod ( x , n ) { var ans = dup ( x ) ; mod_ ( ans , n ) ; return trim ( ans , 1 ) ; } function addInt ( x , n ) { var ans = expand ( x , x . length + 1 ) ; addInt_ ( ans , n ) ; return trim ( ans , 1 ) ; } function mult ( x , y ) { var ans = expand ( x , x . length + y . length ) ; mult_ ( ans , y ) ; return trim ( ans , 1 ) ; } function powMod ( x , y , n ) { var ans = expand ( x , n . length ) ; powMod_ ( ans , trim ( y , 2 ) , trim ( n , 2 ) , 0 ) ; return trim ( ans , 1 ) ; } function sub ( x , y ) { var ans = expand ( x , ( x . length > y . length ? x . length + 1 : y . length + 1 ) ) ; sub_ ( ans , y ) ; return trim ( ans , 1 ) ; } function add ( x , y ) { var ans = expand ( x , ( x . length > y . length ? x . length + 1 : y . length + 1 ) ) ; add_ ( ans , y ) ; return trim ( ans , 1 ) ; } function inverseMod ( x , n ) { var ans = expand ( x , n . length ) ; var s ; s = inverseMod_ ( ans , n ) ; return s ? trim ( ans , 1 ) : null ; } function multMod ( x , y , n ) { var ans = expand ( x , n . length ) ; multMod_ ( ans , y , n ) ; return trim ( ans , 1 ) ; } function randBigInt ( n , s ) { var a , b ; a = Math . floor ( ( n - 1 ) / bpe ) + 2 ; b = int2bigInt ( 0 , 0 , a ) ; randBigInt_ ( b , n , s ) ; return b ; } function GCD ( x , y ) { var xc , yc ; xc = dup ( x ) ; yc = dup ( y ) ; GCD_ ( xc , yc ) ; return xc ; } function GCD_ ( x , y ) { var i , xp , yp , A , B , C , D , q , sing ; if ( T . length != x . length ) { T = dup ( x ) ; } sing = 1 ; while ( sing ) { sing = 0 ; for ( i = 1 ; i < y . length ; i ++ ) if ( y [ i ] ) { sing = 1 ; break ; } if ( ! sing ) break ; for ( i = x . length ; ! x [ i ] && i >= 0 ; i -- ) ; xp = x [ i ] ; yp = y [ i ] ; A = 1 ; B = 0 ; C = 0 ; D = 1 ; while ( ( yp + C ) && ( yp + D ) ) { q = Math . floor ( ( xp + A ) / ( yp + C ) ) ; let qp = Math . floor ( ( xp + B ) / ( yp + D ) ) ; if ( q != qp ) { break ; } t = A - q * C ; A = C ; C = t ; t = B - q * D ; B = D ; D = t ; t = xp - q * yp ; xp = yp ; yp = t ; } if ( B ) { copy_ ( T , x ) ; linComb_ ( x , y , A , B ) ; linComb_ ( y , T , D , C ) ; } else { mod_ ( x , y ) ; copy_ ( T , x ) ; copy_ ( x , y ) ; copy_ ( y , T ) ; } } if ( y [ 0 ] == 0 ) { return ; } t = modInt ( x , y [ 0 ] ) ; copyInt_ ( x , y [ 0 ] ) ; y [ 0 ] = t ; while ( y [ 0 ] ) { x [ 0 ] %= y [ 0 ] ; t = x [ 0 ] ; x [ 0 ] = y [ 0 ] ; y [ 0 ] = t ; } } function inverseMod_ ( x , n ) { var k = 1 + 2 * Math . max ( x . length , n . length ) ; if ( ! ( x [ 0 ] & 1 ) && ! ( n [ 0 ] & 1 ) ) { copyInt_ ( x , 0 ) ; return 0 ; } if ( eg_u . length != k ) { eg_u = new Array ( k ) ; eg_v = new Array ( k ) ; eg_A = new Array ( k ) ; eg_B = new Array ( k ) ; eg_C = new Array ( k ) ; eg_D = new Array ( k ) ; } copy_ ( eg_u , x ) ; copy_ ( eg_v , n ) ; copyInt_ ( eg_A , 1 ) ; copyInt_ ( eg_B , 0 ) ; copyInt_ ( eg_C , 0 ) ; copyInt_ ( eg_D , 1 ) ; for ( ; ; ) { while ( ! ( eg_u [ 0 ] & 1 ) ) { halve_ ( eg_u ) ; if ( ! ( eg_A [ 0 ] & 1 ) && ! ( eg_B [ 0 ] & 1 ) ) { halve_ ( eg_A ) ; halve_ ( eg_B ) ; } else { add_ ( eg_A , n ) ; halve_ ( eg_A ) ; sub_ ( eg_B , x ) ; halve_ ( eg_B ) ; } } while ( ! ( eg_v [ 0 ] & 1 ) ) { halve_ ( eg_v ) ; if ( ! ( eg_C [ 0 ] & 1 ) && ! ( eg_D [ 0 ] & 1 ) ) { halve_ ( eg_C ) ; halve_ ( eg_D ) ; } else { add_ ( eg_C , n ) ; halve_ ( eg_C ) ; sub_ ( eg_D , x ) ; halve_ ( eg_D ) ; } } if ( ! greater ( eg_v , eg_u ) ) { sub_ ( eg_u , eg_v ) ; sub_ ( eg_A , eg_C ) ; sub_ ( eg_B , eg_D ) ; } else { sub_ ( eg_v , eg_u ) ; sub_ ( eg_C , eg_A ) ; sub_ ( eg_D , eg_B ) ; } if ( equalsInt ( eg_u , 0 ) ) { if ( negative ( eg_C ) ) { add_ ( eg_C , n ) ; } copy_ ( x , eg_C ) ; if ( ! equalsInt ( eg_v , 1 ) ) { copyInt_ ( x , 0 ) ; return 0 ; } return 1 ; } } } function inverseModInt ( x , n ) { var a = 1 , b = 0 , t ; for ( ; ; ) { if ( x == 1 ) return a ; if ( x == 0 ) return 0 ; b -= a * Math . floor ( n / x ) ; n %= x ; if ( n == 1 ) return b ; if ( n == 0 ) return 0 ; a -= b * Math . floor ( x / n ) ; x %= n ; } } function inverseModInt_ ( x , n ) { return inverseModInt ( x , n ) ; } function eGCD_ ( x , y , v , a , b ) { var g = 0 ; var k = Math . max ( x . length , y . length ) ; if ( eg_u . length != k ) { eg_u = new Array ( k ) ; eg_A = new Array ( k ) ; eg_B = new Array ( k ) ; eg_C = new Array ( k ) ; eg_D = new Array ( k ) ; } while ( ! ( x [ 0 ] & 1 ) && ! ( y [ 0 ] & 1 ) ) { halve_ ( x ) ; halve_ ( y ) ; g ++ ; } copy_ ( eg_u , x ) ; copy_ ( v , y ) ; copyInt_ ( eg_A , 1 ) ; copyInt_ ( eg_B , 0 ) ; copyInt_ ( eg_C , 0 ) ; copyInt_ ( eg_D , 1 ) ; for ( ; ; ) { while ( ! ( eg_u [ 0 ] & 1 ) ) { halve_ ( eg_u ) ; if ( ! ( eg_A [ 0 ] & 1 ) && ! ( eg_B [ 0 ] & 1 ) ) { halve_ ( eg_A ) ; halve_ ( eg_B ) ; } else { add_ ( eg_A , y ) ; halve_ ( eg_A ) ; sub_ ( eg_B , x ) ; halve_ ( eg_B ) ; } } while ( ! ( v [ 0 ] & 1 ) ) { halve_ ( v ) ; if ( ! ( eg_C [ 0 ] & 1 ) && ! ( eg_D [ 0 ] & 1 ) ) { halve_ ( eg_C ) ; halve_ ( eg_D ) ; } else { add_ ( eg_C , y ) ; halve_ ( eg_C ) ; sub_ ( eg_D , x ) ; halve_ ( eg_D ) ; } } if ( ! greater ( v , eg_u ) ) { sub_ ( eg_u , v ) ; sub_ ( eg_A , eg_C ) ; sub_ ( eg_B , eg_D ) ; } else { sub_ ( v , eg_u ) ; sub_ ( eg_C , eg_A ) ; sub_ ( eg_D , eg_B ) ; } if ( equalsInt ( eg_u , 0 ) ) { if ( negative ( eg_C ) ) { add_ ( eg_C , y ) ; sub_ ( eg_D , x ) ; } multInt_ ( eg_D , - 1 ) ; copy_ ( a , eg_C ) ; copy_ ( b , eg_D ) ; leftShift_ ( v , g ) ; return ; } } } function negative ( x ) { return ( ( x [ x . length - 1 ] >> ( bpe - 1 ) ) & 1 ) ; } function greaterShift ( x , y , shift ) { var i , kx = x . length , ky = y . length , k = ( ( kx + shift ) < ky ) ? ( kx + shift ) : ky ; for ( i = ky - 1 - shift ; i < kx && i >= 0 ; i ++ ) if ( x [ i ] > 0 ) { return 1 ; } for ( i = kx - 1 + shift ; i < ky ; i ++ ) if ( y [ i ] > 0 ) { return 0 ; } for ( i = k - 1 ; i >= shift ; i -- ) if ( x [ i - shift ] > y [ i ] ) { return 1 ; } else if ( x [ i - shift ] < y [ i ] ) return 0 ; return 0 ; } function greater ( x , y ) { var i ; var k = ( x . length < y . length ) ? x . length : y . length ; for ( i = x . length ; i < y . length ; i ++ ) if ( y [ i ] ) { return 0 ; } for ( i = y . length ; i < x . length ; i ++ ) if ( x [ i ] ) { return 1 ; } for ( i = k - 1 ; i >= 0 ; i -- ) if ( x [ i ] > y [ i ] ) { return 1 ; } else if ( x [ i ] < y [ i ] ) { return 0 ; } return 0 ; } function divide_ ( x , y , q , r ) { var kx , ky ; var i , j , y1 , y2 , c , a , b ; copy_ ( r , x ) ; for ( ky = y . length ; y [ ky - 1 ] == 0 ; ky -- ) ; b = y [ ky - 1 ] ; for ( a = 0 ; b ; a ++ ) b >>= 1 ; a = bpe - a ; leftShift_ ( y , a ) ; leftShift_ ( r , a ) ; for ( kx = r . length ; r [ kx - 1 ] == 0 && kx > ky ; kx -- ) ; copyInt_ ( q , 0 ) ; while ( ! greaterShift ( y , r , kx - ky ) ) { subShift_ ( r , y , kx - ky ) ; q [ kx - ky ] ++ ; } for ( i = kx - 1 ; i >= ky ; i -- ) { if ( r [ i ] == y [ ky - 1 ] ) { q [ i - ky ] = mask ; } else { q [ i - ky ] = Math . floor ( ( r [ i ] * radix + r [ i - 1 ] ) / y [ ky - 1 ] ) ; } for ( ; ; ) { y2 = ( ky > 1 ? y [ ky - 2 ] : 0 ) * q [ i - ky ] ; c = y2 >> bpe ; y2 = y2 & mask ; y1 = c + q [ i - ky ] * y [ ky - 1 ] ; c = y1 >> bpe ; y1 = y1 & mask ; if ( c == r [ i ] ? y1 == r [ i - 1 ] ? y2 > ( i > 1 ? r [ i - 2 ] : 0 ) : y1 > r [ i - 1 ] : c > r [ i ] ) { q [ i - ky ] -- ; } else { break ; } } linCombShift_ ( r , y , - q [ i - ky ] , i - ky ) ; if ( negative ( r ) ) { addShift_ ( r , y , i - ky ) ; q [ i - ky ] -- ; } } rightShift_ ( y , a ) ; rightShift_ ( r , a ) ; } function carry_ ( x ) { var i , k , c , b ; k = x . length ; c = 0 ; for ( i = 0 ; i < k ; i ++ ) { c += x [ i ] ; b = 0 ; if ( c < 0 ) { b = - ( c >> bpe ) ; c += b * radix ; } x [ i ] = c & mask ; c = ( c >> bpe ) - b ; } } function modInt ( x , n ) { var i , c = 0 ; for ( i = x . length - 1 ; i >= 0 ; i -- ) c = ( c * radix + x [ i ] ) % n ; return c ; } function int2bigInt ( t , bits , minSize ) { var i , k , buff ; k = Math . ceil ( bits / bpe ) + 1 ; k = minSize > k ? minSize : k ; buff = new Array ( k ) ; copyInt_ ( buff , t ) ; return buff ; } function str2bigInt ( s , base , minSize ) { var d , i , j , x , y , kk ; var k = s . length ; if ( base == - 1 ) { x = new Array ( 0 ) ; for ( ; ; ) { y = new Array ( x . length + 1 ) ; for ( i = 0 ; i < x . length ; i ++ ) y [ i + 1 ] = x [ i ] ; y [ 0 ] = parseInt ( s , 10 ) ; x = y ; d = s . indexOf ( ',' , 0 ) ; if ( d < 1 ) { break ; } s = s . substring ( d + 1 ) ; if ( s . length == 0 ) { break ; } } if ( x . length < minSize ) { y = new Array ( minSize ) ; copy_ ( y , x ) ; return y ; } return x ; } x = int2bigInt ( 0 , base * k , 0 ) ; for ( i = 0 ; i < k ; i ++ ) { d = digitsStr . indexOf ( s . substring ( i , i + 1 ) , 0 ) ; if ( base <= 36 && d >= 36 ) { d -= 26 ; } if ( d >= base || d < 0 ) { break ; } multInt_ ( x , base ) ; addInt_ ( x , d ) ; } for ( k = x . length ; k > 0 && ! x [ k - 1 ] ; k -- ) ; k = minSize > k + 1 ? minSize : k + 1 ; y = new Array ( k ) ; kk = k < x . length ? k : x . length ; for ( i = 0 ; i < kk ; i ++ ) y [ i ] = x [ i ] ; for ( ; i < k ; i ++ ) y [ i ] = 0 ; return y ; } function equalsInt ( x , y ) { var i ; if ( x [ 0 ] != y ) { return 0 ; } for ( i = 1 ; i < x . length ; i ++ ) if ( x [ i ] ) { return 0 ; } return 1 ; } function equals ( x , y ) { var i ; var k = x . length < y . length ? x . length : y . length ; for ( i = 0 ; i < k ; i ++ ) if ( x [ i ] != y [ i ] ) { return 0 ; } if ( x . length > y . length ) { for ( ; i < x . length ; i ++ ) if ( x [ i ] ) { return 0 ; } } else { for ( ; i < y . length ; i ++ ) if ( y [ i ] ) { return 0 ; } } return 1 ; } function isZero ( x ) { var i ; for ( i = 0 ; i < x . length ; i ++ ) if ( x [ i ] ) { return 0 ; } return 1 ; } function bigInt2str ( x , base ) { var i , t , s = "" ; if ( s6 . length != x . length ) { s6 = dup ( x ) ; } else { copy_ ( s6 , x ) ; } if ( base == - 1 ) { for ( i = x . length - 1 ; i > 0 ; i -- ) s += x [ i ] + ',' ; s += x [ 0 ] ; } else { while ( ! isZero ( s6 ) ) { t = divInt_ ( s6 , base ) ; s = digitsStr . substring ( t , t + 1 ) + s ; } } if ( s . length == 0 ) { s = "0" ; } return s ; } function dup ( x ) { var i , buff ; buff = new Array ( x . length ) ; copy_ ( buff , x ) ; return buff ; } function copy_ ( x , y ) { var i ; var k = x . length < y . length ? x . length : y . length ; for ( i = 0 ; i < k ; i ++ ) x [ i ] = y [ i ] ; for ( i = k ; i < x . length ; i ++ ) x [ i ] = 0 ; } function copyInt_ ( x , n ) { var i , c ; for ( c = n , i = 0 ; i < x . length ; i ++ ) { x [ i ] = c & mask ; c >>= bpe ; } } function addInt_ ( x , n ) { var i , k , c , b ; x [ 0 ] += n ; k = x . length ; c = 0 ; for ( i = 0 ; i < k ; i ++ ) { c += x [ i ] ; b = 0 ; if ( c < 0 ) { b = - ( c >> bpe ) ; c += b * radix ; } x [ i ] = c & mask ; c = ( c >> bpe ) - b ; if ( ! c ) return ; } } function rightShift_ ( x , n ) { var i ; var k = Math . floor ( n / bpe ) ; if ( k ) { for ( i = 0 ; i < x . length - k ; i ++ ) x [ i ] = x [ i + k ] ; for ( ; i < x . length ; i ++ ) x [ i ] = 0 ; n %= bpe ; } for ( i = 0 ; i < x . length - 1 ; i ++ ) { x [ i ] = mask & ( ( x [ i + 1 ] << ( bpe - n ) ) | ( x [ i ] >> n ) ) ; } x [ i ] >>= n ; } function halve_ ( x ) { var i ; for ( i = 0 ; i < x . length - 1 ; i ++ ) { x [ i ] = mask & ( ( x [ i + 1 ] << ( bpe - 1 ) ) | ( x [ i ] >> 1 ) ) ; } x [ i ] = ( x [ i ] >> 1 ) | ( x [ i ] & ( radix >> 1 ) ) ; } function leftShift_ ( x , n ) { var i ; var k = Math . floor ( n / bpe ) ; if ( k ) { for ( i = x . length ; i >= k ; i -- ) x [ i ] = x [ i - k ] ; for ( ; i >= 0 ; i -- ) x [ i ] = 0 ; n %= bpe ; } if ( ! n ) { return ; } for ( i = x . length - 1 ; i > 0 ; i -- ) { x [ i ] = mask & ( ( x [ i ] << n ) | ( x [ i - 1 ] >> ( bpe - n ) ) ) ; } x [ i ] = mask & ( x [ i ] << n ) ; } function multInt_ ( x , n ) { var i , k , c , b ; if ( ! n ) { return ; } k = x . length ; c = 0 ; for ( i = 0 ; i < k ; i ++ ) { c += x [ i ] * n ; b = 0 ; if ( c < 0 ) { b = - ( c >> bpe ) ; c += b * radix ; } x [ i ] = c & mask ; c = ( c >> bpe ) - b ; } } function divInt_ ( x , n ) { var i , r = 0 , s ; for ( i = x . length - 1 ; i >= 0 ; i -- ) { s = r * radix + x [ i ] ; x [ i ] = Math . floor ( s / n ) ; r = s % n ; } return r ; } function linComb_ ( x , y , a , b ) { var i , c , k , kk ; k = x . length < y . length ? x . length : y . length ; kk = x . length ; for ( c = 0 , i = 0 ; i < k ; i ++ ) { c += a * x [ i ] + b * y [ i ] ; x [ i ] = c & mask ; c >>= bpe ; } for ( i = k ; i < kk ; i ++ ) { c += a * x [ i ] ; x [ i ] = c & mask ; c >>= bpe ; } } function linCombShift_ ( x , y , b , ys ) { var i , c , k , kk ; k = x . length < ys + y . length ? x . length : ys + y . length ; kk = x . length ; for ( c = 0 , i = ys ; i < k ; i ++ ) { c += x [ i ] + b * y [ i - ys ] ; x [ i ] = c & mask ; c >>= bpe ; } for ( i = k ; c && i < kk ; i ++ ) { c += x [ i ] ; x [ i ] = c & mask ; c >>= bpe ; } } function addShift_ ( x , y , ys ) { var i , c , k , kk ; k = x . length < ys + y . length ? x . length : ys + y . length ; kk = x . length ; for ( c = 0 , i = ys ; i < k ; i ++ ) { c += x [ i ] + y [ i - ys ] ; x [ i ] = c & mask ; c >>= bpe ; } for ( i = k ; c && i < kk ; i ++ ) { c += x [ i ] ; x [ i ] = c & mask ; c >>= bpe ; } } function subShift_ ( x , y , ys ) { var i , c , k , kk ; k = x . length < ys + y . length ? x . length : ys + y . length ; kk = x . length ; for ( c = 0 , i = ys ; i < k ; i ++ ) { c += x [ i ] - y [ i - ys ] ; x [ i ] = c & mask ; c >>= bpe ; } for ( i = k ; c && i < kk ; i ++ ) { c += x [ i ] ; x [ i ] = c & mask ; c >>= bpe ; } } function sub_ ( x , y ) { var i , c , k , kk ; k = x . length < y . length ? x . length : y . length ; for ( c = 0 , i = 0 ; i < k ; i ++ ) { c += x [ i ] - y [ i ] ; x [ i ] = c & mask ; c >>= bpe ; } for ( i = k ; c && i < x . length ; i ++ ) { c += x [ i ] ; x [ i ] = c & mask ; c >>= bpe ; } } function add_ ( x , y ) { var i , c , k , kk ; k = x . length < y . length ? x . length : y . length ; for ( c = 0 , i = 0 ; i < k ; i ++ ) { c += x [ i ] + y [ i ] ; x [ i ] = c & mask ; c >>= bpe ; } for ( i = k ; c && i < x . length ; i ++ ) { c += x [ i ] ; x [ i ] = c & mask ; c >>= bpe ; } } function mult_ ( x , y ) { var i ; if ( ss . length != 2 * x . length ) { ss = new Array ( 2 * x . length ) ; } copyInt_ ( ss , 0 ) ; for ( i = 0 ; i < y . length ; i ++ ) if ( y [ i ] ) { linCombShift_ ( ss , x , y [ i ] , i ) ; } copy_ ( x , ss ) ; } function mod_ ( x , n ) { if ( s4 . length != x . length ) { s4 = dup ( x ) ; } else { copy_ ( s4 , x ) ; } if ( s5 . length != x . length ) { s5 = dup ( x ) ; } divide_ ( s4 , n , s5 , x ) ; } function multMod_ ( x , y , n ) { var i ; if ( s0 . length != 2 * x . length ) { s0 = new Array ( 2 * x . length ) ; } copyInt_ ( s0 , 0 ) ; for ( i = 0 ; i < y . length ; i ++ ) if ( y [ i ] ) { linCombShift_ ( s0 , x , y [ i ] , i ) ; } mod_ ( s0 , n ) ; copy_ ( x , s0 ) ; } function squareMod_ ( x , n ) { var i , j , d , c , kx , kn , k ; for ( kx = x . length ; kx > 0 && ! x [ kx - 1 ] ; kx -- ) ; k = kx > n . length ? 2 * kx : 2 * n . length ; if ( s0 . length != k ) { s0 = new Array ( k ) ; } copyInt_ ( s0 , 0 ) ; for ( i = 0 ; i < kx ; i ++ ) { c = s0 [ 2 * i ] + x [ i ] * x [ i ] ; s0 [ 2 * i ] = c & mask ; c >>= bpe ; for ( j = i + 1 ; j < kx ; j ++ ) { c = s0 [ i + j ] + 2 * x [ i ] * x [ j ] + c ; s0 [ i + j ] = ( c & mask ) ; c >>= bpe ; } s0 [ i + kx ] = c ; } mod_ ( s0 , n ) ; copy_ ( x , s0 ) ; } function trim ( x , k ) { var i , y ; for ( i = x . length ; i > 0 && ! x [ i - 1 ] ; i -- ) ; y = new Array ( i + k ) ; copy_ ( y , x ) ; return y ; } function powMod_ ( x , y , n ) { var k1 , k2 , kn , np ; if ( s7 . length != n . length ) { s7 = dup ( n ) ; } if ( ( n [ 0 ] & 1 ) == 0 ) { copy_ ( s7 , x ) ; copyInt_ ( x , 1 ) ; while ( ! equalsInt ( y , 0 ) ) { if ( y [ 0 ] & 1 ) { multMod_ ( x , s7 , n ) ; } divInt_ ( y , 2 ) ; squareMod_ ( s7 , n ) ; } return ; } copyInt_ ( s7 , 0 ) ; for ( kn = n . length ; kn > 0 && ! n [ kn - 1 ] ; kn -- ) ; np = radix - inverseModInt ( modInt ( n , radix ) , radix ) ; s7 [ kn ] = 1 ; multMod_ ( x , s7 , n ) ; if ( s3 . length != x . length ) { s3 = dup ( x ) ; } else { copy_ ( s3 , x ) ; } for ( k1 = y . length - 1 ; k1 > 0 & ! y [ k1 ] ; k1 -- ) ; if ( y [ k1 ] == 0 ) { copyInt_ ( x , 1 ) ; return ; } for ( k2 = 1 << ( bpe - 1 ) ; k2 && ! ( y [ k1 ] & k2 ) ; k2 >>= 1 ) ; for ( ; ; ) { if ( ! ( k2 >>= 1 ) ) { k1 -- ; if ( k1 < 0 ) { mont_ ( x , one , n , np ) ; return ; } k2 = 1 << ( bpe - 1 ) ; } mont_ ( x , x , n , np ) ; if ( k2 & y [ k1 ] ) { mont_ ( x , s3 , n , np ) ; } } } function mont_ ( x , y , n , np ) { var i , j , c , ui , t , ks ; var kn = n . length ; var ky = y . length ; if ( sa . length != kn ) { sa = new Array ( kn ) ; } copyInt_ ( sa , 0 ) ; for ( ; kn > 0 && n [ kn - 1 ] == 0 ; kn -- ) ; for ( ; ky > 0 && y [ ky - 1 ] == 0 ; ky -- ) ; ks = sa . length - 1 ; for ( i = 0 ; i < kn ; i ++ ) { t = sa [ 0 ] + x [ i ] * y [ 0 ] ; ui = ( ( t & mask ) * np ) & mask ; c = ( t + ui * n [ 0 ] ) >> bpe ; t = x [ i ] ; j = 1 ; for ( ; j < ky - 4 ; ) { c += sa [ j ] + ui * n [ j ] + t * y [ j ] ; sa [ j - 1 ] = c & mask ; c >>= bpe ; j ++ ; c += sa [ j ] + ui * n [ j ] + t * y [ j ] ; sa [ j - 1 ] = c & mask ; c >>= bpe ; j ++ ; c += sa [ j ] + ui * n [ j ] + t * y [ j ] ; sa [ j - 1 ] = c & mask ; c >>= bpe ; j ++ ; c += sa [ j ] + ui * n [ j ] + t * y [ j ] ; sa [ j - 1 ] = c & mask ; c >>= bpe ; j ++ ; c += sa [ j ] + ui * n [ j ] + t * y [ j ] ; sa [ j - 1 ] = c & mask ; c >>= bpe ; j ++ ; } for ( ; j < ky ; ) { c += sa [ j ] + ui * n [ j ] + t * y [ j ] ; sa [ j - 1 ] = c & mask ; c >>= bpe ; j ++ ; } for ( ; j < kn - 4 ; ) { c += sa [ j ] + ui * n [ j ] ; sa [ j - 1 ] = c & mask ; c >>= bpe ; j ++ ; c += sa [ j ] + ui * n [ j ] ; sa [ j - 1 ] = c & mask ; c >>= bpe ; j ++ ; c += sa [ j ] + ui * n [ j ] ; sa [ j - 1 ] = c & mask ; c >>= bpe ; j ++ ; c += sa [ j ] + ui * n [ j ] ; sa [ j - 1 ] = c & mask ; c >>= bpe ; j ++ ; c += sa [ j ] + ui * n [ j ] ; sa [ j - 1 ] = c & mask ; c >>= bpe ; j ++ ; } for ( ; j < kn ; ) { c += sa [ j ] + ui * n [ j ] ; sa [ j - 1 ] = c & mask ; c >>= bpe ; j ++ ; } for ( ; j < ks ; ) { c += sa [ j ] ; sa [ j - 1 ] = c & mask ; c >>= bpe ; j ++ ; } sa [ j - 1 ] = c & mask ; } if ( ! greater ( n , sa ) ) { sub_ ( sa , n ) ; } copy_ ( x , sa ) ; }