Results 1 to 10 of 10

Thread: Partial prime factorization of big number using trial division

  1. #1

    Thread Starter
    Addicted Member
    Join Date
    Oct 2018
    Posts
    141

    Partial prime factorization of big number using trial division

    Hello,
    Id like to make an app for partial prime factorization using trial division - BigInteger. Kinda works, but when I type big number (15 digits), Ive 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
            ListBox1.Items.Add("The prime factors of are")
            While number > 1
                If number Mod factor = 0 Then
                    ListBox1.Items.Add(factor)
                    number = number / factor
                Else
                    factor += 1
                End If
            End While
        End Sub
    End Class
    Thanks.

  2. #2
    Frenzied Member
    Join Date
    Jul 2011
    Location
    UK
    Posts
    1,282

    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)
    Instead, use BigInteger.Parse or BigInteger.TryParse.

    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.

  3. #3
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    35,126

    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.
    My usual boring signature: Nothing

  4. #4
    Frenzied Member
    Join Date
    Nov 2017
    Posts
    1,101

    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.
    Last edited by OptionBase1; Jan 13th, 2020 at 07:14 PM.

  5. #5
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    35,126

    Re: Partial prime factorization of big number using trial division

    Quote Originally Posted by OptionBase1 View Post
    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.
    My usual boring signature: Nothing

  6. #6
    Frenzied Member
    Join Date
    Nov 2017
    Posts
    1,101

    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.

  7. #7
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    35,126

    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.
    My usual boring signature: Nothing

  8. #8
    Powered By Medtronic dbasnett's Avatar
    Join Date
    Dec 2007
    Location
    Pointless Forest 38.517,-92.023
    Posts
    9,271

    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.
    My First Computer -- Documentation Link (RT?M) -- Using the Debugger -- Prime Number Sieve
    Counting Bits -- Subnet Calculator -- UI Guidelines -- >> SerialPort Answer <<

    "Those who use Application.DoEvents have no idea what it does and those who know what it does never use it." John Wein

  9. #9

    Thread Starter
    Addicted Member
    Join Date
    Oct 2018
    Posts
    141

    Re: Partial prime factorization of big number using trial division

    I want implement something like this. Note that I dont 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. Im OK with trial division.

    BigInteger is the only method for my numbers due to their size. I agree that many things that Im 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 its more clear now...
    Last edited by VB.NET Developer; Feb 2nd, 2020 at 06:42 AM. Reason: added explanation

  10. #10
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    35,126

    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.
    My usual boring signature: Nothing

Posting Permissions

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



Click Here to Expand Forum to Full Width