Carmichael Numbers and Primality Testing
Author
Hey all..
So I have an assignment to do some simple primality testing. It seems to work for all the primes and composites, but for some reason Carmichael numbers seem to evaluate to composite. I was pretty sure that the point of a Carmichael number is that when you try Fermat's theorem on it, it evalutes to prime even though it's not.
Can anyone confirm if this should be happening or not?
Thanks!
Certain numbers (pseudoprimes) will pass a probabilistic primality test even though they aren't prime. If you want to be 100% sure, you'll need to switch to a deterministic algorithm once your probabilistic test identifies a number as a probable prime.
Author
Good point ;) I forgot this forum existed. I just remembered that GDNet knows everything.
:)
:)
Quote:Original post by ktuluorion
So I have an assignment to do some simple primality testing. It seems to work for all the primes and composites, but for some reason Carmichael numbers seem to evaluate to composite. I was pretty sure that the point of a Carmichael number is that when you try Fermat's theorem on it, it evalutes to prime even though it's not.
That is correct. A Carmichael number n is one that will pass a test of Fermat's theorem for any base that is relatively prime with n.
If your test is identifying a Carmichael number n as composite, can you post n and what base you are trying?
Quote:Original post by ktuluorion
Good point ;) I forgot this forum existed. I just remembered that GDNet knows everything.
:)
Be careful...your post here is okay but this is NOT a forum that is here to help with homework or schoolwork. In fact, there is a strict policy about it, which you should review at the Forum FAQ. As moderator, I am given the authority to make judgement calls and if I believe a post is inappropriate, I will close it.
Author
Quote:Original post by grhodes_at_workQuote:Original post by ktuluorion
Good point ;) I forgot this forum existed. I just remembered that GDNet knows everything.
:)
Be careful...your post here is okay but this is NOT a forum that is here to help with homework or schoolwork. In fact, there is a strict policy about it, which you should review at the Forum FAQ. As moderator, I am given the authority to make judgement calls and if I believe a post is inappropriate, I will close it.
Yes, i'm aware of that policy. I'm really not asking the question that is at the heart of the assignment, it's more of an aside.
The reason it is identifying it as composite sometimes is because I am using all a (from 1-p), so some of them are not relatively prime.
Thanks everyone. The professor actually ended up confirming my suspicion.. I had taken cryptology in the past but forgot the properties of carmichael numbers.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement