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...) 
If the number is large but not too huge, I would suggest:
[URL="http://www.alpertron.com.ar/ECM.HTM"]http://www.alpertron.com.ar/ECM.HTM[/URL] 
[QUOTE=NeoGen]If I have a very large number that I want to know if it is prime or not.....[/QUOTE]Define [B]very large[/B].

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. 
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. :sad: Definition of "very large"... hmm... something around 10,000,000 digits for the eff awards would be great. :razz: They state on the rules that [QUOTE][B]The primality proof must be a deterministic proof for a distinct integer[/B] 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. Probableprimality 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. [/QUOTE] So I guess going around the problem is a nono for them.:no: 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?:razz: 
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... 
So... trial factoring would be the only possible (but absolutely unfeasible) method...:down:

[QUOTE=NeoGen]So... trial factoring would be the only possible (but absolutely unfeasible) method...:down:[/QUOTE]
Why infeasible? If you can write the number in the form a^b+c with a and c reasonably small, trialfactoring is a very attractive approach. 
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. :razz: 
All times are UTC. The time now is 11:39. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2020, Jelsoft Enterprises Ltd.