20150926, 22:33  #1 
Sep 2015
11_{2} Posts 
How to Check if NonMersenne Number isPrime?
Hello!
Can anyone point me in the right direction on how to check if a 1 billion digit long number is prime? Just as an FYI, I haven't even taken calculus yet, so I hope it's not too complex, but if someone could point me in the right direction, I'd be grateful. Thanks! 
20150926, 23:27  #2  
If I May
"Chris Halsall"
Sep 2002
Barbados
2960_{16} Posts 
Quote:
There are many way smarter than you and me (and most others) thinking about this. Perhaps spend some time getting many (many!) qubits online. Last fiddled with by chalsall on 20150926 at 23:38 Reason: Fixed broken quote. 

20150927, 00:15  #3 
Sep 2015
3 Posts 
That's kind of what I thought... Hmmmm...

20150927, 04:23  #4  
"Curtis"
Feb 2005
Riverside, CA
2^{2}·3·449 Posts 
Quote:
If little/nothing is known about the number's form, you could try trial division to disprove primality. Of course, if you don't find a factor in a month or two, you still have no idea if it's prime... 

20150927, 04:44  #5 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
10644_{10} Posts 
A quick and dirty calculation estimates it would take a quad core 4GHz machine working *perfectly* for about 15.516 years to run a single test (provided it had enough memory, memory bandwidth, large enough cache, and other such.) on a Mersenne number. Other types of primes take longer (as I am lead to understand). A single bad bit (cosmic ray, a little over heat) and the test can fail. The FFT size is too big for current processors, IIRC, so that number is already too small (by a factor of 2 to 4). Also, I don't know if mlucas, glucas, or CUDAlucas are set to handle a number this large. I don't think the current version of Prime95 is. You would want to do ~ 12 years of factoring on a GPU first, then about a year's worth of P1 with a massive amount of memory (128GB ?).

20150927, 06:13  #6 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
1C35_{16} Posts 
It takes months/years on modern hardware to:
1) Test the primality of 10,000,000100,000,000 digit Mersenne numbers 2) Test the primality of ~50,000 digit numbers of arbitrary/no form. If the number in question has a nonMersenne special form, it may take less time than the general method, but still substantially more than a Mersenneform test. In any case, proving the primality of a billion digit number is, with current techniques and hardware, a pipe dream. As VBCurtis points out, it may be worthwhile to attempt a PRP test, or perhaps to attempt to find super duper small factors. "Most" randomly selected billion digit numbers have small factors, though of course we know nothing about your particular billion digit number. 
20150927, 14:14  #7 
Aug 2002
3^{2}×23×41 Posts 
One (educational) approach might be to determine a way to check if a single digit number is prime. Make a flow chart of the process. Then apply your flow chart to a two digit number. See if you can optimize your flow chart. Lather, rinse and repeat.

20150927, 15:05  #8  
"Bob Silverman"
Nov 2003
North of Boston
1D28_{16} Posts 
Quote:
The question you ask has nothing to do with calculus. The subject area here is algebra and number theory. You also express hope that it is "not too complex". This implies that you believe that calculus is (1) A complex subject It can be, but it isn't always. Any area of math can be simple or it can be complex. You are confusing "elementary" with "complex". Elementary problems in math can be very complicated. Very advanced mathematics can be quite simple. (2) It also implies that you think you will better understand "complicated" mathematics after you take calculus. I can assure you that this is not true. Number theory and algebra can be studied totally independently from calculus. BTW. Testing billion digit arbitrary numbers for primality is beyond the range of current algorithms and computers. It is possible that with moderate effort one can show that a billion digit number isn't prime, but such a demonstration requires luck. Last fiddled with by R.D. Silverman on 20150927 at 15:06 Reason: typo 

20150927, 15:13  #9 
"Forget I exist"
Jul 2009
Dumbassville
20307_{8} Posts 
like for a number of form k*b^n+1 you can prove that if gcd((ky)*b^n,y*b^n+1)!=1 that it's composite but this could require as many as k separate tests.

20150927, 15:13  #10  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}×3×311 Posts 
Quote:
The difference between me and you is that I have devoted lots and lots of time to studying this subject. Don't equate dedication and brilliance. Many people spend lots and lots of time  mastering the balance beam  learning history  learning how to paint landscapes  learning the law (yech!) etc. etc. ... etc. I renew a chronic complaint. The general public thinks anyone who understands math is somehow a "genius". This is not true. What is true is that the person has spent a lot of time studying the subject. As Edison said: Genius is 1% inspiration and 99% perspiration. 

20150927, 15:17  #11  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}·3·311 Posts 
Quote:
to implement Step 2 that requires space that is about 100 log(N)/(word size of machine) OTOH, a convolutionbased implementation of Step 2 DOES require massive memory. Please stop promoting this myth. There is a pure timespace tradeoff. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Fast isPrime() for n < 2^32  SPWorley  Computer Science & Computational Number Theory  35  20180728 13:02 
Number of distinct prime factors of a Double Mersenne number  aketilander  Operazione Doppi Mersennes  1  20121109 21:16 
Number of Factors for a Mersenne Number  kurtulmehtap  Math  12  20100503 14:02 
First check and double check llrnet servers.  opyrt  Prime Sierpinski Project  3  20090102 01:50 
How to check if a number is a Mersenne prime ?  Unregistered  Software  6  20040619 08:18 