Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

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.

share|cite|improve this answer
Thank you for answer Henning. I was thinking that for given almost prime number N, for example 341 we can maybe find exact combination of products of last digits (a+1)(b+1) or (a+3)(b+7) or (a+9)(b+9). I tried with next algoritm:… where i generalised d accordingly to these tree posibbilities but my knowledge of modular arithmetics of polynomials is not good. Maybe it is even not posible with that alghoritm!? – user21973 Dec 30 '11 at 0:32
For 3-digit numbers, analysis of the last digit may be helpful. For 300-digit numbers, not so much - and it's 300-digit numbers that are interesting, from a factorization point of view. – Gerry Myerson Dec 30 '11 at 3:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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