## 1 Billion digit prime

For other topics related to the FreeBASIC project or its community.
owen
Posts: 554
Joined: Apr 19, 2006 10:55
Location: Kissimmee, FL
Contact:

### 1 Billion digit prime

If'n anyone has a fast pc with a bunch of ram can you please help me crunch some numbers
http://htwif.com/owen/prime/primorial.html
owen reese
owen
Posts: 554
Joined: Apr 19, 2006 10:55
Location: Kissimmee, FL
Contact:

### Re: 1 Billion digit prime

Searching for a billion digit prime is so impractical, it's no wonder I only have 36 views on this post with no replies at this time.

What would be practical is a freebasic port of gmp. This endeavor would be a serious contribution to the FB community and would shed great insight to FFT.

I've been messing around with the idea of just multiplying large numbers and have had some interesting findings however nothing I came up with could even come close to touching the speed of gmp.

So this post is about finding a billion digit and eventually a trillion digit prime.
The investigation of primes plays a significant role in programming and in my opinion the more prime number theory discussions in this community the better we stand a chance of attracting and retaining great contributors. That is not to say that there haven't been excellent contributions to FB, proof of point is FB itself. FB is a remarkable contribution to society.

The practicality / feasibility of investigating large primes is a myth. Wow, now that's a statement which should lead to further discussion...

Owen, the most notorious double poster in this forum.
Cheers.
srvaldez
Posts: 2518
Joined: Sep 25, 2005 21:54

### Re: 1 Billion digit prime

owen, I went to your site but did not visit any of the sites that you linked to, so my question is: will the result of the multiplies be a prime?
aXu
Posts: 17
Joined: Jan 19, 2012 20:32

### Re: 1 Billion digit prime

srvaldez wrote:owen, I went to your site but did not visit any of the sites that you linked to, so my question is: will the result of the multiplies be a prime?

No. A prime is a number which is not divisible by any other number than itself and 1. Thus, primes cannot be found by multiplying other primes, because the result would be divisible by those prime numbers.
owen
Posts: 554
Joined: Apr 19, 2006 10:55
Location: Kissimmee, FL
Contact:

### Re: 1 Billion digit prime

No, the result of the multiples are most definitely not prime. The product is a composite of primes only
In other words: The first few prime numbers are 2,3,5,7,11.
Notice the number 4,6,8,9 & 10 are not included since they are not prime numbers.
So my composite number is the product of prime numbers only (actually that is the one thing I need double verification on after this large composite is found.)

Take for example my first text file 200M-1.txt...
That number is (or should be) the product of the first primes up to and including 230278831

The next four text files are the products of the remaining primes:
So 200M-2.txt is the product of the next prime number after 230278831 (what ever it is) multiplied with the next primes up to and including 460540889.

I know I left that info out on the above noted web page but that's because that info will be rather irrelevant / insignificant once we calculate the product of the 5 large numbers.

And just like I always do... the primorial will be free for all to know and may be the largest published primorial to date. Not quite sure if I'll actually host the 1 gig text file on my server for very long. Probably give it to google or something.
owen
Posts: 554
Joined: Apr 19, 2006 10:55
Location: Kissimmee, FL
Contact:

### Re: 1 Billion digit prime

The next step, after verification of course, will be to represent this large primorial in the form of 2^n +or-x. Naturally the goal will be to find the smallest x by either increasing or decreasing the primorial since primorial sometimes comes close to converging with 2^n (i think, {been awhile since i looked into that idea}).
Richard
Posts: 3030
Joined: Jan 15, 2007 20:44
Location: Australia

### Re: 1 Billion digit prime

Cryptography requires a pair of big primes for use in key generation and transfer. If big primes can be generated and checked, then they can obviously also be factored. If you multiply two of those big primes together then the same factorisation method applied to the product will be slower, but it will still be possible to find the original prime factors.

What is the purpose of trying to generate billion digit primes ?
What would you do with a billion digit prime if you found and proved one, publish it or keep it secret and use it yourself ?

Why not do research into primes on more tractable 1000 digit primes ?
owen
Posts: 554
Joined: Apr 19, 2006 10:55
Location: Kissimmee, FL
Contact:

### Re: 1 Billion digit prime

Why a 1 billion digit prime?
1. The largest know prime to date is a 10 million digit number and the current race is to find a 100 million digit number which will more then likely also be a mersenne prime. My chances of finding a 100 million digit prime before they do is unlikely which is why I decided to begin my investigation with a billion digits. If I do find and am able to prove my prime, it will more then likely not be a mersenne prime which will be quite a break in the trend.

