-   Software (
-   -   newbie question - testing primality of very large numbers (

NeoGen 2006-03-17 21:01

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

Uncwilly 2006-03-17 22:13

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


smh 2006-03-17 23:10

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

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

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

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

ewmayer 2006-03-19 21:58

[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, 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. :razz:

All times are UTC. The time now is 11:39.

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