Jump to content
  • Advertisement
Sign in to follow this  
ktuluorion

Carmichael Numbers and Primality Testing

This topic is 3881 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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!