mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2003-12-21, 10:57   #1
andi314
 
andi314's Avatar
 
Nov 2002

2×37 Posts
Default 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???
andi314 is offline   Reply With Quote
Old 2003-12-21, 12:11   #2
michael
 
Dec 2003
Belgium

5·13 Posts
Default

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
michael is offline   Reply With Quote
Old 2003-12-21, 12:18   #3
andi314
 
andi314's Avatar
 
Nov 2002

4A16 Posts
Default

i thought that carmichael numbers are really rare and can be excluded by doing a little trail factoring.
andi314 is offline   Reply With Quote
Old 2003-12-21, 12:27   #4
michael
 
Dec 2003
Belgium

6510 Posts
Default

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
michael is offline   Reply With Quote
Old 2003-12-21, 20:49   #5
andi314
 
andi314's Avatar
 
Nov 2002

2×37 Posts
Default

but these numbers are eliminated by trial factoring up to 7000!!!
andi314 is offline   Reply With Quote
Old 2003-12-21, 20:54   #6
michael
 
Dec 2003
Belgium

10000012 Posts
Default

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
michael is offline   Reply With Quote
Old 2003-12-21, 21:10   #7
michael
 
Dec 2003
Belgium

5×13 Posts
Default

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
michael is offline   Reply With Quote
Old 2003-12-22, 02:45   #8
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default Re: primility testing

Quote:
Originally posted by andi314
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!!!???
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 but sometimes, even if very rarely, is false..

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".
cheesehead is offline   Reply With Quote
Old 2003-12-22, 09:42   #9
andi314
 
andi314's Avatar
 
Nov 2002

7410 Posts
Default

so which other methods could i use to determine that a number is 100% prime???
andi314 is offline   Reply With Quote
Old 2003-12-22, 12:49   #10
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

100101001012 Posts
Default

Quote:
Originally posted by andi314
so which other methods could i use to determine that a number is 100% prime???
Try http://www.alpertron.com.ar/ECM.HTM
smh is offline   Reply With Quote
Old 2003-12-22, 13:23   #11
andi314
 
andi314's Avatar
 
Nov 2002

1128 Posts
Default

but i want to implement this methods in a program so i cant use a webpage!!
andi314 is offline   Reply With Quote
Reply

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

All times are UTC. The time now is 06:24.

Tue May 11 06:24:45 UTC 2021 up 33 days, 1:05, 1 user, load averages: 1.03, 1.31, 1.45

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.