Integer Factorization: Performance Stats/Graphs for


I ran tonight on the collection of 10-digit and 12-digit discrete semiprimes I had generated earlier in my study. An image of the table I generated is below, along with scatter plots of particular behaviors. If someone wanted, I could certainly supply them with the raw data used to generate the graphs. I include them here to help my reader visualize some apparent findings:

When m=pq is a discrete semiprime, the product of prime numbers p and q, the Perl script finds those prime factors fastest when p and q are close together. This, I think, causes the downward trend in the number of iterations required when graphed against the size of m. That might be an artifact of how I generated the data: for the 10-digit primes, I used standard math library functions available for Perl to generate two random primes less than 10000, and multiplied them together. For the 12-digit primes, they were random primes less than 1000000. Someone at some point could use a different dataset for a more homogeneous graph: Produce a set of random dots on a square, then let the x and y coordinates of that square range from 0 to MAXSIZE, and for each of the dots, find the nearest prime numbers for the x and y coordinates and multiply them together. But I’m just spitballin’.

The values in each row of the table are m, the number to be factored; c, the Ceiling Root of m; r which is c2-m; p and q, the prime factors of m, in order; Iters, the number of iterations required to factor m; and p/q.

The scatter plots I put next to the chart of values are of m vs. the number of iterations, and the number of iteratios vs. p/q, where p and q are the prime numbers whose product is m, with p<q.

Leave a ReplyCancel reply