Fermat test (test for simplicity)
Function for checking the number for simplicity by Fermat's small theorem:
import math
import random
def is_prime(num, test_count):
for i in range(test_count):
rnd = random.randint(1, num - 1)
if (rnd ** (num - 1) % num != 1):
return False
return True
print(is_prime(13, 10))
It is said that you need to perform a larger number of tests so that the result is more accurate (so that you are less likely to stumble upon "tricksters" of Fermat).
Rod Stevenson's book Algorithms says: "..for a natural number p, at least half of the values of n between 1 and p are Fermat's witnesses... You may get unlucky and take as n the trickster Farm...
The question itself: I ran tests and did not find these "tricksters" of Fermat in any way... Except for the actual number 1. How do I "stumble" on this number, or am I doing something wrong?
1 answers
You see, you were told that there were at least 50% of witnesses. This is score from below, i.e. if there are cheaters, then there are no more than 50% of them. For example, 0.0001%. Or not at all - this is also less than 50% :) By the way, I have some doubts about the 50% estimate - there are, for example, Carmichael numbers, where this value, as far as I remember, is much higher...
The simplest deceivers are 4, 11, 14 for the number 15. 3 pieces, about 20%. The following cheaters are only for 21, for all there are no intermediate ones.
For 91 = 7 * 13, there are 35 of them, more than 38%.
So there are scammers, you're just unlucky enough to stumble upon them.
Look for yourself at p = 561 or 1105, how many cheaters there are.
P.S. I'm not strong in Python, how is it with a range of integer values? and then it's one thing to build a 10 to 12 degree, and quite another - 300 to 500... You would have made a loop just in case, but in the loop you calculated the exponentiation modulo.