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 &gt; 1 and args.possible_prime % 2 == 1:
        print(fermat_witness_liar_count(args.possible_prime))
    else:
        print("Please enter an odd integer &gt; 1.")


def fermat_witness_liar_count(possible_prime):
    """Counts the amount of Fermat witnesses and liars
    for a number 1 &lt;= test_num &lt;= possible_prime.
    Basic usage:
    &gt;&gt;&gt; fermat_witness_liar_count(3)
    (0, 0)
    &gt;&gt;&gt; fermat_witness_liar_count(9)
    (6, 2)
    &gt;&gt;&gt; fermat_witness_liar_count(31)
    (0, 0)
    &gt;&gt;&gt; fermat_witness_liar_count(33)
    (28, 4)
    &gt;&gt;&gt; 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:
    &gt;&gt;&gt; fermat_witness(2, 3)
    False
    &gt;&gt;&gt; fermat_witness(8, 9)
    False
    &gt;&gt;&gt; fermat_witness(30, 31)
    False
    &gt;&gt;&gt; fermat_witness(3, 33)
    True
    &gt;&gt;&gt; fermat_witness(6, 437)
    True
    """

    if pow(test_num, possible_prime-1) % possible_prime != 1:
        # test_num is a Fermat witness, possible_prime composite
        return True

    # possible_prime may be prime
    return False


if __name__ == '__main__':
    import doctest
    doctest.testmod()
    main()
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.