mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2006-03-17, 21:01   #1
NeoGen
 
Dec 2005

2·33 Posts
Default 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...)
NeoGen is offline   Reply With Quote
Old 2006-03-17, 22:13   #2
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

22E816 Posts
Default

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

http://www.alpertron.com.ar/ECM.HTM
Uncwilly is offline   Reply With Quote
Old 2006-03-17, 23:10   #3
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29·41 Posts
Default

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.
smh is offline   Reply With Quote
Old 2006-03-17, 23:21   #4
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32×112 Posts
Default

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.
Wacky is offline   Reply With Quote
Old 2006-03-18, 04:24   #5
NeoGen
 
Dec 2005

2×33 Posts
Default

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?
NeoGen is offline   Reply With Quote
Old 2006-03-18, 09:16   #6
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

3×277 Posts
Default

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...
Mystwalker is offline   Reply With Quote
Old 2006-03-19, 01:48   #7
NeoGen
 
Dec 2005

2·33 Posts
Default

So... trial factoring would be the only possible (but absolutely unfeasible) method...
NeoGen is offline   Reply With Quote
Old 2006-03-19, 21:58   #8
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

1157110 Posts
Default

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.
ewmayer is offline   Reply With Quote
Old 2006-03-20, 01:22   #9
NeoGen
 
Dec 2005

5410 Posts
Default

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.
NeoGen is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 08:20.

Thu Dec 3 08:20:00 UTC 2020 up 4:31, 0 users, load averages: 1.17, 1.14, 1.04

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.