mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Operation Billion Digits

Reply
 
Thread Tools
Old 2015-09-26, 22:33   #1
FloatingPoint
 
Sep 2015

3 Posts
Default 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!
FloatingPoint is offline   Reply With Quote
Old 2015-09-26, 23:27   #2
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

23·1,103 Posts
Default

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

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 2015-09-26 at 23:38 Reason: Fixed broken quote.
chalsall is offline   Reply With Quote
Old 2015-09-27, 00:15   #3
FloatingPoint
 
Sep 2015

3 Posts
Default

That's kind of what I thought... Hmmmm...
FloatingPoint is offline   Reply With Quote
Old 2015-09-27, 04:23   #4
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2·1,997 Posts
Default

Quote:
Originally Posted by FloatingPoint View Post
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...
VBCurtis is offline   Reply With Quote
Old 2015-09-27, 04:44   #5
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

22·3·647 Posts
Default

Quote:
Originally Posted by FloatingPoint View Post
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 ?).
Uncwilly is offline   Reply With Quote
Old 2015-09-27, 06:13   #6
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

It takes months/years on modern hardware to:
1) Test the primality of 10,000,000-100,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 non-Mersenne special form, it may take less time than the general method, but still substantially more than a Mersenne-form 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.
Dubslow is offline   Reply With Quote
Old 2015-09-27, 14:14   #7
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

2×7×13×41 Posts
Default

Quote:
Originally Posted by FloatingPoint View Post
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.
Xyzzy is offline   Reply With Quote
Old 2015-09-27, 15:05   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

73×101 Posts
Default

Quote:
Originally Posted by FloatingPoint View Post
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
R.D. Silverman is offline   Reply With Quote
Old 2015-09-27, 15:13   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
science_man_88 is offline   Reply With Quote
Old 2015-09-27, 15:13   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

737310 Posts
Default

Quote:
Originally Posted by chalsall View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2015-09-27, 15:17   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

73·101 Posts
Default

Quote:
Originally Posted by Uncwilly View Post
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.

Please stop promoting this myth.

There is a pure time-space tradeoff.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Fast isPrime() for n < 2^32 SPWorley Computer Science & Computational Number Theory 35 2018-07-28 13:02
Number of distinct prime factors of a Double Mersenne number aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16
Number of Factors for a Mersenne Number kurtulmehtap Math 12 2010-05-03 14:02
First check and double check llrnet servers. opyrt Prime Sierpinski Project 3 2009-01-02 01:50
How to check if a number is a Mersenne prime ? Unregistered Software 6 2004-06-19 08:18

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

Wed Apr 1 05:11:06 UTC 2020 up 7 days, 2:44, 0 users, load averages: 1.74, 1.51, 1.48

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.