primility testing
 

I hope somebody can help me:

I have a number ( approx. 15-20 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 p-1.
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 15-20 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^n-1 is congruent to 1 modulo n.

A Carmichael number is a composite number n such that b^n-1 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!!

Primality tests
 

I understand you need some code to implement in a computer program. please specify the OS platform and programming language you preffer to work with and i'll see what i can do.

From what i gather you need to test primes up to 20 digits, is this correct?

Please reply here or at the user forum at [url]www.shteker.com[/url]

I'm using win98 and c++

mostly i wirte my programs with the help of the MIRACL libary or the giantint library

Some basic background information on trial factoring.

Only need to test to the square root of the number.

For numbers expressed in base ten the square root will be at most one more than half the number of digits as the number your trying to factor.

A 15 digit number would have 8 digits max for the square root.

All primes except 2 and 3 are 6x +/- 1 with x = 1 ... so the factor mod 6 must be either 1 or 5 to be a potential prime.

A 64 bit unsigned integer can hold a 20 digit number (18446744073709551615 max).

but trial factoring a 20 -digit number take a while!!!

I want to implement a primility test where i know theat the number is 100% prime!!!

[QUOTE=andi314]so which other methods could i use to determine that a number is 100% prime???[/QUOTE]

For numbers having no special form, there are a number of algorithms you could try, e.g. APRCL (named after its inventors), ECPP, or the recent deterministic AKS algorithm. Do a Google search on any of these and you'll find background info and in most case freeware implementations. The practical limit of these seems to be 5000-10000 digits at present - proving any number < 100 digits or so would be virtually instantaneous via these methods.