mersenneforum.org newbie question - testing primality of very large numbers
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

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

"Sander"
Oct 2002
52.345322,5.52471

29×41 Posts

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.

 2006-03-17, 23:21 #4 Wacky     Jun 2003 The Texas Hill Country 32×112 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, 04:24   #5
NeoGen

Dec 2005

2×33 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:
 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?

 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·33 Posts So... trial factoring would be the only possible (but absolutely unfeasible) method...
2006-03-19, 21:58   #8
ewmayer
2ω=0

Sep 2002
República de California

265518 Posts

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.

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

 Similar Threads Thread Thread Starter Forum Replies Last Post lukerichards Software 8 2018-01-24 22:30 1260 Software 17 2015-08-28 01:35 wsc812 Computer Science & Computational Number Theory 36 2013-03-04 06:25 jasong Math 1 2007-11-06 21:46 NeoGen Math 7 2007-03-13 00:04

All times are UTC. The time now is 05:02.

Sun Apr 18 05:02:26 UTC 2021 up 9 days, 23:43, 0 users, load averages: 3.35, 2.53, 2.24