Thread: How to factor a number of 100 characters into prime factors in 1-2 seconds?

I have a really long number up to 100 symbols in length. For example:
93286507371999205962977351361478938826658030508392 0591925740371392254317064584855785088915745761
And I need to get this answer from it:
Prime factor of 93286507371999205962977351361478938826658030508392 0591925740371392254317064584855785088915745761 is:
995663^8 x 995669^8
I was able to do this with much lower numbers thanks to Sieve of Eratosthenes and signed long long int:

Code:

int main(int argc, char *argv[]){
    int ch = 0;
    signed long long int num;
    int div = 2;
    
    
    while ((ch = scanf("%lli", &num)) == 1)
    {
        if (num > 0){
            printf("Prime factor of %lli is:\n", num);
            if (num == 1){
                printf("%lli", num);
            }
            while (num > 1){
                int tmp = 0;
                long int limit = 1000000;
                int prime[limit+1];
                int arrprime[tmp];
                for(int i = 1; i <= limit; i++){
                    prime[i] = i;
                }
                for(int i = 2; i*i <= limit; i++){
                    if (prime[i] != -1){
                        for(int j = 2*i; j<= limit; j += i){
                            prime[j] = -1;
                        }
                    }
                }
                for (int i = 0; i < limit; i++){
                    if (prime[i] > 0){
                        arrprime[tmp] = prime[i];
                        tmp++;
                    }
                }
                
                int power = 0;
                for (int i = 1; i < tmp; i++){
                    while ((num % div) == 0){
                        num /= div;
                        power++;
                        if (num == 1){
                            break;
                        }
                        else{
                            continue;
                        }
                    }
                    if (power > 0){
                        printf("%d", div);
                        if (power > 1){
                            printf("^%d", power);
                        }
                        if (num > 1){
                            printf(" x ");
                        }
                    }
                    div++;
                }
            }
            printf("\n");
            div = 2;
        }
        
        else if(num == 0){
            return 0;
        }
    }
}

But this solution would not work with a big number like in the example (Mainly due to long code processing), so I can't really use the Sieve, nor I can use specialized libraries. So how do I get a prime factor out of a very long number (~100 symbols)?

So how do I get a prime factor out of a very long number (~100 symbols)?

In 1 to 2 seconds?
You don't.

If you want to numerically deal with the large numbers, then perhaps The GNU MP Bignum Library

Here is a link to an online factoring program that also includes source code, that finds the the factors for that large number in a fraction of a second.

Integer factorization calculator

The online factoring program accepts expressions, such as 2^512 - 1.

Originally Posted by rcgldr

Here is a link to an online factoring program that also includes source code, that finds the the factors for that large number in a fraction of a second.

Really? Try this:

Code:

1017803105208811141547706054010446761424659440478753690892748944869985260751624643110487274054409671

Obviously his extremely simple example number can be factored in a fraction of a second. But that's only because it's factors are small.

EDIT: Even a simple-minded program like the following can factor the given number in a fraction of a second.

Code:

#include <stdio.h>
#include <stdbool.h>
#include <gmp.h>
 
int main()
{
    const char *num = "932865073719992059629773513614789388266580305083"
                      "920591925740371392254317064584855785088915745761";
    // = 995663^8 * 995669^8
 
    mpz_t n;
    mpz_init_set_str(n, num, 10);
 
    unsigned long d = 2;
    int cnt = 0;
    bool first = true;
 
    while (mpz_cmp_ui(n, 1) != 0)
    {
        if (mpz_fdiv_ui(n, d) == 0)
        {
            ++cnt;
            mpz_fdiv_q_ui(n, n, d);
        }
        else
        {
            if (cnt > 0)
            {
                if (!first) printf(" * ");
                else        first = false;
                printf("%lu", d);
                if (cnt > 1) printf("^%d", cnt);
                cnt = 0;
            }
            d += 1 + (d % 2); // so it counts: 2, 3, 5, 7, 9, ...
        }
    }
 
    if (cnt > 0)
    {
        if (!first) printf(" * ");
        printf("%lu", d);
        if (cnt > 1) printf("^%d", cnt);
    }
 
    printf("\n");
    mpz_clear(n);
 
    return 0;
}

It's a mathematical problem rather than a programming problem, and certainly rather than a C problem.

An entire industry is based onthe premise that factoring large integer with large prime factors is hard. However an awful lot of research has been done on speeding up the process. I don't follow any of it personally - it's neither my talent nor an area of interest for me. I would imagine that most of the literature is pretty inaccessible to a person with only high school math skills.