Miller Rabin Notorious Liar Identification

mrliar.py

import multiprocessing
import multiprocessing.pool
import time

class TimeMeasurement(object):
	def __init__(self, operation, printStd=True):
		self._t0 = 0
		self._t1 = 0
		
		self._operation = operation
		self._printStd = printStd
	
	@property
	def delta(self):
		return self._t1 - self._t0
	
	def __enter__(self):
		self._t1 = 0
		self._t0 = time.perf_counter()
		
		return self
	
	def __exit__(self, *args):
		self._t1 = time.perf_counter()
		
		if self._printStd:
			print('Operation \'{!s}\' took {:.4f} s'.format(self._operation, self.delta))


def is_prime(n):
	if n < 2:
		return False
	
	if n % 2 == 0:
		return n == 2
	
	k = 3
	while (k * k) <= n:
		if (n % k) == 0:
			return False
		
		k += 2
	
	return True


def get_liars(n):
	liarsStats = {}
	
	m = 0
	n_less = n - 1
	n_test = n_less
	certIsPrime = is_prime(n)
	
	while (n_test % 2) == 0:
		n_test = n_test // 2
		m += 1
	
	d = n_less // 2**m
	
	numLiars = 0
	
	for a in range(1, n):
		mrTest = pow(a, d, n)
		mrIsPrime = (mrTest == 1) or (mrTest == n_less)
		
		if mrIsPrime and not certIsPrime:
			numLiars += 1
			
			if a not in liarsStats:
				liarsStats[a] = 0
			
			liarsStats[a] += 1
		
	return liarsStats
	
def main_parallel(limit=1e4, tops=10, chunksize=10):
	limit = int(limit)
	tops = int(tops)
	chunksize = int(chunksize)
	liarsStats = {}
	
	with multiprocessing.pool.Pool() as pool:
		print('Using {:d} processes'.format(len(pool._pool)))
		
		liarsStatsRaw = pool.map(get_liars, range(3, limit, 2), chunksize)
		
		for liarsStatsChunk in liarsStatsRaw:
			for liar in liarsStatsChunk:
				if liar not in liarsStats:
					liarsStats[liar] = 0
				
				liarsStats[liar] += liarsStatsChunk[liar]
		
	sortedLiars = sorted(liarsStats.items(), key=lambda item: item[1], reverse=True)
	
	print("Top {:d} liars for n up to n = {:d}".format(tops, limit))
	
	for liar in sortedLiars[:tops]:
		print("Liar {:d} - {:d}".format(liar[0], liar[1]))
	
def main_linear(limit=1e4, tops=10):
	limit = int(limit)
	tops = int(tops)
	liarStats = {}
	
	for n in range(3, limit, 2):
		# print("n = {:d}".format(n))
		
		m = 0
		n_test = n - 1
		isPrime_Fac = is_prime(n)
		
		# print("\tn_test = {}".format(n_test))
		
		while (n_test % 2) == 0:
			n_test = n_test // 2
			m += 1
		
		d = (n - 1) // 2**m
		# print("\td = {:d}; m = {:d}".format(d, m))
		
		numLiar = 0
		
		for a in range(1, n):
			mrTest = pow(a, d, n)
			isPrime_MR = (mrTest == 1) or (mrTest == (n - 1))
			
			# print("\ta = {:d}; mrTest = {:d}".format(a, mrTest))
			
			if isPrime_MR and not isPrime_Fac:
				numLiar += 1
				
				if a in liarStats:
					liarStats[a] += 1
				else:
					liarStats[a] = 1
				
				# print("\t{:d} is a liar for {:d}".format(a, n))
			
			# print("\t{:d} liars for n = {:d}".format(numLiar, n))
	
	sortedLiars = sorted(liarStats.items(), key=lambda item: item[1], reverse=True)
	
	print("Top {:d} liars for n up to n = {:d}".format(tops, limit))

	for liar in sortedLiars[:tops]:
		print("Liar {:d} - {:d}".format(liar[0], liar[1]))


if __name__ == '__main__':
	n = int(1e4)
	
	print('Miller Rabin Liar identification up to n = {:d}'.format(n))
	print('')
	
	print('Parallel')
	with TimeMeasurement('Parallel Miller Rabin Liar Identification for n = {:d}'.format(n)):
		main_parallel(n)
	
	print('')
	print('Standard')
	with TimeMeasurement('Linaer Miller Rabin Liar Identification for n = {:d}'.format(n)):
		main_linear(n)