# Carmichael Numbers and Primality Testing

This topic is 3974 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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!

##### Share on other sites
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.

##### Share on other sites
Would this be more useful in "maths and physics"?

Done

##### Share on other sites
Good point ;) I forgot this forum existed. I just remembered that GDNet knows everything.
:)

##### Share on other sites
Quote:
 Original post by ktuluorionSo 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?

##### Share on other sites
Quote:
 Original post by ktuluorionGood 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.

##### Share on other sites
Quote:
Original post by grhodes_at_work
Quote:
 Original post by ktuluorionGood 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.

1. 1
Rutin
46
2. 2
3. 3
4. 4
5. 5
JoeJ
19

• 11
• 15
• 9
• 10
• 13
• ### Forum Statistics

• Total Topics
633004
• Total Posts
3009836
• ### Who's Online (See full list)

There are no registered users currently online

×