1
$\begingroup$

Suppose I have some super fancy algorithm for prime factorization. I want to demonstrate its potential on a difficult case, like an RSA sized number composed of two primes,$\space n=p_1p_2$. As far as I know, 2-factor primes are considered to be most difficult. I want to demonstrate that it performs in a good runtime. Would it be considered cheating to hard code into the algorithm an expression that checks immediately after finding $p_1$ whether the $n$ contains a $p_2$ such that $p_2= \frac{n}{p_1}$ and terminating if it is so?

Would this be okay for demonstration purposes? Would it fly in an RSA challenge? Is a provision for such difficult cases a faux-pas in algorithm design?

Improve this question
$\endgroup$
4
  • $\begingroup$ What do you mean by "differ by one bit"? Do you mean their length differs by one bit, or the binary representations of p and q has Hamming distance 1? Please edit your question to clarify what you are asking? $\endgroup$
    – D.W.
    Jul 11, 2022 at 16:54
  • $\begingroup$ If you know one prime factor $p_1$ of $n$, and you know $n$ has just two prime factors, then you can very quickly compute the second prime factor $p_2$ using $p_2 = n/p_1$. So, once an algorithm finds $p_1$ in this context, it is essentially done (it has the full factorization of $n$). $\endgroup$
    – Neal Young
    Jul 11, 2022 at 16:59
  • $\begingroup$ Edited, thanks! $\endgroup$
    – Würthi
    Jul 11, 2022 at 17:01
  • $\begingroup$ Further insight: If you find a prime factor $p$, it's totally legitimate to just return it and not worry about the cofactor. Partial factorization algorithms like ECM are definitely useful, and in the case of semiprimes they solve the problem completely. Indeed, if you find a composite 1 < m < n, that's useful too, even without having any more factors. $\endgroup$
    – Charles
    Apr 13 at 15:19

1 Answer 1

Reset to default
2
$\begingroup$

It's not cheating. The last step of an algorithm can certainly be: compute $n/p_1$ and check whether that is an integer and is prime. That's an allowable step in an algorithm and can be computed efficiently.

RSA challenges allow you to do whatever you want to obtain a factorization, as long as you can implement it and it finishes running and gives you a result.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Makes sense, thank you! $\endgroup$
    – Würthi
    Jul 11, 2022 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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