from random import randint
import math

def fermat(n):
	x = math.floor(math.sqrt(n))
	y = 0
	factors = []
	if n == x**2:
		factors.append(x)
		return factors
	else:
		x = x + 1
	while True:
		if x == (n + 1) // 2:
			return factors.append(n)
		else:
			y = math.sqrt(x**2 - n)
			if math.floor(y)**2 == (x**2 - n):
				factors.append(x+y)
				factors.append(x-y)
				return factors
			else:
				x = x + 1

def binexp(a, n, mod=1):
	res = 1
	while n != 0:
		if(n&1):
			res = res*a % mod
		a = a*a % mod
		n = n >> 1
	return res

def ftest(n, times):
	result = False
	for i in range(times):
		a = randint(0, n)
		if binexp(a, n, n) == a:
			result = True
		else:
			return(False)
	return(result)
		
if __name__ == "__main__":
	n = 34649*71473
	print(ftest(34649, 11))
	print(ftest(71473, 11))
	print(ftest(n, 11))
	factors = fermat(n);
	print(factors);