mersenneforum.org How to Check if Non-Mersenne Number isPrime?
 Register FAQ Search Today's Posts Mark Forums Read

 2015-09-26, 22:33 #1 FloatingPoint   Sep 2015 112 Posts How to Check if Non-Mersenne 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!
2015-09-26, 23:27   #2
chalsall
If I May

"Chris Halsall"
Sep 2002

22·41·53 Posts

Quote:
 Originally Posted by FloatingPoint ...but if someone could point me in the right direction, I'd be grateful.
Give up hope. Seriously.

Perhaps spend some time getting many (many!) qubits online.

Last fiddled with by chalsall on 2015-09-26 at 23:38 Reason: Fixed broken quote.

 2015-09-27, 00:15 #3 FloatingPoint   Sep 2015 38 Posts That's kind of what I thought... Hmmmm...
2015-09-27, 04:23   #4
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

2·3·5·131 Posts

Quote:
 Originally Posted by FloatingPoint Hello! Can anyone point me in the right direction on how to check if a 1 billion digit long number is prime?
Of what form? Are you interested in knowing how big a number of your form can be checked for primality (or "probable primality"), or do you have special interest in one specific number?

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

2015-09-27, 04:44   #5
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

1DCC16 Posts

Quote:
 Originally Posted by FloatingPoint Can anyone point me in the right direction on how to check if a 1 billion digit long number is prime?
A quick and dirty calculation estimates it would take a quad core 4GHz machine working *perfectly* for about 15.5-16 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 ~ 1-2 years of factoring on a GPU first, then about a year's worth of P-1 with a massive amount of memory (128GB ?).

 2015-09-27, 06:13 #6 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
2015-09-27, 14:14   #7
Xyzzy

"Mike"
Aug 2002

1CFC16 Posts

Quote:
 Originally Posted by FloatingPoint 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.
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.

2015-09-27, 15:05   #8
R.D. Silverman

Nov 2003

7,309 Posts

Quote:
 Originally Posted by FloatingPoint 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!
I am curious. Why do you think that not having taken calculus is relevant?
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 2015-09-27 at 15:06 Reason: typo

2015-09-27, 15:13   #9
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by R.D. Silverman It is possible that with moderate effort one can show that a billion digit number isn't prime, but such a demonstration requires luck.
like for a number of form k*b^n+1 you can prove that if gcd((k-y)*b^n,y*b^n+1)!=1 that it's composite but this could require as many as k separate tests.

2015-09-27, 15:13   #10
R.D. Silverman

Nov 2003

7,309 Posts

Quote:
 Originally Posted by chalsall Give up hope. Seriously. There are many way smarter than you and me (and most others) thinking about this.
Perhaps. But I am certainly no smarter than you.
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.

2015-09-27, 15:17   #11
R.D. Silverman

Nov 2003

7,309 Posts

Quote:
 Originally Posted by Uncwilly A quick and dirty calculation estimates it would take a quad core 4GHz machine working *perfectly* for about 15.5-16 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 ~ 1-2 years of factoring on a GPU first, then about a year's worth of P-1 with a massive amount of memory (128GB ?).
P-1, even a 2-step P-1 does NOT require a massive amount of memory. There is a simple method
to implement Step 2 that requires space that is about 100 log(N)/(word size of machine)

OTOH, a convolution-based implementation of Step 2 DOES require massive memory.

There is a pure time-space tradeoff.

 Similar Threads Thread Thread Starter Forum Replies Last Post SPWorley Computer Science & Computational Number Theory 35 2018-07-28 13:02 aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16 kurtulmehtap Math 12 2010-05-03 14:02 opyrt Prime Sierpinski Project 3 2009-01-02 01:50 Unregistered Software 6 2004-06-19 08:18

All times are UTC. The time now is 19:33.

Tue Feb 25 19:33:06 UTC 2020 up 25 days, 14:04, 2 users, load averages: 3.02, 2.78, 2.78