Getting Past My Naivety

[storm5510]

I will admit it. When it comes to mathematical theory and advanced subjects, I am naive as one can be. I am not too proud to admit it. At the same time, I am fascinated by it. I am afraid this fascination came too late. I had no interest in it when I was younger, beyond what I needed in everyday life. Then the computer age came into being and I knew I had messed up, badly.

I like to think of myself as being a decent programmer. I took to it right off in college. Languages like Pascal, Basic, and COBOL were all easy. C+ and Assembly were a lot harder but I managed. The problem then, and still now, is my lack of mathematical understanding. This inability puts a cap on what I can do in programming.

I would like to get past my naivety to some small degree if possible. In the past when I have asked questions here, I have been given links to pages on Wikipedia, mostly. That is fine. There is no need to write something out that already exists. I found a lot of those pages using mathematical notation to varying degrees. Some of it I can understand; those being the things I saw when studying industrial and digital electronics in college. The rest, not so well.

So, here is the lay of it. In 2005, I wrote an application that could find prime numbers, in general. No specific types. It was the GIMPS project which peaked, and still holds, my interest. I knew that prime numbers were only divisible by themselves, and one. So, that is what I based my application on. Wikipedia calls what I used the "naive" way. It is the longest way; taking a number and dividing it by every odd value above two to the value of the number, minus two, and skipping units of five.

I would like to learn a better way to do this, and I am asking for assistance. If someone would lend a hand, that would be wonderful. If not, then that will be alright too. I understand.

[R.D. Silverman]

Originally Posted by storm5510

I will admit it. When it comes to mathematical theory and advanced subjects, I am naive as one can be. I am not too proud to admit it. At the same time, I am fascinated by it. I am afraid this fascination came too late. I had no interest in it when I was younger, beyond what I needed in everyday life. Then the computer age came into being and I knew I had messed up, badly.

I like to think of myself as being a decent programmer. I took to it right off in college. Languages like Pascal, Basic, and COBOL were all easy. C+ and Assembly were a lot harder but I managed. The problem then, and still now, is my lack of mathematical understanding. This inability puts a cap on what I can do in programming.

I would like to get past my naivety to some small degree if possible. In the past when I have asked questions here, I have been given links to pages on Wikipedia, mostly. That is fine. There is no need to write something out that already exists. I found a lot of those pages using mathematical notation to varying degrees. Some of it I can understand; those being the things I saw when studying industrial and digital electronics in college. The rest, not so well.

So, here is the lay of it. In 2005, I wrote an application that could find prime numbers, in general. No specific types. It was the GIMPS project which peaked, and still holds, my interest. I knew that prime numbers were only divisible by themselves, and one. So, that is what I based my application on. Wikipedia calls what I used the "naive" way. It is the longest way; taking a number and dividing it by every odd value above two to the value of the number, minus two, and skipping units of five.

I would like to learn a better way to do this, and I am asking for assistance. If someone would lend a hand, that would be wonderful. If not, then that will be alright too. I understand.

Start by reading:

D.E. Knuth, The Art of Computer Programming, Vol 2.

This will teach you about multi-precise arithmetic and a lot of other things.
Aho, Hopcroft & Ullman also wrote an excellent book on Algorithms.

add a decent book on number theory.

Hardy & Wright, Introduction to the Theory of Numbers is a good
text and quite broad; it covers a lot of topics.

Try also:

D. Shanks, Solved & Unsolved Problems in Number Theory.

Then add a good general book about modern algebra. There are
a lot of good ones. Stay away from S. Lang's effort.
I would recomment Hungerford's book, but it is likely too difficult.
Birkhoff & MacLane is excellent.


Then you can try reading Crandall & Pomerance's book.

Read. Read. Read. Do the exercizes. There is no shortcut.

[bsquared]

Originally Posted by storm5510

... an application that could find prime numbers, in general. No specific types. ...

Well, this isn't really my specialty, but I think I know this much: it really depends a lot on how big of prime numbers you want to find.

You can use a sieve to find ALL prime numbers up to several billion in a few seconds.

You can use these primes to test numbers up to about 20 digits long in a few more seconds, using the naive approach.

Anything much more than that and you have to start using quite a bit more math involved in general purpose primalty proving algorithms, because the number of divisions to perform grows to quickly to continue using the naive approach.

General purpose primalty proving algorithm include the APRCL test and ECPP (probably others). Even with these tests, you'd be doing great to be able to prove primes up to a couple thousand digits. Any bigger than that, and you're only hope is that the number has a special form and corresponding prime proving algorithm (Mersenne's, Fermat's). That's where my usefullness (such as it is) stops.

[storm5510]

Originally Posted by bsquared

...Even with these tests, you'd be doing great to be able to prove primes up to a couple thousand digits...

