// big integer functions


// This function evaluates the given expression
// mainly used in other functions
// 
// inputs
// x - integer as string
// y - integer as string
//
// return values
// 1 - string x is larger
// -1 - string y is larger
// 0 - strings have equal values
//
function bigint_evaluate(s)
{
	var s1,s2	
	var p,c

	if (s.length>1 && s.charAt(0) == "-" && s.charAt(1) == "-")
	{
		return bigint_evaluate(s.substring(2,s.length))
	}

	if (s.length>1 && s.charAt(0) == "(" && s.charAt(s.length-1) == ")")
	{
		return bigint_evaluate(s.substring(1,s.length-1))
	}

	if (s.length>2 && s.charAt(0) == "-" && s.charAt(1) == "(" && s.charAt(s.length-1) == ")")
	{
		return bigint_evaluate(s.substring(2,s.length-1))
	}

	if (s == "-0")
	{
		return "0"
	}

	p=s.length-1
	c=0
	while (p>=0)
	{
		if (s.charAt(p) == ")")
			c = c + 1
		if (s.charAt(p) == "(")
			c = c - 1

		if (s.charAt(p) == "+" && c==0)
		{
			s1 = s.substring(0,p)
			s2 = s.substring(p+1,s.length)
			return bigint_addfloat(bigint_evaluate(s1),bigint_evaluate(s2))
		}

		if (s.charAt(p) == "-" && c==0)
		{
			s1 = s.substring(0,p)
			s2 = s.substring(p+1,s.length)
			return bigint_subfloat(bigint_evaluate(s1),bigint_evaluate(s2))
		}

		p = p - 1
	}

	p=s.length-1
	c=0
	while (p>=0)
	{
		if (s.charAt(p) == ")")
			c = c + 1
		if (s.charAt(p) == "(")
			c = c - 1

		if (s.charAt(p) == "*" && c==0)
		{
			s1 = s.substring(0,p)
			s2 = s.substring(p+1,s.length)
			return bigint_multfloat(bigint_evaluate(s1),bigint_evaluate(s2))
		}

		if (s.charAt(p) == "/" && c==0)
		{
			s1 = s.substring(0,p)
			s2 = s.substring(p+1,s.length)
			return bigint_divfloat(bigint_evaluate(s1),bigint_evaluate(s2))
		}

		if (s.charAt(p) == "d" && c==0)
		{
			s1 = s.substring(0,p-2)
			s2 = s.substring(p+1,s.length)
			return bigint_mod(bigint_evaluate(s1),bigint_evaluate(s2))
		}

		p = p - 1
	}

	p=0
	c=0
	while (p<s.length)
	{
		if (s.charAt(p) == "(")
			c = c + 1
		if (s.charAt(p) == ")")
			c = c - 1

		if (s.charAt(p) == "^" && c==0)
		{
			s1 = s.substring(0,p)
			s2 = s.substring(p+1,s.length)
			return bigint_pow(bigint_evaluate(s1),bigint_evaluate(s2))
		}

		p = p + 1
	}

	return s
}


// This function compares x and y
// mainly used in other functions
// 
// inputs
// x - integer as string
// y - integer as string
//
// return values
// 1 - string x is larger
// -1 - string y is larger
// 0 - strings have equal values
//
function bigint_compare(x,y)
{
	// x positive and y negative
	if (x.charAt(0) != "-" && y.charAt(0) == "-")
		return 1	

	// x negative and y positive
	if (x.charAt(0) == "-" && y.charAt(0) != "-")
		return -1	

	// x negative and y negative
	if (x.charAt(0) == "-" && y.charAt(0) == "-")
		return -1*bigint_compare(x.substring(1,x.length),y.substring(1,y.length))
	
	// Both x and y are positive if we get here
	// If x has more chaacters, x is larger
	if (x.length > y.length)
		return 1

	// If y has more chaacters, y is larger
	if (x.length < y.length)
		return -1

	// Both x and y have the same number of characters
	// We must compare digit by digit
	for (i=0; i<x.length; i++) {
		if (x.charAt(i) > y.charAt(i))
			return 1

		if (x.charAt(i) < y.charAt(i))
			return -1
	}

	return 0
}

