Counting Fermat witnesses and liars

We were asked to implement a program that calculates the number of Fermat witnesses and liars for odd numbers greater 1. This involves Fermat’s little theorem.

Fermat’s little is used to identify whether a possible prime number is composite. It’ll find a number/numbers called Fermat witness then. The other numbers are Fermat liars unless Fermat’s little doesn’t find any witness. Then the number is possibly prime.

```
# coding=utf-8

"""Basic usage:
$ python fermat.py 7
(0, 0)
$ python fermat.py 9
(6, 2)
"""

import argparse

def main():
"""Prints out the results of fermat_witness_liar_count().
fermat_witness_liar_count() takes a non-optional integer as an argument.
"""

parser = argparse.ArgumentParser()
parser.add_argument('possible_prime', type=int)
args = parser.parse_args()

if args.possible_prime > 1 and args.possible_prime % 2 == 1:
print(fermat_witness_liar_count(args.possible_prime))
else:
print("Please enter an odd integer > 1.")

def fermat_witness_liar_count(possible_prime):
"""Counts the amount of Fermat witnesses and liars
for a number 1 >> fermat_witness_liar_count(3)
(0, 0)
>>> fermat_witness_liar_count(9)
(6, 2)
>>> fermat_witness_liar_count(31)
(0, 0)
>>> fermat_witness_liar_count(33)
(28, 4)
>>> fermat_witness_liar_count(437)
(432, 4)
"""

witness_count = 0
liar_count = 0
temp_liar_count = 0

for test_num in range(1, possible_prime):
if fermat_witness(test_num, possible_prime):
witness_count += 1
else:
temp_liar_count += 1

# When there are Fermat witnesses, all test_num’s that aren’t are Fermat liars
if witness_count != 0:
liar_count = temp_liar_count

return witness_count, liar_count

def fermat_witness(test_num, possible_prime):
"""Basic usage:
>>> fermat_witness(2, 3)
False
>>> fermat_witness(8, 9)
False
>>> fermat_witness(30, 31)
False
>>> f

I think it would be worth explaining the terms you are using : what is a liar ? what is a witness ?

Except for that, the code is well presented and well tested (so many thanks for that).

Making code more simple in fermat_witness

You could easily rewrite fermat_witness: return pow(test_num, possible_prime-1) % possible_prime != 1.

Making code more simple in fermat_witness_liar_count

You could also rewrite fermat_witness_liar_count with less variables because you can get rid of liar_count by writing :

if witness_count != 0:
    return witness_count, temp_liar_count
return 0, 0

You can also get rid of temp_liar_count by writing :

witness_count = 0
for test_num in range(1, possible_prime):
    if fermat_witness(test_num, possible_prime):
        witness_count += 1
if witness_count != 0:
    return witness_count, possible_prime - witness_count - 1
return 0, 0

Then, you can use the fact that non-zero integers are considered as true values and try to write a single return:

return witness_count, possible_prime - witness_count - 1 if witness_count else 0

Finally, if you want to count, you can use sum and simply write :

witness_count = sum(1 for test_num in range(1, possible_prime)
    if fermat_witness(test_num, possible_prime))

The whole function becomes :

witness_count = sum(1 for test_num in range(1, possible_prime)
    if fermat_witness(test_num, possible_prime))

# When there are Fermat witnesses, all test_nums that arent are Fermat liars
return witness_count, possible_prime - witness_count - 1 if witness_count else 0

pow is a pow-erful builtin

pow handles what you are trying to do in a more efficient way :


if z is present, return x to the power y, modulo z (computed more
efficiently than pow(x, y) % z)

fermat_witness becomes :

return pow(test_num, possible_prime-1, possible_prime) != 1

Then, I guess more mathematical optimisations could be performed but I haven't tried at all.

StackExchange Code Review Q#70995, answer score: 7