2
$\begingroup$

What is computational complexity of finding factors of two almost prime number N, which is not divisible by 2 and 3 and 5?

Can we help our selfs with knowledge that we know digit sum of that number and that we know every digit of that number N

example:341 S(341)=8 = S(1*8) = S(2*4) = S(7*5) Last Digit of number 341 is 1 and this is result of two factors which have last digit 1 and 1 or 3 and 7 or 9 and 9

1 Answers 1

4

The exact complexity of integer factorization is unknown. The best known algorithms have complexities (relative to the number of digits in the number to be factored) larger than any polynomial but smaller than any exponential function. It is not known whether any polynomial-time algorithms exist.

Since factorization is NP, a proof of $P=NP$ would imply that factorization is possible in polynomial time. But factorization is not known to be NP-complete, so it is conceivable that it can be done in polynomial time even if $P\ne NP$.

To the best of my knowledge, digit sums or last-digits are not particularly helpful for factorization. They just give the number modulo 9 or 10, and division by arbitrary constants is "fast" at the timescales we're working with anyway.

  • 1
    For 3-digit numbers, analysis of the last digit may be helpful. For 3$0$0-digit numbers, not so much - and it's 300-digit numbers that are interesting, from a factorization point of view.2011-12-30