function bigint_addfloat(x,y)
{
	var i,i1=0,i2=0
	var xlen,ylen
	var max
	var s,sign,slen
	
	if (x.lastIndexOf('.')>=0)
		i1 = x.length - x.lastIndexOf('.') - 1
	if (y.lastIndexOf('.')>=0)
		i2 = y.length - y.lastIndexOf('.') - 1
	
	if (x.lastIndexOf('.')<0 && y.lastIndexOf('.')<0)
		return bigint_add(x,y)

	max = i1
	if (i2>i1)
		max = i2

	if (x.lastIndexOf('.')>=0)
		x = x.substring(0,x.lastIndexOf('.'))+x.substring(x.lastIndexOf('.')+1)
	if (y.lastIndexOf('.')>=0)
		y = y.substring(0,y.lastIndexOf('.'))+y.substring(y.lastIndexOf('.')+1)


	if (i1<0)
		i1 = 0
	if (i2<0)
		i2 = 0

	for (i=0; i<max-i1; i++)
		x = x + "0"

	for (i=0; i<max-i2; i++)
		y = y + "0"

	s = bigint_add(x,y)
	
	if(s.charAt(0) == "-")
	{
		sign = "-" 	
		s = s.substring(1)
	}

	if (s.length-max>0)
		s = s.substring(0,s.length-max)+"."+s.substring(s.length-max)
	else
	{
		slen = s.length
		for (i=0; i<max-slen; i++)
			s = "0" + s

		s = "0." + s
	}

	if (s.lastIndexOf('.')>=0)
	{
		while (s.charAt(s.length-1) == "0")
			s = s.substring(0,s.length-1)
	}

	while (s.charAt(s.length-1) == ".")
		s = s.substring(0,s.length-1)
	
	if (sign == "-")
		s = sign + s
	
	return s
}

function bigint_subfloat(x,y)
{
	var i,i1=0,i2=0
	var xlen,ylen
	var max
	var s,sign,slen
	
	if (x.lastIndexOf('.')>=0)
		i1 = x.length - x.lastIndexOf('.') - 1
	if (y.lastIndexOf('.')>=0)
		i2 = y.length - y.lastIndexOf('.') - 1
	
	if (x.lastIndexOf('.')<0 && y.lastIndexOf('.')<0)
		return bigint_sub(x,y)

	max = i1
	if (i2>i1)
		max = i2

	if (x.lastIndexOf('.')>=0)
		x = x.substring(0,x.lastIndexOf('.'))+x.substring(x.lastIndexOf('.')+1)
	if (y.lastIndexOf('.')>=0)
		y = y.substring(0,y.lastIndexOf('.'))+y.substring(y.lastIndexOf('.')+1)


	if (i1<0)
		i1 = 0
	if (i2<0)
		i2 = 0

	for (i=0; i<max-i1; i++)
		x = x + "0"

	for (i=0; i<max-i2; i++)
		y = y + "0"

	s = bigint_sub(x,y)
	
	if(s.charAt(0) == "-")
	{
		sign = "-" 	
		s = s.substring(1)
	}

	if (s.length-max>0)
		s = s.substring(0,s.length-max)+"."+s.substring(s.length-max)
	else
	{
		slen = s.length
		for (i=0; i<max-slen; i++)
			s = "0" + s

		s = "0." + s
	}

	if (s.lastIndexOf('.')>=0)
	{
		while (s.charAt(s.length-1) == "0")
			s = s.substring(0,s.length-1)
	}

	while (s.charAt(s.length-1) == ".")
		s = s.substring(0,s.length-1)

	if (sign == "-")
		s = sign + s
	
	return s
}

function bigint_multfloat(x,y)
{
	var i,i1=0,i2=0
	var xlen,ylen
	var max
	var s,sign,slen
	
	if (x.lastIndexOf('.')>=0)
		i1 = x.length - x.lastIndexOf('.') - 1
	if (y.lastIndexOf('.')>=0)
		i2 = y.length - y.lastIndexOf('.') - 1
	
	if (x.lastIndexOf('.')<0 && y.lastIndexOf('.')<0)
		return bigint_mult(x,y)

	max = i1+i2

	if (x.lastIndexOf('.')>=0)
		x = x.substring(0,x.lastIndexOf('.'))+x.substring(x.lastIndexOf('.')+1)
	if (y.lastIndexOf('.')>=0)
		y = y.substring(0,y.lastIndexOf('.'))+y.substring(y.lastIndexOf('.')+1)


	s = bigint_mult(x,y)
	
	if(s.charAt(0) == "-")
	{
		sign = "-" 	
		s = s.substring(1)
	}

	if (s.length-max>0)
		s = s.substring(0,s.length-max)+"."+s.substring(s.length-max)
	else
	{
		slen = s.length
		for (i=0; i<max-slen; i++)
			s = "0" + s

		s = "0." + s
	}

	if (s.lastIndexOf('.')>=0)
	{
		while (s.charAt(s.length-1) == "0")
			s = s.substring(0,s.length-1)
	}

	while (s.charAt(s.length-1) == ".")
		s = s.substring(0,s.length-1)

	if (sign == "-")
		s = sign + s
	
	return s
}

