newbie question - testing primality of very large numbers

NeoGen · 2006-03-17, 21:01

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 P-1, 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...)

Uncwilly · 2006-03-17, 22:13

If the number is large but not too huge, I would suggest:

http://www.alpertron.com.ar/ECM.HTM

smh · 2006-03-17, 23:10

Quote:

Originally Posted by NeoGen

If I have a very large number that I want to know if it is prime or not.....

Define very large.

Wacky · 2006-03-17, 23:21

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 non-primes to find a "probable prime" is quite adequate. If a number cannot be proven to be non-prime with a reasonable effort, often you can use the number as if it were prime.

NeoGen · 2006-03-18, 04:24

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:

The primality proof must be a deterministic proof for a distinct integer
The claim must be for the primality for a distinct integer. The proof of primality of that distinct integer must be constructive, definitive, reproductable, verifiable and deterministic.

Probable-primality proofs are not acceptable. Claims involving probable primes will not be accepted.

Your claim must explicitly identify a distinct prime number. For example, claims involving Mills' Theorem real number or Matijasevic polynomial without providing a specific solution will not be accepted.

So I guess going around the problem is a no-no for them.

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?

Mystwalker · 2006-03-18, 09:16

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...

NeoGen · 2006-03-19, 01:48

So... trial factoring would be the only possible (but absolutely unfeasible) method...

ewmayer · 2006-03-19, 21:58

Quote:

Originally Posted by NeoGen

So... trial factoring would be the only possible (but absolutely unfeasible) method...

Why infeasible? If you can write the number in the form a^b+c with a and c reasonably small, trial-factoring is a very attractive approach.

NeoGen · 2006-03-20, 01:22

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.

2006-03-17, 21:01	#1
NeoGen Dec 2005 2·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 P-1, 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...)

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Primality testing non-Mersennes	lukerichards	Software	8	2018-01-24 22:30
Testing an expression for primality	1260	Software	17	2015-08-28 01:35
a new Deterministic primality testing	wsc812	Computer Science & Computational Number Theory	36	2013-03-04 06:25
a new primality testing method	jasong	Math	1	2007-11-06 21:46
newbie question - finding small factors of very large numbers	NeoGen	Math	7	2007-03-13 00:04

2006-03-17, 22:13	#2
Uncwilly 6809 > 6502 """"""""""""""""""" Aug 2003 101×103 Posts 2×5×13×73 Posts	If the number is large but not too huge, I would suggest: http://www.alpertron.com.ar/ECM.HTM

2006-03-17, 23:21	#4
Wacky Jun 2003 The Texas Hill Country 3²×11² 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 non-primes to find a "probable prime" is quite adequate. If a number cannot be proven to be non-prime with a reasonable effort, often you can use the number as if it were prime.

2006-03-18, 09:16	#6
Mystwalker 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...

2006-03-19, 01:48	#7
NeoGen Dec 2005 2·3³ Posts	So... trial factoring would be the only possible (but absolutely unfeasible) method...

2006-03-20, 01:22	#9
NeoGen Dec 2005 110110₂ 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.