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

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;
}