/*function that implements the basic primality test if witness does not return is definitely composite do this by computing (mod nand looking for non-trivial square roots of along the way *hugeint witnessconst hugeint aconst hugeint iconst hugeint ifi = return hugeint witnessai )ifx = /if is recursively compositestop return / is not prime if we find non-trivial square root of hugeint nify = & ! & ! return ifi ! nreturn /*the number of witnesses queried in randomized primality test *const int trials /*randomized primality test adjust trials to increase confidence level is the number to test if return value is falsen is definitely not prime if return value is truen is probably prime *bool isprimeconst hugeint random rforint counter counter trials++counter ifwitnessr randomhugeint ) ! return falsereturn truefigure probabilistic primality testing algorithm