|
2003-12-21, 10:57
|
#1 |
Nov 2002
2·37 Posts |
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??? |
|
|
|
2003-12-21, 12:11
|
#2 |
|
Dec 2003
Belgium
5·13 Posts |
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 |
|
|
|
|
2003-12-21, 12:18
|
#3 |
|
Nov 2002
2·37 Posts |
i thought that carmichael numbers are really rare and can be excluded by doing a little trail factoring.
|
|
|
|
|
2003-12-21, 12:27
|
#4 |
|
Dec 2003
Belgium
1018 Posts |
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 |
|
|
|
|
2003-12-21, 20:49
|
#5 |
|
Nov 2002
7410 Posts |
but these numbers are eliminated by trial factoring up to 7000!!!
|
|
|
|
|
2003-12-21, 20:54
|
#6 |
|
Dec 2003
Belgium
5·13 Posts |
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 Last fiddled with by michael on 2003-12-21 at 20:55 |
|
|
|
|
2003-12-21, 21:10
|
#7 |
|
Dec 2003
Belgium
5·13 Posts |
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 |
|
|
|
|
2003-12-22, 02:45
|
#8 | |
"Richard B. Woods"
Aug 2002
Wisconsin USA
1E0C16 Posts |
Re: primility testing
Quote:
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 probable prime, but one cannot correctly say that the number is a "prime" with no qualifying adjective ahead of the word "prime". So it's always necessary to refer to the latter example as a "probable prime" or "pseudoprime". |
|
|
|
|
|
2003-12-22, 09:42
|
#9 |
|
Nov 2002
4A16 Posts |
so which other methods could i use to determine that a number is 100% prime???
|
|
|
|
|
2003-12-22, 12:49
|
#10 | |
"Sander"
Oct 2002
52.345322,5.52471
29×41 Posts |
Quote:
|
|
|
|
|
|
2003-12-22, 13:23
|
#11 |
|
Nov 2002
2·37 Posts |
but i want to implement this methods in a program so i cant use a webpage!!
|
|
|
|
 |
| Thread Tools | |
Similar Threads
|
||||
| Thread | Thread Starter | Forum | Replies | Last Post |
| Anti-poverty drug testing vs "high" tax deduction testing | kladner | Soap Box | 3 | 2016-10-14 18:43 |
| PRP testing | pepi37 | Software | 6 | 2013-04-12 09:42 |
| Testing | grobie | Marin's Mersenne-aries | 1 | 2006-05-15 12:26 |
| Speed of P-1 testing vs. Trial Factoring testing | eepiccolo | Math | 6 | 2006-03-28 20:53 |
| P-1 Testing | ndpowell | Math | 4 | 2005-06-26 20:14 |