// This function returns the integer part of x/y
// 
// inputs
// x - non negative integer as string
// y - positive integer as string
// d - max digits after decimal point
//
// return value
// p - integer as string
//
function bigint_divfloat(x,y)
{
	var i,i1=0,i2=0
	var xlen,ylen
	var max
	var s,sign,slen
	var d = 20
	
	if (x.lastIndexOf('.')>=0)
		i1 = x.length - x.lastIndexOf('.') - 1
	if (y.lastIndexOf('.')>=0)
		i2 = y.length - y.lastIndexOf('.') - 1
	
//	if (x.lastIndexOf('.')<0 && y.lastIndexOf('.')<0)
//		return bigint_div(x,y)

	max = i1
	if (i2>i1)
		max = i2

	if (x.lastIndexOf('.')>=0)
		x = x.substring(0,x.lastIndexOf('.'))+x.substring(x.lastIndexOf('.')+1)
	if (y.lastIndexOf('.')>=0)
		y = y.substring(0,y.lastIndexOf('.'))+y.substring(y.lastIndexOf('.')+1)

	if (i1<0)
		i1 = 0
	if (i2<0)
		i2 = 0

	for (i=0; i<max-i1+d; i++)
		x = x + "0"

	for (i=0; i<max-i2; i++)
		y = y + "0"

	s = bigint_div(x,y)
	
	if(s.charAt(0) == "-")
	{
		sign = "-" 	
		s = s.substring(1)
	}

	if (s.length-max>0)
		s = s.substring(0,s.length-max)+"."+s.substring(s.length-max)
	else
	{
		slen = s.length
		for (i=0; i<max-slen; i++)
			s = "0" + s

		s = "0." + s
	}

	if (s.lastIndexOf('.')>=0)
	{
		while (s.charAt(s.length-1) == "0")
			s = s.substring(0,s.length-1)
	}

	while (s.charAt(s.length-1) == ".")
		s = s.substring(0,s.length-1)

	if (sign == "-")
		s = sign + s
	
	s = bigint_multfloat(s,"0.00000000000000000001")

	return s
}

// This function returns x+y
// 
// inputs
// x - integer as string
// y - integer as string
//
// return value
// ans - integer as string
//
function bigint_add(x,y)
{
	var maxlen,minlen
	var ans = ""
	var i,d0,d1	
	
	if (x.charAt(0) != "-" && y.charAt(0) == "-")
		return bigint_sub(x,y.substring(1,y.length))	

	if (x.charAt(0) == "-" && y.charAt(0) != "-")
		return bigint_sub(y,x.substring(1,x.length))	

	if (x.charAt(0) == "-" && y.charAt(0) == "-")
		return "-" + bigint_add(x.substring(1,x.length),y.substring(1,y.length))
	
	// x and y are both positive if we get here
	if (x.length > y.length) {
		maxlen = x.length
		minlen = y.length
	}
	else {
		maxlen = y.length
		minlen = x.length
	}

	// we add digit by digit
	d1 = 0
	for (i=0; i<minlen; i++) {
		d0 = x.charAt(x.length-1-i)*1 + y.charAt(y.length-1-i)*1 + d1		
		d1 = (d0-d0%10)/10
		d0 = d0%10
		ans = d0 + ans
	}

	if (x.length > y.length) {
		for (i=maxlen-minlen-1; i>=0; i--) {
			d0 = x.charAt(i)*1 + d1
			d1 = (d0-d0%10)/10
			d0 = d0%10
			ans = d0 + ans
		}
	}
	else {
		for (i=maxlen-minlen-1; i>=0; i--) {
			d0 = y.charAt(i)*1 + d1
			d1 = (d0-d0%10)/10
			d0 = d0%10
			ans = d0 + ans
		}
	}

	if (d1>0)
		ans = d1 + ans

	return ans
}

