2
$\begingroup$

I was thinking about semiprime factorization, and I had an idea of an algorithm:

Let's take a small semiprime for this example: 3053. So we have to primes p and q that p×q=3053.

Now we go digit to digit checking all possibles multiplications.

The last digit is 3. This means that p and q must have as last digit one of this combination: 1 and 3 or 7 and 9.

So we know that p is like x1 and q x3 or p is like x7 and q x9. Where x is any number. In this case, q is 43 and p 71.

And repeat for every digit on the semiprime, with the proper corrections. So you can calculate p and q intuiting the digits.

Do you think if is a reasonable algorithm to factorize small semiprimes?


Edit. Let´s do this fancier.

Consider two primes of 4 digits length. And $n$ as a semiprime:

$$abcd \times efgh = n$$

So, we can express it with the classic multiplication:

$$ \begin{matrix} & & & a & b & c & d \\ & & & e & f & g & h \\ \hline & & & ha & hb & hc & hd\\ & & ga & gb & gc & gd\\ & fa & fb & fc & fd\\ ea & eb & ec & ed\\ \hline x_6 & x_5 & x_4 & x_3 & x_2 & x_1 & x_0\\ \end{matrix} $$

Note that $x_i$ are a number between 0 and 9, CARRY are added to $x_{i+1}$. So we can write the semiprime as:

$$x_7 x_6 x_5 x_4 x_3 x_1 x_0 = n$$

Now, you check every $x_i$:

  • For $x_0$ you must find $h$ and $d$. $$ hd =x_0$$
  • For $x_1$ you must find $c$ and $g$. $$ hc+gd =x_1$$
  • For $x_2$ you must find $b$ and $f$. $$ hb+fd =x_2 -gc$$ Note that $x_2 -gc$ must be possitive.
  • And repeat.

The key here is: How much numbers between 0 and 9 solve the equation $ax +by = x_n$? $a$ and $b$ are always given by previous steps.

As Oldboy let`s call this $S$. So given a semiprime of length $m$ we need to check $S^m$ possibilities.

Now, How much is $S$? With a fast example, I calculated that $S$ are between 5 and 6.

In conclusion, with this algorithm, you need to check $6^m$ numbers. With a semiprime of 100 digits, exists $6^{100}$ possibilities.

$\endgroup$
  • 1
    $\begingroup$ When you say "for every digit on the semiprime", what do you have in mind for the other digits? The last digit is considerably easier to handle than the others. $\endgroup$ – Misha Lavrov Sep 10 '18 at 22:03
  • $\begingroup$ To factor small numbers, just apply trial division. I do not think that the mentioned method will be significantically faster. $\endgroup$ – Peter Sep 11 '18 at 8:24
0
$\begingroup$

This is too long for a comment so I'm posting this as an answer.

Suppose that you have a semiprime $N$ made of 2 four-digit numbers: $abcd$ and $efgh$. It means that:

$$(1000a + 100b+ 10c+d)\times(1000e+100f+10g+h)=N$$

Step 1: The first digit of $N$ from the right is equal to the last digit of $dh$. You can specualte about the possible combinations of $d$ and $h$ based on the last semiprime digit. You will definitely have a few combinations.

Step 2: The second digit of $N$ from the right is equal to the last digit of: $ch+dg+CARRY$, with $CARRY$ being a carry-over from the previous step. Note that we introduced two new variables here, $c$ and $g$ and we have to combine each option from the step 1 with all valid options from the step 2.

Step 3: The third digit of $N$ from the right is equal to the last digit of: $bh+cg+df+CARRY$. Note that we introduced two new variables here, $b$ and $f$ and we have to combine each option from the steps 1 and 2 with all valid options from the step 3.

Step 4: The fourth digit of $N$ from the right is equal to the last digit of: $ah+bg+cf+de+CARRY$. Note that we introduced two new variables here, $a$ and $e$ and we have to combine each option from the steps 1, 2 and 3 with all valid options from the step 4.

Beyond this point we are introducing no new variables into our equations. Based on chosen values for $a,b,c,d,e,f,g,h$, for each possible combination of values from steps 1-4, we just have to check if the remaining digits of the semiprime are correct.

Notice that in steps 2, 3, and 4 we have to solve the equation of the following type for single-digit values of $x,y$:

$$a_1x + a_2y\equiv a_3\quad\text{(mod 10)}\tag{1}$$

...with values for $a_1,a_2,a_3$ coming from previous steps. The key question here is how many solutions does this equation have? I'm not an expert but suppose that the average number of solutions for randomly chosen $a_1, a_2, a_3$ is $S$.

So the total number of options that we have to check is approximately $S^3$, multiplied by the number of options in step 1 which is actually not so important because it shows up only once.

And now for a ballpark estimate (just imagine a BIG ballpark):

If you have a semiprime $N$, approximate number of its decimal digits is $\log N$ and each prime factor will have about $\frac12 \log N$. It means that the complexity of this algorithm is of the order:

$$O(S^{\frac12\log (N-1)})=O(S^{\frac12 \frac{\log_S N}{\log_S 10}})=O(\sqrt{N}^\frac1{\log_S 10})\tag{2}$$

To factorize a semiprime by doing simple, brute-force divisibility check, you should try all numbers from 1 to $\sqrt{N}$, possibly skipping some obvious non-primes. In the worst case when you just jump from one number to the next the complexity is:

$$O(\sqrt{N})\tag{3}$$

So which one is better: (2) or (3). It all depends on the value of S :) If it is around 10, this method, however naive it may look, is not so inferior.

Please have mercy, I have never speculated so much in any of my previous posts.

$\endgroup$
  • $\begingroup$ Thanks for your response, with your feedback I updated the question. $\endgroup$ – Mr.Joe Sep 13 '18 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.