Sign into an existing account

It turns out, karasuba's method can sort of be inversed for estimating the smallest digits of a semiprime.

How we do it is we start by iterating i, and j, representing the smallest digits of a semiprime n's potential factors p and q.

We run i and j up to 10,0000 each. We multiply i and j. We then match their positional digits with the corresponding positional digits in n, and log them to a results array if they match. (leaving off the leading digit of the product of i and j when we perform the check for matches).

The results of this array will always contain the partial digits, at the correct magnitude, for the factor of n=pq

This can be repeated for the other digital groups of n.

The result arrays for each group are 2000 elements each.

We repeat this process with the limit of i and j set to 1000.

We then filter this second result group based on the first result group and end up with < 200 potential candidates.

We also check to confirm [i, j] and [j, i] are not already in the results, to avoid duplicates.

For example, with
p=66431
q=6044767
n=pq=401559916577

The results of this algorithm yield:

[[1, 77], [7, 11], [9, 53], [31, 67]]

And in fact if you multiply any of these pairs together, 177, 711, you will find
it reproduces the first two digits of n. N is the target for determining what the digits of its own factors are. Any pair product that doesn't reproduce the digits of n, cannot by definition be the potential digits of n's factors p and q, QED.

In practice a group of three digits will yield about 200 results each time, and each group requires about one million iterations to generate.

With each set of results, we then have to test all combinations.

For a nine digit number the savings are about 900%.
The search space advantage grows exponentially with the size of the semiprime in question.

While the current fset algebra, attacks the problem from the left, yielding the magnitude and leading digit of a semiprimes smallest factor, this algorithm attacks the problem from the right, yielding the smallest digits first.