// This function returns x-y
// 
// inputs
// x - integer as string
// y - integer as string
//
// return value
// ans - integer as string
//
function bigint_sub(x,y)
{
	var maxlen,minlen
	var ans = ""
	var i,d0,d1	
	
	if (x.charAt(0) != "-" && y.charAt(0) == "-")
		return bigint_add(x,y.substring(1,y.length))	

	if (x.charAt(0) == "-" && y.charAt(0) != "-")
		return "-" + bigint_add(x.substring(1,x.length),y)	

	if (x.charAt(0) == "-" && y.charAt(0) == "-")
		return bigint_add(x,y.substring(1,y.length))


	if (bigint_compare(x,y) < 0)
		return "-" + bigint_sub(y,x)

	// x and y are both positive and x>=y if we get here	
	maxlen = x.length
	minlen = y.length

	// we subtract digit by digit
	d1 = 0
	for (i=0; i<maxlen; i++) {
		d0 = x.charAt(x.length-1-i)*1 - y.charAt(y.length-1-i)*1 + d1		
		if (d0<0) {
			d1 = -1
			d0 = d0 + 10
		}
		else d1 = 0
		ans = d0 + ans
	}

	// delete 0s at the beginning of number
	while (ans.charAt(0)==0 && ans.length>1)
		ans = ans.substring(1,ans.length)

	return ans
}

// This function returns x^2
// 
// inputs
// x - integer as string of up to 50000 digits
//
// return value
// p - integer as string
//
function bigint_square(x)
{
	var xlen
	var i,j,k
	var p = ""

	// (-x)^2 = x^2
	if (x.charAt(0) == "-")
		x=x.substring(1,x.length)
	
	var xlen = ((x.length+5)-(x.length+5)%6)/6
	var tlen = 2*xlen

	var prod = new Array(tlen)

	for (k=0; k<xlen; k++)
		prod[2*k+1]=0

	for (k=0; k<xlen; k++)
		prod[2*k] = (x.substring(x.length-6*k-6,x.length-6*k))*(x.substring(x.length-6*k-6,x.length-6*k))

	for (i=0; i<xlen; i++)
		for (j=i+1; j<xlen; j++)
			prod[i+j] = prod[i+j] + 2*(x.substring(x.length-6*i-6,x.length-6*i))*(x.substring(x.length-6*j-6,x.length-6*j))

	for (k=0; k<tlen; k++)
		if (prod[k]>999999) {
			prod[k+1] = prod[k+1] + ((prod[k]-prod[k]%1000000)/1000000)
			prod[k] = prod[k]%1000000
		}		

	if (prod[tlen-1]==0)
		tlen--

	for (k=0; k<tlen-1; k++) {
		p = prod[k] + p
		while (p.length%6>0) p = "0" + p
	}

	p = prod[tlen-1] + p

	// delete 0s at the beginning of number
	while (p.charAt(0)==0 && p.length>1)
		p = p.substring(1,p.length)

	return p
}

// This function returns x*y
// 
// inputs
// x - integer as string of up to 50000 digits
// y - integer as string of up to 50000 digits
//
// return value
// p - integer as string
//
function bigint_mult(x,y)
{
	var xlen,ylen
	var i,j,k
	var p = ""
	var sign = ""

	if (x.charAt(0) == "-" && y.charAt(0) != "-")
		sign = "-"
	if (x.charAt(0) != "-" && y.charAt(0) == "-")
		sign = "-" 

	if (x.charAt(0) == "-")
		x=x.substring(1,x.length)
	if (y.charAt(0) == "-")
		y=y.substring(1,y.length)

	// x and y are both positive here
	// We break number into blocks of 6 digits	
	var xlen = ((x.length+5)-(x.length+5)%6)/6
	var ylen = ((y.length+5)-(y.length+5)%6)/6
	var tlen = xlen+ylen

	var prod = new Array(tlen)


	for (k=0; k<tlen; k++)
		prod[k] = 0

	// main loop
	for (i=0; i<xlen; i++)
		for (j=0; j<ylen; j++)
			prod[i+j] = prod[i+j] + (x.substring(x.length-6*i-6,x.length-6*i))*(y.substring(y.length-6*j-6,y.length-6*j))

	for (k=0; k<tlen; k++)
		if (prod[k]>999999) {
			prod[k+1] = prod[k+1] + ((prod[k]-prod[k]%1000000)/1000000)
			prod[k] = prod[k]%1000000
		}		

	if (prod[tlen-1]==0)
		tlen--

	for (k=0; k<tlen-1; k++) {
		p = prod[k] + p
		while (p.length%6>0) p = "0" + p
	}

	p = prod[tlen-1] + p

	// delete 0s at the beginning of number
	while (p.charAt(0)==0 && p.length>1)
		p = p.substring(1,p.length)

	p = sign + p
	if (p=="-0") p = "0"

	return p
}

