Factorization of prime number products

Question

I've making some research about RSA, and see that it is working with products of two prime numbers and difficulty of factorization... But why we can't make assumptions of primes like this way...

Here is a example, 27221 is product of two three digit primes, so we can think last digits of primes can be

ab1

cd1

or

ab9

cd9

or

ab3

cd7

or

ab7

cd3

So it seems to me thinking like this and going backwards for every digit of products with computer power could work. What is problem of my logic?

Answer 1

Just example: $$p\times q = 6460651 \times 3765833 = 24329732737283.$$

$\bmod 10$: last digit '$3$': there are $4$ pairs of candidates ($2$ ordered ones): $$\_\_1\times\_\_3,\\ \_\_3\times\_\_1,\\ \_\_7\times\_\_9,\\ \_\_9\times\_\_7.$$

$\bmod 100$: last digits '$83$': there are $40$ pairs of candidates ($20$ ordered ones): $$\_\_01\times\_\_83,\\ \_\_11\times\_\_53,\\ \_\_21\times\_\_23,\\ \_\_31\times\_\_93,\\ \cdots \\ \_\_79\times\_\_77, \\ \_\_89\times\_\_47, \\ \_\_99\times\_\_17.$$

$\bmod 1000$: last digits '$283$': there are $400$ pairs of candidates.

$\bmod 10000$: last digits '$7283$': there are $4000$ pairs of candidates.

$\;\;\cdots$

$\;\;\cdots$

Complexity grows exponentially.

Number of candidates is comparable with value described by 'last digits'. Finally, number of candidates is comparable with the whole product.

Of course, we can stop this process considering exactly one half of last digits (digits '$2737283$' of this example). But it cannot help essentially: number $\sqrt{p\times q}$ is huge too in practice.

Answer 2

you can't reduced it other than that since a necessary condition for primes is that they end with $1,3,7,9$ but there is no condition about second digit or third or fourth and so on..., so this is the limit of this approach.