@CogitoErgoCogitoSum Yes, but Carmichael numbers are rare. There's only 2,163 Carmichael numbers less than 25,000,000,000, and they get rarer as the numbers get bigger. If you are testing a large number for primality, I'd say the odds you happened to pick a Carmichael number are less than getting twenty false reads from the primality test. The test didn't promise 100% certainty, just 99.9999%, right?
@@zanti4132 There is that. But you really don't want an adversarial number that always passes when it should fail. That should be "bad luck" with the test rather than "bad luck" with the number chosen.
As the gcd(5,6) = 1, but 6 is not prime. You would need to generate the values of all the integers less than p and test the gcd for all of them and if all their values are 1. Then, it is a prime. But, that is a much slower method.
@@medhanshkhandelwal6339 that is Fermats method. It's just that the we don't check all of them, but rather random ones. GCD (1,6) = 1 GCD (2,6) = 2 GCD (3,6) = 3 GCD (4,6) = 2 GCD (5,6) = 1 And we'll, this is the definition of prime. If a number has a non one GCD, they have a common factor, meaning the prime has a factor, which means it's not prime.
May I ask why do we have to check for the GCD? That operation will be very time consuming if we are dealing with arbitrarily large numbers, besides, doesn't Fermat equation tell you whether the number is primary or not regardless of what the GCD is?
The GCD of two numbers, a and b, can be calculated in O(log (ab)) steps using Euclid's algorithm. The constraints for Fermat's theorem are that a and b must be coprime. If the number under consideration is prime, then GCD(, ) will always be 1. Now if GCD(a, b) is 1, then we proceed with the Primality test. Calculating (a exp ( b - 1 ) mod b) requires log (b - 1 ) as well. So yea, I don't think there is much difference in time consumption.
6:43 ..... Should Fermat test say prime? It may wrongly say it's prime but not say it's composite by error (Believing that the trial division successfully determined it to be prime after all those millions of steps)
Can someone explain me why the number 561 (Carmichael number) is supposed to fool this primality test but: 75^560 mod 561 = 375? So this would tell us that is not prime, and it is not, but it is Carmichael
A Carmichael number (n) is a composite number that satisfies the condition: (C exp (n - 1)) % n = 1. But in Fermat's primality test, the prerequisite is to check for the GCD as well. GCD(75, 561) = 3 ( not equal to 1). So hence, we will not proceed with this test as we'd already get GCD not equal to 1, and hence, we'd dismiss the number 561 as composite. So How does this Carmichael number fool the Fermat Primality test? If we randomly generate a number between 2 and (n -1), if we get the GCD as 1, let's say C = 2, 4, 5, 7, 8 ... . We get GCD( C, n) as 1 And when we find C exp (n-1) % n , we still get 1. This suggests that n is prime, which it really isn't.
I think I was able to tweak a version of this in python. If you guys may be interested in that, i could probably sell it to you. Normally, I would like to just share what I've found, but I've been out of work for several months and really need something. I do have some videos of it on my channel here. It does seem to really no longer have problems with Carmichael numbers at all.
one of the best explanations ive ever seen on this theme, thank you
I really enjoyed this video! Definitely deserves more views and likes. Thank you!
bro wtf why did you end on a cliffhanger? I know its Carmichael numbers but I need to know more!!!
Fermat? More like Fantastic! 👍
There is a new primality test that is becoming popular. It's made by primorial and demonstrated by Vinc'S Theorem.
What do you mean? Is Vinc's theorem a new way to check for primarlity which can be even more efficient than this one?
@@jannismilz the Fermat primality test is probabilistic (there is uncertainty). Vinc'S primality test is deterministic even if slower.
@@VincenzoSambito Ah okay interesting, thanks
Merci beaucoup, tu connais Théorème de BKD
Actually... 5:48 should say "just under 1 in a million" or "1 in just over million". NBD. But seriously, the video was helpful.
So what's the flaw???
@CogitoErgoCogitoSum Yes, but Carmichael numbers are rare. There's only 2,163 Carmichael numbers less than 25,000,000,000, and they get rarer as the numbers get bigger. If you are testing a large number for primality, I'd say the odds you happened to pick a Carmichael number are less than getting twenty false reads from the primality test. The test didn't promise 100% certainty, just 99.9999%, right?
@@zanti4132
There is that. But you really don't want an adversarial number that always passes when it should fail. That should be "bad luck" with the test rather than "bad luck" with the number chosen.
If gcd(a,p)=1
Why can't we conclude p is prime
Why do we need to check weather the Fermat's theorem holds.since we are using the same base a
As the gcd(5,6) = 1, but 6 is not prime. You would need to generate the values of all the integers less than p and test the gcd for all of them and if all their values are 1. Then, it is a prime. But, that is a much slower method.
@@medhanshkhandelwal6339 that is Fermats method.
It's just that the we don't check all of them, but rather random ones.
GCD (1,6) = 1
GCD (2,6) = 2
GCD (3,6) = 3
GCD (4,6) = 2
GCD (5,6) = 1
And we'll, this is the definition of prime. If a number has a non one GCD, they have a common factor, meaning the prime has a factor, which means it's not prime.
May I ask why do we have to check for the GCD? That operation will be very time consuming if we are dealing with arbitrarily large numbers, besides, doesn't Fermat equation tell you whether the number is primary or not regardless of what the GCD is?
The GCD of two numbers, a and b, can be calculated in O(log (ab)) steps using Euclid's algorithm.
The constraints for Fermat's theorem are that a and b must be coprime.
If the number under consideration is prime, then GCD(, ) will always be 1.
Now if GCD(a, b) is 1, then we proceed with the Primality test. Calculating (a exp ( b - 1 ) mod b) requires log (b - 1 ) as well.
So yea, I don't think there is much difference in time consumption.
6:43 .....
Should Fermat test say prime? It may wrongly say it's prime but not say it's composite by error
(Believing that the trial division successfully determined it to be prime after all those millions of steps)
Can someone explain me why the number 561 (Carmichael number) is supposed to fool this primality test but:
75^560 mod 561 = 375?
So this would tell us that is not prime, and it is not, but it is Carmichael
A Carmichael number (n) is a composite number that satisfies the condition:
(C exp (n - 1)) % n = 1.
But in Fermat's primality test, the prerequisite is to check for the GCD as well.
GCD(75, 561) = 3 ( not equal to 1).
So hence, we will not proceed with this test as we'd already get GCD not equal to 1, and hence, we'd dismiss the number 561 as composite.
So How does this Carmichael number fool the Fermat Primality test?
If we randomly generate a number between 2 and (n -1), if we get the GCD as 1, let's say C = 2, 4, 5, 7, 8 ... . We get GCD( C, n) as 1
And when we find C exp (n-1) % n , we still get 1. This suggests that n is prime, which it really isn't.
@1:21 ... a^p = a mod p? how?
...that's the Fermat's theorem
nice cliffhanger... whats the flaw cmon
Carmichael numbers
I think I was able to tweak a version of this in python. If you guys may be interested in that, i could probably sell it to you. Normally, I would like to just share what I've found, but I've been out of work for several months and really need something. I do have some videos of it on my channel here. It does seem to really no longer have problems with Carmichael numbers at all.
ppap Pen-Pineapple-Apple-Pen