// This function returns the integer part of x/y
// 
// inputs
// x - non negative integer as string
// y - positive integer as string
//
// return value
// p - integer as string
//
function bigint_div(x,y)
{
	var xlen,ylen
	var i,d0,f
	var p = "", q = ""
	var f
	var flen

	if (bigint_compare(x,y) < 0)
		return "0"

	xlen = x.length
	ylen = y.length
	
	// the variable f is the first 6 digits of the divisor (or the while divisor if less than 6 digits)
	if (ylen > 6) {
		f = y.substring(0,6)*1
		flen = 6
	}
	else {	
		f = y.substring(0,ylen)*1
		flen = ylen
	}

	q = x.substring(0,ylen-1)

	// main loop, we get one more digit in the quotient each time
	for (i=ylen-1; i<xlen; i++) {
		// get next digit		
		if (bigint_compare(q,"0") > 0)
			q = q + "0"
		q = bigint_add(q, x.charAt(i))
		
		// estimate next digit d0
		if (q.length > ylen) {
			d0 = q.substring(0,flen+1)*1
			d0 = (d0-d0%f)/f
		}
		else {
			d0 = q.substring(0,flen)*1
			d0 = (d0-d0%f)/f
		}		

		q = bigint_sub(q, bigint_mult(y,d0+""))		

		// if  estimate of d0 is too high, keep subtarcting 1
		while (bigint_compare(q, "0") < 0)
		{
			q = bigint_add(q, y)
			d0 = d0 - 1
		}

		p = p + d0
	}

	// delete 0s at the beginning of number
	while (p.charAt(0)==0 && p.length>1)
		p = p.substring(1,p.length)

	return p
}

// This function returns x mod y
// 
// inputs
// x - non negative integer as string
// y - positive integer as string
//
// return value
// q - non negative integer as string
//
function bigint_mod(x,y)
{
	var xlen,ylen
	var i,d0
	var q = ""
	var f
	var flen

	// if x<y x mod y = x
	if (bigint_compare(x,y) < 0)
		return x

	xlen = x.length
	ylen = y.length

	// the variable f is the first 6 digits of the divisor (or the while divisor if less than 6 digits)
	if (ylen > 6) {
		f = y.substring(0,6)*1
		flen = 6
	}
	else {	
		f = y.substring(0,ylen)*1
		flen = ylen
	}

	q = x.substring(0,ylen-1)

	// main loop, we move digit by digit
	for (i=ylen-1; i<xlen; i++) {
		// get next digit
		if (bigint_compare(q,"0") > 0)
			q = q + "0"
		q = bigint_add(q, x.charAt(i))
		
		// estimate next digit d0
		if (q.length > ylen) {
			d0 = q.substring(0,flen+1)*1
			d0 = (d0-d0%f)/f
		}
		else {
			d0 = q.substring(0,flen)*1
			d0 = (d0-d0%f)/f
		}		

		q = bigint_sub(q, bigint_mult(y,d0+""))		

		// if  estimate of d0 is too high, keep subtarcting 1
		while (bigint_compare(q, "0") < 0)
		{
			q = bigint_add(q, y)
			d0 = d0 - 1
		}
	}

	// return the remainder
	return q
}

// This function returns x^y (x to the y power)
// 
// inputs
// x - integer
// y - non negative integer
//
// return value
// p - integer as string
//
function bigint_pow(x,y)
{
	var p = "1"
	var q = "" + x

	// converts y to base 2 and squares to speed up calculation
	while (y > 0) {
		while (y % 2 == 0) {
			y = y / 2
			q = bigint_square(q)
		}
		y = y - 1
		p = bigint_mult(p,q)
	}

	return p
}

// This function returns x^y mod n
// 
// inputs
// x - integer as string
// y - non negative integer as string
// n - positive integer as string
//
// return value
// z - non negative integer as string
//
function bigint_powmod(x, y, n)
{
	var z = "1"

	while (bigint_compare(y,"0") > 0) {
		while (y.charAt(y.length-1) == "0" || y.charAt(y.length-1) == "2" || y.charAt(y.length-1) == "4"
			|| y.charAt(y.length-1) == "6" || y.charAt(y.length-1) == "8") {
			y = bigint_mult(y,"5")
			y = y.substring(0,y.length-1)
			x = bigint_mod(bigint_square(x), n)
		}
		y = bigint_sub(y,"1")
		z = bigint_mod(bigint_mult(z,x), n)
	}
	return z
}

