def AKS(n):
	for a in range(2,pari(sqrt(n)).floor()+1):
		for b in range(2,pari(sqrt(n)).floor()+1):
			if (n==a^b):
				return 'composite'
	r=2
	m=pari(4*log(n,2))^2.floor()+1
	while(r<n):
		if(Mod(n,r)==0):
			return 'composite'		
		if (is_prime(r)==True):
			for i in range(1,m):
				if(power_mod(n,i,r)!=1):
					break
		r=r+1
	if(r==n):
		return 'prime'
	n=pari(2*sqrt(r)*log(n,2)+1).floor()
	for a in range(1,n):
		R=PolynomialRing(Integers(n))
		x=R.gen()
		S=R.quotient((x^r)-1)
		c=S((x+a)^n)
		e=Mod(n,r)
		d=(x^e)+a
		if (c!=d):
			return 'composite'
	return 'prime'