20060317, 21:01  #1 
Dec 2005
2×3^{3} Posts 
newbie question  testing primality of very large numbers
If I have a very large number that I want to know if it is prime or not, what software or algorithm can I use? (preferably a simple one)
Assuming that it is a long string of totally random digits, and not a number like mersenne, or P1, or others expressable by short formulas. How do I prove it to be a prime or not? (I hope trial factoring is not the only way...) 
20060317, 22:13  #2 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
221F_{16} Posts 

20060317, 23:10  #3  
"Sander"
Oct 2002
52.345322,5.52471
29·41 Posts 
Quote:


20060317, 23:21  #4 
Jun 2003
The Texas Hill Country
1082_{10} Posts 
Do you really need to PROVE that the number is prime?
It is much easier to demonstrate that a number is NOT prime. And, in many cases, eliminating nonprimes to find a "probable prime" is quite adequate. If a number cannot be proven to be nonprime with a reasonable effort, often you can use the number as if it were prime. 
20060318, 04:24  #5  
Dec 2005
66_{8} Posts 
I found and tried the alpertron applet. It was fun to play with but started getting really slow as I upped the lenght of the numbers. I think it has too many extra functions in the package that I'm not looking for, like knowing precisely how many factors a given number has.
At a point I tried to play with it and the PSP Sieve's factors and it said something like the number was too big. Definition of "very large"... hmm... something around 10,000,000 digits for the eff awards would be great. They state on the rules that Quote:
And yea, I know I'm dreaming way up in the clouds, and totally off my league, but isn't dreaming what always takes us further? 

20060318, 09:16  #6 
Jul 2004
Potsdam, Germany
3·277 Posts 
For a number that large, you can only try to find a factor and thus prove it's not prime.
Proving primalty of number of no special form can't be done for such big numbers. The biggest such number I heard of has been proven prime had ~15,000 digits... 
20060319, 01:48  #7 
Dec 2005
2·3^{3} Posts 
So... trial factoring would be the only possible (but absolutely unfeasible) method...

20060319, 21:58  #8  
∂^{2}ω=0
Sep 2002
República de California
9,791 Posts 
Quote:


20060320, 01:22  #9 
Dec 2005
2·3^{3} Posts 
Nice! Where can I get some info on how that works, or the relation between that formula and trial factoring?
I thought that trial factoring only meant testing the number against all primes lower or equal to the square root of the number. (infeasible against a 10,000,000 digits number) And because these things seem to be quite relative... define "reasonably small" please. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Primality testing nonMersennes  lukerichards  Software  8  20180124 22:30 
Testing an expression for primality  1260  Software  17  20150828 01:35 
a new Deterministic primality testing  wsc812  Computer Science & Computational Number Theory  36  20130304 06:25 
a new primality testing method  jasong  Math  1  20071106 21:46 
newbie question  finding small factors of very large numbers  NeoGen  Math  7  20070313 00:04 