I have been wondering this question because given a number $n$ with prime factors of the form $4k+3$ when we square $n$ and find a sum of two squares which should reveal these types of factors (as when we find non-trivial answers they have a gcd above 1 etc.). However, when a number solely has prime factors of form $4k+1$ this seems to be a more difficult reduction that needs multiple representations and these types of approaches seem to be bound to condition very often. This equivalence seems interesting because it connects computational problems in summation with problems in multiplication. Does anyone know of the/a reduction?

  • $\begingroup$ I don't understand what you're asking, but I note that $n^2$ can be decomposed as a sum of two squares as $0^2+n^2$, which seems to argue against "which should reveal these types of factors". $\endgroup$ Nov 22 '18 at 14:26
  • $\begingroup$ What do you mean by "asymptoticaly equivalent"? Are you asking if they're equivalent under, e.g., polynomial-time reductions? $\endgroup$ Nov 22 '18 at 19:30
  • $\begingroup$ @PeterTaylor yes, I meant nonzero squares. You are right in noting that your case would not reveal any information. $\endgroup$
    – Askeroni
    Nov 23 '18 at 15:39
  • $\begingroup$ @DavidRicherby yes that is what I meant. $\endgroup$
    – Askeroni
    Nov 23 '18 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.