 # Thread: Partial prime factorization of big number using trial division

1. ## Partial prime factorization of big number using trial division

Hello,
I´d like to make an app for partial prime factorization using trial division - BigInteger. Kinda works, but when I type big number (15 digits), I´ve got an error: Arithmetic operation resulted in an overflow.

I thought that problem is in listbox limited values that can handle, but it does not work even with small numbers (65459641964). Also, I want to pause factorization when I press the alt+c key, shows the factors incl. composite, and, most importantly, I want to make a support for 400 digits in length. Also, it will be good if things could work via other way than via listbox. BigInteger class is declared, but maybe incorrectly. I need only partial factors.

Code:
```Option Strict On
Imports System.Numerics
Public Class Form1
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
Dim number As BigInteger = CType(CDbl(CInt(TextBox1.Text)), BigInteger)
Dim factor As BigInteger = 2
While number > 1
If number Mod factor = 0 Then
number = number / factor
Else
factor += 1
End If
End While
End Sub
End Class```
Thanks.  Reply With Quote

2. ## Re: Partial prime factorization of big number using trial division

I thought we discussed this in an earlier thread. Don't use
Code:
`Dim number As BigInteger = CType(CDbl(CInt(TextBox1.Text)), BigInteger)`

The TryParse approach is better if you are getting the numbers from a TextBox as the user might enter something that is not numeric, and the use of TryParse would prevent your program from crashing in that case.  Reply With Quote

3. ## Re: Partial prime factorization of big number using trial division

CInt is part of the problem, CDbl is the other part of the problem. You may be ending up with a BigInteger, but you are trying to go through both Integer and Dbl along the way. Since the number won't fit in an integer, it fails on that step. It might fit in a double, but it also might not, and since there is no reason to make it a double, since you want it to be a BigInteger eventually, skip that entirely and do as Inferrd said.

Just because you end up where you want to be, and do it all in a single line, the compiler will not skip the intermediate steps that you have told it to perform.  Reply With Quote

4. ## Re: Partial prime factorization of big number using trial division

Using your code, if someone were to enter a prime number N, your while loop checks if N is divisible by every number from 2 to N.

Using just Long variables, I ran your code against the number 1500450271. It took over 4 minutes to come back and report that:

"The prime factors of 1500450271 are
1500450271"

It divided 1500450271 by every integer from 2 to 1500450271 to get there. The largest integer a number N can possibly be divisible by is N/2, so every value past N/2 can't possibly be a prime factor of N. So that is a huge inefficiency in your code to begin with.

But even further, if you have a number N, that is a product of two prime numbers, p and q (meaning N = p*q, and p <= q), then the following is true:

(p < sqrt(N) AND q > sqrt(N)) OR (p = q = sqrt(N))

The bottom line is, your loop should terminate when the "factor" variable is greater than sqrt(number), at which point you can conclude that the value in "number" is the final prime factor of the original value.

I made that simple change to your code and ran it against 1500450271 again and it determined that 1500450271 is the only prime factor in less than a second.

Also, since your code says "the prime factors are...", it isn't clear to me why you are incrementing your factor variable by 1. That means that you are trying to divide the "number" variable by even numbers other than 2, which obviously aren't prime. They will never erroneously be reported as prime factors, of course, but doing it that way causes multitudes of pointless calculations that will never result in a prime factor being found. All it does is slow your code down even more for no reason.

That's a nice wish list you have in your opening post about what you would like to do with your code. Good luck writing it. Some of it just isn't possible. Prime factoring a 400 digit number isn't feasible. Imagine if that number is the product of two 200 digit prime numbers. You're going to start at 2 and check divisibility by every integer between 2 and (200 digit prime number)? Not gonna happen.

Good luck.  Reply With Quote

5. ## Re: Partial prime factorization of big number using trial division Originally Posted by OptionBase1 You're going to start at 2 and check divisibility by every integer between 2 and (200 digit prime number)? Not gonna happen.

Good luck.
Technically, not gonna happen in any reasonable amount of time. If we say that you can check 2 billion numbers 1x10^9 in 1 second, and you want to check a number that is 1x10^200, then that would take 1x10^191 seconds, which is a VERY long time.

The problem is certainly an interesting one, as it has a lot to do with cryptography. Factoring VERY large numbers is so prohibitively time consuming that it is considered essentially unsolvable. However, if you could subdivide the problem into a LOT of very small chunks and run them all in parallel, then it might be solvable. A CPU can't really do that, because most computers have no more than 6 to 8 cores at the most, which means that they can only efficiently run 6 to 8 simultaneous threads (they could run more in some cases, but these threads would have no waiting, so the practical cap is probably not higher than one per core). On the other hand, GPUs can have over two thousand cores, these days (unless I misread that), and since the math demand is so small, they could likely each handle a thread like this would require. Still, if you had a system with ten such GPU boards in it, you'd only be increasing your processing by a factor of about 2x10^4, which would still take roughly forever to get through the problem.  Reply With Quote

6. ## Re: Partial prime factorization of big number using trial division

The same poster posted recently about wanting to generate 100 digit primes in under 4 minutes and several of us attempted to explain why that isn't feasible. So, they come back and then talk about wanting to do prime factorization of 400 digit numbers?   The only reason I have taken the time to reply here and in past threads is to hopefully encourage the poster to not waste their own time with numbers this large; certainly not with the code they posted.

That's why I've repeatedly encouraged this poster to always start by getting something written that does what they want to do in small scale first (limit yourself to Long variables), get the code working as fast as possible, and then go from there. And that advice seems to continue to be ignored. So I will keep doing it when they come back with a new post about doing something prime related with 1000 digit numbers.  Reply With Quote

7. ## Re: Partial prime factorization of big number using trial division

Yeah, I recognized the post, as well. I assume they haven't worked through the true cost of what they are trying to do, so I was trying to put some numbers to it. This is a common issue. Computers can do things so very fast that they can be effectively instantaneous for small subsets. For example, finding the prime factors of a number up to a billion doesn't have to take much time at all. Therefore, people may think that the same short time will be true for much larger problems and don't scale it up correctly. We often see this with combinatorial questions where somebody wants to get all possible combinations from some set. The design works great for small sets, and they don't realize that it's an exponential series that will take an unreasonable amount of time when the set gets slightly larger. The key, I feel, is working through the actual expected cost to show that just because it works fine for a subset of the problem doesn't mean that it will work fine for the actual problem.  Reply With Quote

8. ## Re: Partial prime factorization of big number using trial division

I went back and looked at a Sieve I wrote and found this performance(at the time)

' Performance based on Intel Dual Core @ 2.5GHz
' number of primes verified at http://primes.utm.edu/howmany.shtml
' Primes less than:
' 1,000,000 Number of Primes: 78,498 less than .02 second
' 10,000,000 Number of Primes: 664,579 less than .1 second
' 100,000,000 Number of Primes: 5,761,455 less than .7 second
' 1,000,000,000 Number of Primes: 50,847,534 about 11 seconds
' 2,000,000,000 Number of Primes: 98,222,287 about 24 seconds
' 6,000,000,000 Number of Primes: 279,545,368 about 1.25 minutes

If I can find the program I'll bet the numbers would be better because of faster processor.  Reply With Quote

9. ## Re: Partial prime factorization of big number using trial division

I want implement something like this. Note that I don´t want to factor it fully.

Code:
```sage: a = 207411784165069788403685789342707568622276103
sage: f = trial_factor(a)

Trying primelike factorisation of
# = 207411784165069788403685789342707568622276103

# = (45-digit composite)
# = (44-digit composite) * found new prime divisor: 19
# = (42-digit composite) * (prime divisors above) * 29
# = (41-digit composite) * (prime divisors above) * 37
# = (38-digit composite) * (prime divisors above) * 929
# = (32-digit primelike) * (prime divisors above) * 518717
^C
Factoring interrupted. So far, obtained:
# = 19 * 29 * 37 * 929 * 518717 * (32-digit primelike)
where the final (32-digit primelike) is
21112220300468085766530282304433
sage: f
[(19, 1),
(29, 1),
(37, 1),
(929, 1),
(518717, 1),
(21112220300468085766530282304433, 1)]```
So I want to partially factor my number, then interrupt the process after some period of time (say 1 minute) and see what has been found. I´m OK with trial division.

BigInteger is the only method for my numbers due to their size. I agree that many things that I´m trying to achieve are impossible (such as generation very long prime numbers), but what I want to do is to STOP the process after some period of time and see what has been found (like in this case). Hope it´s more clear now...  Reply With Quote

10. ## Re: Partial prime factorization of big number using trial division

The easiest way to do that would be if the calculations were performed using a BackgroundWorker component. There would be a loop somewhere in there, probably to check each number. At the start of each loop, check whether cancelation is pending, which is a feature of the BGW component. Alternatively, you could put a Boolean variable at form or global scope and check that, but since the BGW has a built in mechanism for cancelation, that's the better way to go. If the cancelation is pending, then quit the loop.

The issue is that such a long running math operation will take all the attention of whatever thread it is running on. If you run it on the UI thread, it will block the UI from responding to any user input. The program will appear frozen, and you won't be able to press any buttons. Therefore, you need to move that long running operation to a background thread. The BGW is an ideal means to do that, because it doesn't just have that cancelation mechanism, it will also raise progress events on the UI thread if you want it to. Therefore, you could raise the event every time you found a prime. The UI thread would then be able to handle those events and show the primes in something like a listbox. You could stop it at any point, because the UI thread would be fully responsive, but you'd also be able to see the progress as you go.  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

Featured