one thing leads to another…

The Prime Factor Calculator Project in Csharp

And

Insights Into Internet Security

For ease of writing, I’ll call the **P**rime **F**actor** C**alculator, the **PFC**.

Lock The Gates!

Background

**The Original Plan – Build a personal Class Library**

The **Prime Factor Calculator app** (in C#) is an unintended byproduct of a recent “Class Library” project I started. My development projects are typically one-off programs and because of that I’d rarely take the time to put functionality into separate thoughtfully designed classes (let alone in a class library!). In general I would just code the routines I need as just additional functions in the overall program I’m working on. If I happen to need that functionality in a later project I’d just cut and paste code from the earlier project into the program(s) of the new project (and modify as needed). Yeah, sloppy. I know. But lately I have been wanting to use some earlier code in all new projects (in new programs). So, I decided to develop a Class Library with cleaner and more thoughtful versions of the functionality I want in it. And then to go back and clean up the earlier projects (making use of the new Class library).

In the new Class Library I decided I wanted (needed?) **a class to compute Prime Factors** for numbers that you pass to it. Although a Prime Factor computation class is conceptually simple, in practice it takes a fair amount of research to figure out how to actually accomplish the task. And, if you develop a class to compute Prime Factors you will obviously need something to test it with!! **The obvious thing to do is to develop a Prime Factor Calculator app (PFC).**

The way I approached the problem was to implement the prime factor computation code in a class contained ** within** the Prime Factor Calculator app.

.The Prime Factor Calculator app is developed in the Visual Studio IDE as a C# “WinForms” Desktop application… just in case you were wondering.

.

After the app is developed and tested I’d move the prime factor computation class to my new personal Class Library and delete it from the app itself. Then we test everything again. This is a simple and effective way to develop and test new classes.

In some sense we can think of the Prime Factor Calculator app (PFC) as just a ** test-driver** for the computation class; but in reality it is much more than that. It is a simple yet useful app if you happen to have a need for computing the Prime Factors of numbers. Of course, there are more than a few PF calculator apps available “on the internet.” But so what… that’s like telling a car enthusiast that there’s a lot of ’57 Chevys out there so why bother restoring one yourself. Anyway, just below is a short video that shows what this particular PFC app is and what it does.

You might find it interesting to understand the basic techniques that were used in the PF computation ** class** that actually does the factorization. It apparently came from somebody named

**Vishwas Garg.**It took me a little while to comprehend and appreciate how it works. It’s really quite ingenious and reputed to be pretty efficient. Anyway, you can find a link for, and a reprint, of his concept (pseudo-code) near the end of this post. All I did was implement it in C# using the MS .Net

**BigInteger**class.

While playing with and testing the PFC app it quickly became apparent that the amount of time needed to factor numbers increased non-linearly with the number of digits in the number.

As we can see, it’s a pretty “classic” looking graph. So I starting thinking about it and I suspected that the graph and its data should be able to be closely approximated with a simple **exponential** formula.

Thinking back about the many texts/articles one reads, especially texts on cryptography, they will often say that the effort to factor a number will increase with the square of the value of the number. E.g. a 4 digit number will take 10 times more cpu cycles than a 3 digit number. But when I ran that theory (presumption) against the actual PFC results it did NOT hold water! However, when using a spreadsheet to analyze the actual data it instead looked like the increase in time was roughly exponential based on 3.2 times the increase in the number of digits. For example, an 11 digit number required 3.2 times more cpu cycles to factor than a 10 digit number. And a 12 digit number required 3.2 times more cpu cycles than the 11 digit number; and so on.

Then there was that “aha” moment. ** 3.2 is roughly the square-root of 10!** This makes perfect sense because, when factoring numbers…

**The square-root of the number being factored is as high as we need to go in our calculations**. That is because a Prime Factor of a number (any number) can NEVER be greater than the square-root of the number being factored!

**And the factoring routine I was using accounted for that in its code… and that directly affects the cpu cycles needed to factor numbers!**

So the next thing to do is to add this “theory” (formula) to the spreadsheet and produce a new graph!

Look what happened!

As we can see, the **theoretical values** (red line) based on the “3.2 conjecture” **very** closely matches the **empirical reality **(blue line based on actual observations)!

The Relationship To Cryptography

So now we come back around to cryptography and the internet. As you probably know, on the internet it’s all about public key cryptography (think **SSL **and **https**); and public key cryptography is all based on the difficulty of factoring large numbers.

So with this PFC app it takes about 500 seconds on my personal computer to factor 21 digit numbers. If one was depending on encryption using 21 digit numbers it would not be difficult to “crack” the codes. It would take less than 10 minutes. But let’s extrapolate a little…

How about encryption based on 100 digit numbers? That would require about

500 x 3.16^{79} = 1.49 x 10^{42}seconds = ((1.49 x 10^{42}) / 86400) days… or…

about **17,000,000,000,000,000,000,000,000,000,000,000,000 days!**

But we might say, “Gerry… your computer is slow and your code is inefficient. Someone who writes really efficient code with a FAST computer could do better.” This is true. **However **…

.

Let’s assume some other computer is a ** trillion** times faster and someone else’s code is a

**billion times more efficient.**That still would require

**17,000,000,000,000,000 days to crack the code.**

.

**And even if, by some huge miracle you could shave off another 15 zeroes, all that’s needed is to increase the digit count from 100 to just 110 and we’re back up to over**

**2,700 years**to crack the code by factoring the number! As we can see, the “Encryptors” will have the advantage over the “hackers” for Zillions of years unless some miracle of discovery happens in the field of Number Theory.

Now all of this we already knew at some level but by developing our own Prime Factor Calculator, making some observations, creating some spreadsheets and charts, and doing just a little analysis, we are able to get an excellent appreciation for public key cryptography which is based on factoring large numbers and which underpins the internet we know today.

So it seems reasonable to say that the state of public key cryptography is quite safe unless someone comes up with an unbelievably efficient way to factor numbers. In other words, it would require more than just faster machines and more efficient code! It would require a major breakthru in number theory! But I dare say such a discovery would be more notable than Einstein’s theory of relativity.

None of the above is really “new” but now I’ve had the opportunity to gain a better appreciation by “touching” and “feeling” it by coding, testing, and analyzing it in the real world; in my loft; in front of my $600 computer.

Open The Gates!

The following represents, roughly, the technique used by the “PF computation class.” Actually I created 2 versions of this “code.” One is for factoring 64 bit unsigned integers (type **ulong** in C#). The other is for factoring HUGE numbers of arbitrary length via the **BigInteger** class which is part of Microsoft’s .Net class library.

One significant improvement I made to the routine is to move the **sqrt** calculation outside of the loops so that it’s only calculated once (it really only needs to be calculated once at the beginning of the function (and outside of the loops) as detailed earlier).

You may find it interesting to learn that, oddly enough,** the BigInteger class does NOT have a method for obtaining square roots! ** This means that we have to code our own square root routine which means we must code a binary search in order to get the square root of the numbers we want to factor! One thing leads to another… or… It’s always somethin’ ** So… when you see sqrt(n) in the Vishwas’s code below, that’s a whole other routine you must code if you want this stuff to work for big numbers! ooh! ooh! That could be another class to code and put in my class library! This shit never fucking ends!**

I found the routine at

http://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/

but there are other copies/versions (e.g. pseudo-code) that are easily found.

=========================================================

// A function to print all prime factors of a given n

void primeFactors(int n)

{

// Print the number of 2s that divide n

while (n%2 == 0)

{

printf(“%d “, 2);

n = n/2;

}

// n must be odd at this point.

// So we can skip one element (Note i = i +2)

for (int i = 3; i <= sqrt(n); i = i+2)

{

// While i divides n, print i and divide n

while (n%i == 0)

{

printf(“%d “, i);

n = n/i;

}

}

// This condition is to handle the case

// when n is a prime number greater than 2

if (n > 2)

printf (“%d “, n);

}

/* Driver program to test above function */

int main()

{

int n = 315;

primeFactors(n);

return 0;

}

Run on IDE

Output: 3 3 5 7

How does this work?

The steps 1 and 2 take care of composite numbers and step 3 takes care of prime numbers. To prove that the complete algorithm works, we need to prove that steps 1 and 2 actually take care of composite numbers. This is clear that step 1 takes care of even numbers. And after step 1, all remaining prime factor must be odd (difference of two prime factors must be at least 2), this explains why i is incremented by 2.

Now the main part is, the loop runs till square root of n not till. To prove that this optimization works, let us consider the following property of composite numbers.

Every composite number has at least one prime factor less than or equal to square root of itself.

This property can be proved using counter statement. Let a and b be two factors of n such that a*b = n. If both are greater than √n, then a.b > √n, * √n, which contradicts the expression “a * b = n”.

In step 2 of the above algorithm, we run a loop and do following in loop

a) Find the least prime factor i (must be less than √n,)

b) Remove all occurrences i from n by repeatedly dividing n by i.

c) Repeat steps a and b for divided n and i = i + 2. The steps a and b are repeated till n becomes either 1 or a prime number.

Thanks to Vishwas Garg for suggesting the above algorithm. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

The End