No, nothing near that size. A 64-bit unsigned integer as defined in Visual C#, (just above 10^18), would be the max. In reality, I would never get anywhere near that.

I want this to be a learning process. If someone just hands me a solution, I won't get much from it. I would rather be led to it.

[R.D. Silverman]

Originally Posted by storm5510

No, nothing near that size. A 64-bit unsigned integer as defined in Visual C#, (just above 10^18), would be the max. In reality, I would never get anywhere near that.

I want this to be a learning process. If someone just hands me a solution, I won't get much from it. I would rather be led to it.

Read Crandall & Pomerance. 64 bits are easy. Just factor p+1 and
p-1 up to N^1/3, then use the combined Theorem of Selfridge, Lehmer,
Brillhart, etc. See the Cunningham book.

[Orgasmic Troll]

Originally Posted by R.D. Silverman

Read. Read. Read. Do the exercizes. There is no shortcut.

[storm5510]

I agree, it is a good suggestion. I'll see what I can find.

[Harvey563]

I my opinion the very best reference for what you want to do is:

H. Riesel, Prime numbers and computer methods for factorization, Progress in Mathematics Vol, 126, Birkhäuser Boston, Boston, MA, 1994. ISBN 0-8176-3743-5.

It is clear. There are lots of examples in Pascal. And it is all about prime proving and factoring.

[storm5510]

Originally Posted by Harvey563

I my opinion the very best reference for what you want to do is:

H. Riesel, Prime numbers and computer methods for factorization, Progress in Mathematics Vol, 126, Birkhäuser Boston, Boston, MA, 1994. ISBN 0-8176-3743-5.

It is clear. There are lots of examples in Pascal. And it is all about prime proving and factoring.

I will check that out. Thanks.

I decided to start reading here, under "Trial Factoring".

http://www.mersenne.org/various/math.php

The next step is to eliminate exponents by finding a small factor. There are very efficient algorithms for determining if a number divides 2P-1. For example, let's see if 47 divides 223-1. Convert the exponent 23 to binary, you get 10111. Starting with 1, repeatedly square, remove the top bit of the exponent and if 1 multiply squared value by 2, then compute the remainder upon division by 47.

Remove Optional
Square top bit mul by 2 mod 47
------------ ------- ------------- ------
1*1 = 1 1 0111 1*2 = 2 2
2*2 = 4 0 111 no 4
4*4 = 16 1 11 16*2 = 32 32
32*32 = 1024 1 1 1024*2 = 2048 27
27*27 = 729 1 729*2 = 1458 1

Thus, 223 = 1 mod 47. Subtract 1 from both sides. 223-1 = 0 mod 47. Since we've shown that 47 is a factor, 223-1 is not prime.

In the example above, the author tests 223 - 1 to see if it will divide by 47. Taking 1 away from both sides, he ends up with zero, meaning not prime.

Below is a variation of that same procedure I tried in Excel. What I did was to take the same value and place it on both sides. 479 and 1087 are prime numbers. Not Mersenne. 893 is not prime.

The spacing went to crap! Down the left side is the binary string as shown across the top. An "x" appears on the same rows as a binary "0" to indicate the multiply-by-2 is not done. The last number of each row is the Modulo.

479 111011111 Mod

1 - 1 2 2
1 - 4 8 8
1 - 64 128 128
0 - 16384 x 98
1 - 9604 19208 48
1 - 2304 4608 297
1 - 88209 176418 146
1 - 21316 42632 1


893 1101111101 Mod

1 - 1 2 2
1 - 4 8 8
0 - 64 x 64
1 - 4096 8192 155
1 - 24025 48050 721
1 - 519841 1039682 230
1 - 52900 105800 426
1 - 181476 362952 394
0 - 155236 x 747
1 - 558009 1116018 661


1087 10000111111 Mod

1 - 1 2 2
0 - 4 x 4
0 - 16 x 16
0 - 256 x 256
0 - 65536 x 316
1 - 99856 199712 791
1 - 625681 1251362 225
1 - 50625 101250 159
1 - 25281 50562 560
1 - 313600 627200 1
1 - - -

In the first and third test, on known primes, I ended up with one. Remove that from the right, as in the left, and I have zero. The center example ends at 661. The GCD of 893 and 661 is 1.

I wasn't expecting this type of result. I assumed anything on the GIMPS site would be exclusive to multiples of two. The strange part is, I can make this work in Excel, but not in code.

[storm5510]

This is the exception; result is two with prime number 101.

101 1100101 Mod

1 1 2 2
1 4 8 8
0 64 x 64
0 4096 x 56
1 3136 6272 10
0 100 x 100
1 10000 20000 2

[davieddy]

Try reading your "Quick and Dirty" thread again.