// This function returns the greatest common divisor of x and y
// 
// inputs
// x - integer as string
// y - integer as string
//
// return value
// x - integer as string
//
function bigint_gcd(x, y)
{
	var temp
	
	// the Euclidian algorithm
	while (bigint_compare(y,"0") > 0)
	{
		temp = y
		y = bigint_mod(x,y)
		x = temp
	}

	return x
}

// bigint_modinv(a, b) returns a^-1 mod b
// 
// inputs
// a - integer as string
// b - integer as string
//
// return value
// z - integer as string
//
function bigint_modinv(a, b)
{
	// No modular inverse if gcd(a,b) is not 1
	if (bigint_gcd(a,b) != "1")
		return "does not exist"
	
	// Uses algorithm from Knuth to find the modular inverse
	a = bigint_mod(a,b)	

	u = "1"
	v = "0"
	g = a
	u1 = "0"
	v1 = "1"
	g1 = b
	while (g1 != 0) {
    		q = bigint_div(g,g1) // Integer divide
    		t1 = bigint_sub(u,bigint_mult(q,u1))
		t2 = bigint_sub(v,bigint_mult(q,v1))
		t3 = bigint_sub(g,bigint_mult(q,g1))
    		u  = u1
		v  = v1
		g  = g1
		u1 = t1
		v1 = t2
		g1 = t3
	}
	z = bigint_mod(u,b)
	if (bigint_compare(z, "0") < 0)
		z = bigint_add(z,b)

	return z
}


// pollard rho test
function bigint_pollardrho(n)
{
	var x = "2"
	var y = "2"
	var d = "1"
	var z

	// the Euclidian algorithm
	while (d == "1")
	{
		x = bigint_square(x)
		x = bigint_add(x,"1")
		x = bigint_mod(x,n)

		y = bigint_square(y)
		y = bigint_add(y,"1")
		y = bigint_mod(y,n)
		y = bigint_square(y)
		y = bigint_add(y,"1")
		y = bigint_mod(y,n)

		z = bigint_sub(x,y)
		if (bigint_compare(z,"0") < 0)
			z = bigint_mult(z,"-1")

		d = bigint_gcd(z,n)

		if (bigint_compare(d,"1") > 0)
			return d
	}

	return n
}


// other functions

function gcd(x, y)
{	
	var temp
	
	// the Euclidian algorithm
	while ( y > 0 )
	{
		temp = y
		y = x%y
		x = temp
	}

	return x
}

function factor(n)
{	
	var nn = n, p
	var str = n + " = "
	var Items = 0
	var Count

	if (n == 1) return "1 = 1"

	// Find the number of times primes 2,3,5 go into the number	
 	for (p = 2; p<=5; p++) {	
		if (nn % p  == 0) {
			if (Items > 0) str = str + " * "
			Count = 0
			while (nn % p == 0) {
				Count = Count + 1
				nn = nn / p
			}
			str = str + p
			if (Count > 1) str = str + "^" + Count
			Items = Items + 1
		}
	}

	// Check all non multiples of 2,3,5
	// We do this by checking all primes congruent to 7,11,13,17,19,23,29,1 (mod 30).
	// We check for 7,11,13,17,19,23,29,31 the first time through.
	// Then we increase by 30 and repeat.
	p = 7
	while (nn >= p*p) {

		if (nn % p == 0) {
			if (Items > 0) str = str + " * "
			Count = 0
			while (nn % p == 0) {
				Count = Count + 1
				nn = nn / p
			}
			str = str + p
			if (Count > 1) str = str + "^" + Count			
			Items = Items + 1
		}

		if (nn % (p+4) == 0) {
			if (Items > 0) str = str + " * "
			Count = 0
			while (nn % (p+4) == 0) {
				Count = Count + 1
				nn = nn / (p+4)
			}
			str = str + (p+4)
			if (Count > 1) str = str + "^" + Count			
			Items = Items + 1
		}

		if (nn % (p+6) == 0) {
			if (Items > 0) str = str + " * "
			Count = 0
			while (nn % (p+6) == 0) {
				Count = Count + 1
				nn = nn / (p+6)
			}
			str = str + (p+6)
			if (Count > 1) str = str + "^" + Count			
			Items = Items + 1
		}

		if (nn % (p+10) == 0) {
			if (Items > 0) str = str + " * "
			Count = 0
			while (nn % (p+10) == 0) {
				Count = Count + 1
				nn = nn / (p+10)
			}
			str = str + (p+10)
			if (Count > 1) str = str + "^" + Count			
			Items = Items + 1
		}

		if (nn % (p+12) == 0) {
			if (Items > 0) str = str + " * "
			Count = 0
			while (nn % (p+12) == 0) {
				Count = Count + 1
				nn = nn / (p+12)
			}
			str = str + (p+12)
			if (Count > 1) str = str + "^" + Count			
			Items = Items + 1
		}

		if (nn % (p+16) == 0) {
			if (Items > 0) str = str + " * "
			Count = 0
			while (nn % (p+16) == 0) {
				Count = Count + 1
				nn = nn / (p+16)
			}
			str = str + (p+16)
			if (Count > 1) str = str + "^" + Count			
			Items = Items + 1
		}

		if (nn % (p+22) == 0) {
			if (Items > 0) str = str + " * "
			Count = 0
			while (nn % (p+22) == 0) {
				Count = Count + 1
				nn = nn / (p+22)
			}
			str = str + (p+22)
			if (Count > 1) str = str + "^" + Count			
			Items = Items + 1
		}

		if (nn % (p+24) == 0) {
			if (Items > 0) str = str + " * "
			Count = 0
			while (nn % (p+24) == 0) {
				Count = Count + 1
				nn = nn / (p+24)
			}
			str = str + (p+24)
			if (Count > 1) str = str + "^" + Count			
			Items = Items + 1
		}

		p = p + 30

	}

	if (nn > 1) {
		if (Items > 0) str = str + " * "
		str = str + nn
	}

	return str
}

