Tag: integer factorization
-
Integer Factorization: Quick Observation
Advertisements Examining the series of real values of x for which f(x)=x2+2cx+r is a perfect square, when m=c2-r is the number we wish to factor, c is the Ceiling Root, and r is the difference between m and the Ceiling Square, is not evidently any better – and is in fact a slower and unenlightening…
-
Integer Factorization: When x^2+2cx+r Yields a Perfect Square
Advertisements For odd positive integer m=c2-r, define the characteristic polynomial f(x)=x2+2cx+r. We are looking for the least nonnegative integer x for which f(x) is a perfect square. Completing the square of the polynomial may give us a way to find values of x given f(x). I decided to try to determine when f(x) = 0,…
-
Integer Factorization: A More Uniform Test, and a Similar Result
Advertisements For 100 pairs of randomly-chosen p and q less than 100,000,000: the Perl routine factor_it_4.pl performed as shown in the following scatter plot of m=pq vs. the number of iterations it required to factor m: Notice, as I mentioned in my blog post about the previous, less uniform test, that the number of iterations…
-
My Integer Factorization Study: Leading Me Ever Back
Advertisements As I’ve previously shared, my math study seems to lead me in kind of a circular path, between periods of great excitement at potentially profound discoveries, and “letdown” periods where I realize what I “discovered” is something not only already evident, but blindingly obvious. I still want to remain happily agnostic about which of…
-
Integer Factorization: Performance Stats/Graphs for factor_it_4.pl
Advertisements I ran factor_it_4.pl 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…
-
My Fastest Factorization Script So Far
Advertisements This won’t set any algorithmic speed records, but I am happy with it, for now. It comes in at 48 lines of Perl code. factor_it_4.pl is definitely faster than factor_it_3.pl, and routinely gets its answer in fewer than half the iterations of factor_it_2.pl. Once again, I am not experienced with writing arbitrary-precision arithmetic scripts…
-
Integer Factorization: Quick Summary of Last Night’s Simplification “Revelation”
Advertisements Let m be an odd positive integer we wish to factor. Let c be the smallest integer (also positive) so that c2>m. (If m is a perfect square, we are done.) Set r=c2-m. The least non-negative value of x for which x2+2cx+r is a perfect square is a value of x which produces s=c+x…
-
Integer Factorization: 9/18/2022 Update (short)
Advertisements It would seem, after reviewing factor_it_2.pl, that that code and the mathematics behind it are not due for an update – because they are beyond hope! 😀 No, really, I’ve moved far beyond those ideas, and they no longer seem fruitful enough to upgrade them. It would be like grafting a car onto a…
-
Integer Factorization: Recent Work
Advertisements Ideas kept me up when the dogs got me up around 3 a.m. this morning for a walk and some water. That’s good, even though the ideas did not pan out to much. I had church to attend in a few hours, after all. But it occurs to me to share where it’s all…
-
Integer Factorization: Web-Publish in Haste, Repent at Leisure! 😀
Advertisements All right, I am very sorry… I did happen to see that huge error in arithmetic in computing the characteristic function, but not until late tonight. I have fixed it and placed the updated code in my original characterize.pl post. Again, I do apologize for that. But now I am excited again because until…