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$
3
  • $\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

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, privacy policy and cookie policy

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