mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Operation Billion Digits (https://www.mersenneforum.org/forumdisplay.php?f=50)
-   -   How to Check if Non-Mersenne Number isPrime? (https://www.mersenneforum.org/showthread.php?t=20513)

FloatingPoint 2015-09-26 22:33

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!

chalsall 2015-09-26 23:27

[QUOTE=FloatingPoint;411353]...but if someone could point me in the right direction, I'd be grateful.[/QUOTE]

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.

FloatingPoint 2015-09-27 00:15

That's kind of what I thought... Hmmmm...

VBCurtis 2015-09-27 04:23

[QUOTE=FloatingPoint;411353]Hello!
Can anyone point me in the right direction on how to check if a 1 billion digit long number is prime?
[/QUOTE]

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

Uncwilly 2015-09-27 04:44

[QUOTE=FloatingPoint;411353]Can anyone point me in the right direction on how to check if a 1 billion digit long number is prime?[/QUOTE]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 ?).

Dubslow 2015-09-27 06:13

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.

Xyzzy 2015-09-27 14:14

[QUOTE=FloatingPoint;411353]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.[/QUOTE]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.

R.D. Silverman 2015-09-27 15:05

[QUOTE=FloatingPoint;411353]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![/QUOTE]

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 [b]can[/b] 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.

science_man_88 2015-09-27 15:13

[QUOTE=R.D. Silverman;411398] It is possible that with moderate effort one can show that a
billion digit number isn't prime, but such a demonstration requires luck.[/QUOTE]

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.

R.D. Silverman 2015-09-27 15:13

[QUOTE=chalsall;411354]Give up hope. Seriously.

There are many way smarter than you and me (and most others) thinking about this.
[/QUOTE]

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 2015-09-27 15:17

[QUOTE=Uncwilly;411367]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 ?).[/QUOTE]

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 [b]convolution-based[/b] implementation of Step 2 DOES require massive memory.

Please stop promoting this myth.

There is a pure time-space tradeoff.


All times are UTC. The time now is 10:57.

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