2. This is just a 'for the fun of it' thing to me. A billion digit prime is the top level for our current technology. Basically it's pushing the limit where as a trillion digit prime exceeds our current technology. Perhaps in a few years, the trillion digit investigation will be possible but that's a bunch of ram just to contain the number and even more to crunch it. Basically it would take apx. 8 tera bytes of ram (i'm guessing).

About crypto. It is my opinion that 'one time pads' (used only one time) are the only unbreakable keys. I was not aware that primes were used for crypto until i watch mit's videos on computer science 5 years ago. Actually, it was about 12 years ago when I made a silly program called specomm which created one time pads derived from the users mouse movements. The idea in one time pads being secure is about randomness and I figured the inability to draw a perfect circle with the mouse was about as random as it gets which is how i came up with the idea (i think).

I'm not really into crypto these days as i'm rather tired of the idea of proprietary / secrets / control... I'm just a fun, loving, curios kid who still doesn't know what he wants to be when he grows up.

And ps... the only stupid question is the question never asked. I will more then likely ask some doozies myself and i hope you all will be forgiving and patient. Sometimes I say I must be loosing my mind cuz i can't remember some of the most basic things. Could it be i'm loosing my mind or is it possible i'm just beginning to think.
srvaldez
Posts: 2518
Joined: Sep 25, 2005 21:54

### Re: 1 Billion digit prime

I am willing to do the 200m multiplies, but I think it would be better to do in 64-bit and of course fb is 32-bit and I know very little C.
Richard
Posts: 3030
Joined: Jan 15, 2007 20:44
Location: Australia

### Re: 1 Billion digit prime

Could it be i'm loosing my mind or is it possible i'm just beginning to think

There is no doubt that when you take on a task like testing billion digit primes it helps to be “unusual”.

If you find a biggest prime it will only last for a short while, but if you can find a fast prime verification algorithm for billion digit primes, your name will live forever. Maybe you need to find another way of representing integers that makes their factorisation trivial.

There are PCs running multiple, multi-channel graphics cards, without screens. They are using the GPUs as parallel processors. You will not outrun others by brute force. You need a third way.

If you write a number in base b and it ends in 0 then it is divisible by b. Changing the base from b to b+2 is quite a fast process compared to multiplication. I think it may be done in linear time, not time squared. What would happen if you wrote your integer p in base q, where q ranged from 3 to Sqr(p) in steps of 2. That is the type of third way I am suggesting.
owen
Posts: 554
Joined: Apr 19, 2006 10:55
Location: Kissimmee, FL
Contact:

### Re: 1 Billion digit prime

Changing the base of a number is useful:
1. For communication purposes - (write me)
2. For computational purposes - (write me) (i'm thinking this article has to do with hardware)

I agree - a third way (or another way) which will be derived from our creativity if and only if we never give up on the dream.

I refer to the myth (as noted above) and in my dream it has to do with the scarcity of primes or increasing gaps between primes. The shortest explanation of this dream has to do with the idea of brute force but brute force trial division on a ever decreasing number of divisors, ie. trial division up to the sqr root using primes only is optimal...

Soon, I'll try to explain this best I can and hope it'll be a break through. But after I explain what I have in mind, I anticipate my idea to be that of some idea thought of hundreds of years ago but just not known or understood by me.

In other words, I'm probably re-inventing the wheel - which is what I do best... and is simply delightful to do.
Destructosoft
Posts: 88
Joined: Apr 03, 2011 3:44
Location: Inside the bomb
Contact:

### Re: 1 Billion digit prime

Some years ago I ran a GIMPS program for a couple months. Nothing came of it, and it was interfering with my AFK vending in Ragnarok Online anyway.

Later, I remember running a separate computer to try to find a factor for F14 (the 14th Fermat number). Months went by, then I found out someone else had just discovered the factor.

Mathematical thoroughness is nice, but when there are several irons and not much fire...!
TESLACOIL
Posts: 1769
Joined: Jun 20, 2010 16:04
Location: UK
Contact:

### Re: 1 Billion digit prime

any idea how long it would take to find a billion digit prime ?

eg how many hours on modern quad core say ?
Richard
Posts: 3030
Joined: Jan 15, 2007 20:44
Location: Australia

### Re: 1 Billion digit prime

The thing that takes the time is the proof that a possible prime does not have any factors.
With a billion digit prime there are only 10^(half a billion) possible factors to test for.
Using current software techniques it certainly cannot be done using all the quad core processors yet built, in a hundred years.
TESLACOIL
Posts: 1769
Joined: Jun 20, 2010 16:04
Location: UK
Contact:

### Re: 1 Billion digit prime

hmm you would need some kind of smart attack....as in the careful selection of the target number

and slowly acquiring a statistical proof , the number tested for in specific ways

an absolute proof via bruteforce may not be possible for some numbers in that range

http://primes.utm.edu/largest.html#biggest

http://en.wikipedia.org/wiki/Largest_known_prime_number