function primetest(n)
{	
	var p = 7
	var str = n + " = "
	var Items = 0

	if (n == 1) return false
	if (n == 2 || n == 3 || n == 5) return true

	// Check for prime factors of 2,3,5
	if (n%2 == 0 || n%3 == 0 || n%5 == 0) return false

	// Check all non multiples of 2,3,5
	// We do this by checking all primes congruent to 7,11,13,17,19,23,29,1 (mod 30).
	// We check for 7,11,13,17,19,23,29,31 the first time through.
	// Then we increase by 30 and repeat.
	while (n >= p*p) {
		if (n%p == 0 || n%(p+4) == 0 || n%(p+6) == 0 || n%(p+10) == 0 || n%(p+12) == 0 ||
			n%(p+16) == 0 || n%(p+22) == 0 || n%(p+24) == 0) return false

		p = p + 30
	}

	return true
}

function factorCalc(n)
{	
	var nn = n, i = 2
	factorArray = new Array()
	superArray = new Array()
	var Item = 0
	if (n == 1) return "1 = 1"
	
	while (nn > 1) {
		if ((nn > 30) && MRTest(nn, 5)) {
			factorArray[Item] = nn
			superArray[Item] = 1
			Item += 1
			nn = 1
		}
		if (nn % i == 0) {
			factorArray[Item] = i
			var j = getL(i, nn)
			superArray[Item] = j
			Item += 1
			nn = nn / Math.pow(i, j)
		}
		i = nextPrime(i)
	}

	var str = " = "
	for ( i = 0; i <= Item - 1; i ++ ) {
		for (var j = 0; j <= superArray[i] - 1; j ++ ) {
			str = str + factorArray[i]
			if (j < superArray[i] - 1) str = str + " * "
		}
		if (i < Item - 1) str = str + " * "
	}
	return str
}


function relativePrime(x, y)
{	if (gcd(x, y) == 1) return true
	else return false
}

function mod(a, b)
{
	var len
	var m,t  
	var i

	//if (a<100000000000000 && b<100000000000000)
	//	return a%b

	len = a.length

	m = a.charAt(0)
	m = m*1

	for (i=1; i<len; i++) {
		m = m*10		
		t = a.charAt(i)
		t = t*1
		m = m + t
		m = m % b
	}

	return m
}

function mult1(x,y)
{
	var xlen,ylen
	var i,j,k
	var p = ""

	var xlen = x.length
	var ylen = y.length
	var tlen = xlen+ylen

	var prod = new Array(tlen)

	for (k=0; k<tlen; k++)
		prod[k] = 0

	for (i=0; i<xlen; i++)
		for (j=0; j<ylen; j++)
			prod[i+j] = prod[i+j] + (x.charAt(xlen-i-1))*(y.charAt(ylen-j-1))

	for (k=0; k<tlen; k++)
		if (prod[k]>9) {
			prod[k+1] = prod[k+1] + ((prod[k]-prod[k]%10)/10)
			prod[k] = prod[k]%10
		}		

	if (prod[tlen-1]==0)
		tlen--

	for (k=0; k<tlen; k++)
		p = prod[k] + p
		
	return p
}

