primility testing
I hope somebody can help me:
I have a number ( approx. 1520 digits) and i try to trial factor it to p(1000)=7919 and start afterwards a fermat test ( a^p mod p=a) with the bases a=2,3,5,7. Can i then say that the tested number is prime??? 
No, you can't, but you have a pretty good assumption.
If you want to use Fermat's little theorem as a primality test for a number p you must test all prime exponents smaller than p1. Pseudoprimes for each base aren't very rare, but combinations of a few bases (4 like you did) gives you a good idea... michael 
i thought that carmichael numbers are really rare and can be excluded by doing a little trail factoring.

They are not very frequent, but there are still enough to not be sure about the primality of a number...
If i'm correct there are 3 numbers smaller than 100.000 that pass fermat's little theorem for base 2,3,5 and 7 that are composite: 29341 = 13x37x61 46657 = 13x37x97 75361 = 11x13x17x31 michael 
but these numbers are eliminated by trial factoring up to 7000!!!

But these numbers are only 5 digits too, i wouldn't know how big the factors could become for 1520 digit carmichael numbers...
michael 
721801 = 601x1201, that's already a little bigger, let's see if i can find some pseudoprimes to base 2,3,5,7 with only factors bigger than 7000...
Also: A number n is a pseudoprime to the base b if b^n1 is congruent to 1 modulo n. A Carmichael number is a composite number n such that b^n1 is congruent to 1 modulo n for every b that is relatively prime to n. So we are talking about composite numbers that are pseudoprime to bases 2,3,5 and 7 ... this are not necessarily Carmichael numbers. michael 
Re: primility testing
[QUOTE][i]Originally posted by andi314 [/i]
[B]Can i then say that the tested number is prime ... i thought that carmichael numbers are really rare and can be excluded by doing a little trail factoring. ... but these numbers are eliminated by trial factoring up to 7000!!!???[/B][/QUOTE] There is a big mathematical difference between a statement that can be proved to be true and a statement that is true 99.9999...% of the time [i]but sometimes, even if very rarely, is false.[/i]. If one claims, or wants to say, simply that "[a certain number] is prime", that implies that it can be proven, absolutely and without any possible doubt, that the number is 100% definitely a prime number. If, instead, one is referring to a number which has been proven by trial factoring to have no factors smaller than some limit (e.g., 7000 or even 7 trillion) and, in addition, passes the Fermat pseudoprime test for 4 (or even 4000) different prime bases, then one can correctly say that the number is a [b]probable[/b] prime, but one [i]cannot[/i] correctly say that the number is a "prime" [i]with no qualifying adjective ahead of the word "prime"[/i]. So it's always necessary to refer to the latter example as a "probable prime" or "pseudoprime". 
so which other methods could i use to determine that a number is 100% prime???

[QUOTE][i]Originally posted by andi314 [/i]
[B]so which other methods could i use to determine that a number is 100% prime??? [/B][/QUOTE] Try [url]http://www.alpertron.com.ar/ECM.HTM[/url] 
but i want to implement this methods in a program so i cant use a webpage!!

All times are UTC. The time now is 12:16. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.