Integer Factorization: A More Uniform Test, and a Similar Result


For 100 pairs of randomly-chosen p and q less than 100,000,000:

Screenshot 1

the Perl routine performed as shown in the following scatter plot of m=pq vs. the number of iterations it required to factor m:

Screenshot 2

Notice, as I mentioned in my blog post about the previous, less uniform test, that the number of iterations appear strongly influenced by how close p and q are to each other. This also strongly influences the size of m. That’s an important caveat. Scrupulous persons or processes could provide values of m that would maximize the computation time by choosing values of p and q that are not close together, but that also don’t have their lesser prime so small as to add vulnerability to some other approach.

Leave a ReplyCancel reply