Sign in to follow this  

Carmichael Numbers and Primality Testing

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
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 this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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.

Share this post


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


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.

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this