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! 
[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. 
That's kind of what I thought... Hmmmm...

[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... 
[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.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 ?).

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

[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. 
[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((ky)*b^n,y*b^n+1)!=1 that it's composite but this could require as many as k separate tests. 
[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. 
[QUOTE=Uncwilly;411367]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 ?).[/QUOTE]
P1, even a 2step P1 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]convolutionbased[/b] implementation of Step 2 DOES require massive memory. Please stop promoting this myth. There is a pure timespace tradeoff. 
All times are UTC. The time now is 10:57. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.