-1
$\begingroup$

I was wondering if there is an algorithm to derive $p$ and $q$ or is it simply trial and error?

Consider the following RSA crypto-system with public key $(437,13)$. Since the numbers are so small, it is possible to break the crypto-system and determine the private key. What is the value of the two primes $p,\,q$ with $n=p\times q$ used in the key generation.

Hint: You may ignore the value $13$ in your computations.

The answer is $23$ and $19$ but I was wondering if there is an algorithm for it?

Thanks!

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I rolled back the edit to the question. It's crucial to the answer that the numbers are small, and questions shouldn't be edited in a way that makes answers invalid. $\endgroup$
    – David Richerby
    Commented Dec 8, 2018 at 21:12

2 Answers 2

Reset to default
2
$\begingroup$

Of course there’s an algorithm for it. Trial division is an algorithm, a very straightforward one.

Improve this answer
$\endgroup$
0
$\begingroup$

Divide the odd target number by 3, 5, 7, and 11 to see if they are factors.

Then beginning with the number 11, increment with the values of 2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10 as continuing and repeating .

Finally, divide the odd target number by each incremented number to see if one of them is a factor. Continue dividing by the incremented numbers up to the square root of the target number if no factors are previously found.

One note, I found the increments that produce a sequence of odd numbers with multiples of 3, 5, and 7 removed just by working logically with a sequence of odd numbers. However, the increments can also be determined using Wheel Factorization formulas. But I think it is faster to increment with 48 hard-coded array values than to compute.

Improve this answer
$\endgroup$
7
  • $\begingroup$ You should probably explain that your sequence consists of the gaps between the small primes. You might have well started it with an extra 2,2,4. $\endgroup$
    – Yuval Filmus
    Commented Dec 9, 2018 at 1:14
  • $\begingroup$ The increments produce a sequence of odd numbers with multiples of 3, 5, and 7 removed. The sequence does contain all the forward prime numbers but also contains composite numbers. Use of the number sequence in factoring reduces the number of required divisions and is a major increase in performance $\endgroup$
    – S Spring
    Commented Dec 9, 2018 at 1:54
  • $\begingroup$ That would be a good thing to explain in your answer, though I think you can assume that $n$ is the product of two primes. $\endgroup$
    – Yuval Filmus
    Commented Dec 9, 2018 at 1:56
  • $\begingroup$ The sequence of odd numbers with multiples of 3, 5, and 7 removed, is very little computational overhead in exchange for the increase in performance. Developing all prime numbers for the factoring operation would be much more computational overhead. $\endgroup$
    – S Spring
    Commented Dec 9, 2018 at 2:07
  • $\begingroup$ You can explain all of this in your answer. $\endgroup$
    – Yuval Filmus
    Commented Dec 9, 2018 at 2:08

Your Answer

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

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