Given 1000 numbers of form s*p, number are of 3500 bit long. How to factor these numbers? s and p are not necessarily prime numbers. p is constant for all numbers and s is randomly chosen for all 1000 numbers. Again How to solve the same problem when mod of these numbers is provided instead of direct multiplication.

  • 3
    Note: "a and x" refers to two undefined quantities. Hint: it appears that the simplest strategy in this attack might work. – fgrieu Dec 6 at 17:31
  • Is there other algorithms that might work better for this case. – Ram_Giri Dec 7 at 4:24
  • The problem at hand can be solved by application of an algorithm codified in writing for 23 centuries. The whole thing requires like 8 lines of Python once the inputs are gathered, and I guess a mere second of runtime. Yes there are slightly "better" variants for some definitions of that, but it is a good start. – fgrieu Dec 7 at 7:06
  • Let $a_1 = s_1 p$ and $a_2 = s_2 p$, take $\gcd(a_1,a_2)$. try with some other $a_i$ couples to deduce the $p$. – kelalaka Dec 7 at 9:00
  • 2
    I'm voting to close this question as off-topic because t does not seem to have anything to do with cryptography. – Maeher Dec 8 at 11:55

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.