function mult2(x,y)
{
	var p, a, b, t

	var pow7=10000000
	var pow14=pow7*pow7
				
	b = (x%pow7)*(y%pow7)

	t = (x%pow7)*(y-y%pow7)/pow7 + (y%pow7)*(x-x%pow7)/pow7		

	a = ((x-x%pow7)/pow7) * ((y-y%pow7)/pow7)
				
	b = b + (t%pow7)*pow7 				
	a = a + (t-t%pow7)/pow7 				

	if (b>=pow14) {
		a = a + (b-b%pow14)/pow14
		b = b%pow14
	}
	
	p = "" + b

	while (a>0 && p.length<14)
		p = "0" + p

	if (a>0)
		p = a + p
	
	return p
}

function mod_old(x, n)
{	if (n < 0) {
		alert("Wrong input for n!")
		return -1
	}
	var temp = x % n
	if (temp < 0) temp += n
	return temp
}

function powmod(x, y, n)
{
	var z = 1

	while (y != 0) {
		while (y % 2 == 0) {
			y = y / 2
			x = mod(x * x, n)
		}
		y = y - 1
		z = mod(z * x, n)
	}
	return z
}

function powmod2(x, y, n)
{	var z = 1
	if (x == 0 && y == 0) {return -1}
	if (y == 0 ) {return 1}
	if (y > 0) { return powmod(x, y, n) }
	else {
		var invx = inverse(x, n)
		if (invx == 0) { return n }
		else {return powmod(invx, -y, n)}
	}
}

function inverse(b, n)
{	b = mod(b, n)	
	var bb = b, nn = n, tt = 0, t = 1
	var q = Math.floor ( nn / bb )
	var r = nn - q * bb
	while (r > 0) {
		var temp = tt - q * t
		if (temp >= 0) { temp = mod(temp, n) }
		else  { temp = n - mod((-temp), n) }
		tt = t
		t = temp
		nn = bb
		bb = r
		q  = Math.floor ( nn / bb )
		r = nn - q * bb
	}
	if (bb != 1) { return 0 }
	else { return(mod(t, n)) }
}

function isEven(n)
{	if (n % 2 == 0) return true
	else return false
}

function getL(m, n)
{	var nn = n, L = 0
	while (nn % m == 0) {
		nn = nn / m
		L += 1
	}
	return L
}

function MRTest(n, t)
{	if ( n == 1 )  return false 
	var k = n - 1
	var L = getL(2, k)
	var m = k / Math.pow(2, L)
	if (L == -1) {alert("Wrong input, even n!")
		return -1
	}
	
	var x0
	var x = 1 + Math.floor(Math.random() * k )
	while(x == n) {x = 1 + Math.floor(Math.random() * k )}
		
	x0 = powmod(x, m, n)
	if ( x0 == 1 || x0 == k ) {
		if( t == 0 ) return true
		else return MRTest(n, t - 1)
	}
	
	var xold = x0, xnew
	for ( var i = 1; i <= L; i ++ ) {
		xnew = powmod(xold, 2, n)
		if (xnew == k) { 
			if ( t == 0 )return true
			else return MRTest(n, t - 1) }
		else if (xnew == 1){ return false }
		xold = xnew
	}
	return false	
}

function nextPrime(n)
{	var i = 2;
	if ( n == 1 ) return 2
	if ( n % 2 == 0) n = n - 1
	while(!MRTest(n + i, 5)){i = i + 2}
	return (n + i)
}

function factorold(n)
{	
	var nn = n, i = 2
	factorArray = new Array()
	superArray = new Array()
	var Item = 0
	if (n == 1) return "1 = 1"
	
	while (nn > 1) {
		if ((nn > 30) && MRTest(nn, 5)) {
			factorArray[Item] = nn
			superArray[Item] = 1
			Item += 1
			nn = 1
		}
		if (nn % i == 0) {
			factorArray[Item] = i
			var j = getL(i, nn)
			superArray[Item] = j
			Item += 1
			nn = nn / Math.pow(i, j)
		}
		i = nextPrime(i)
	}

	var str = n + " = "
	for ( i = 0; i <= Item - 1; i ++ ) {
		for (var j = 0; j <= superArray[i] - 1; j ++ ) {
			str = str + factorArray[i]
			if (j < superArray[i] - 1) str = str + " * "
		}
		if (i < Item - 1) str = str + " * "
	}
	return str
}