1
$\begingroup$

If I have an composite integer called $x$, is it possible for me to calculate what the resulting number will be if I add a random integer, denoted by $n$, to all of the factors of $x$ (without factorising $x$, adding $n$ to all of the factors, and then multiplying those numbers to get the resulting number)?

For example, If $x = 30$, and $n = 2$, is it possible for me to calculate the resulting number if I add $2$ to all of the prime factors of $30$ without factorising $30$, adding $2$ to all of its prime factors $(2, 3$ and $5)$, and then multiplying them to get the resulting number $(140$ in this case as $(2+2) * (3+2) * (5+2) = 140)$?

$\endgroup$
6
  • $\begingroup$ Do you mean like $$(n + p_1) \times (n + p_2) \times (n + p_3)$$ equals $$n^3 + n^2(p_1 + p_2 + p_3) + n(p1p_2 + p_1p_3 + p_2p_3) + p_1p_2p_3 ~?$$ Are you wondering how to generalize this to $$\prod_{i=1}^r \left(n + p_i^{a_i}\right),$$ where the prime factorization of the pertinent number is $$\prod_{i=1}^r p_i^{a_i} ~?$$ $\endgroup$
    – user2661923
    May 28, 2022 at 10:50
  • $\begingroup$ @user2661923 I read the question as generalizing to $$\prod_{i=1}^r (n+p_i)^{\alpha_i}$$ $\endgroup$
    – Keith Backman
    May 28, 2022 at 14:33
  • 2
    $\begingroup$ @KeithBackman Your interpretation seems very plausible to me. Seems like the OP (i.e. original poster) needs to clarify this ambiguity. $\endgroup$
    – user2661923
    May 28, 2022 at 14:35
  • $\begingroup$ @user2661923 I am not exactly interested in generalising it in that way because it seems that even if I do generalise it, I will still have to factorise, add and multiply to get the final result. I am more interested in a method that will allow me to do this with very large numbers (with large numbers of factors) in a small number of steps. $\endgroup$
    – liam casey
    May 28, 2022 at 22:03
  • $\begingroup$ The start of my first comment shows the complexity of the $3$rd degree polynomial in $n$ that is created by $$\prod_{i=1}^3 (p_i + n).$$ If you consider the more general $k$th degree polynomial created by $$\prod_{i=1}^k (p_i + n),$$ there is a clear rule governing the final result. The coefficients of each of the terms will follow rules very similar to those represented by Vieta's formulas. $\endgroup$
    – user2661923
    May 29, 2022 at 2:40

1 Answer 1

Reset to default
5
$\begingroup$

No, you can't assume that this is easily possible. There are cryptosystems like the RSA-System, where the security is based on the fact that the factorization of the product of two sufficiently large primes isn't feasible.

Assume now that you have a number $$m=p_1p_2 \tag 1$$ that is the product of such two primes and there is an $n$ such that $$s=(p_1+n)(p_2+n)\tag 2$$ can be calculated easily. Then from $(1)$ and $(2)$ follows $$p_1+p_2=\frac{s-m-n^2}n=:A \tag 3$$ and further $$p_2=A-p_1 \tag 4$$ If we substitute $(4)$ in $(1)$ when we get the quadratic equation $$m=p_1(A-p1)\tag 5$$ which can be easily solved so that we get a prime factors of $m$. This contradicts our assumption that $m$ cannot be easily factored.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .