Is writing a number as two squares and writing the factors of a number equally hard?

Let $L_1$ and $L_2$ be the following:

$L_1=\{r:\exists x,y \in \mathbb{Z} \text{ such that } x^2+y^2=r\}$

$L_2=\{(N,M): M<N, \exists 1<d\leq M \text{ such that d|N} \}$

Claim $L_1 \leq_P L_2$

Sketch Proof

If I want to know whether $r\in L_1$.

The number of integer solutions to $x^2+y^2=r$ is given by

$g(r)=\sum_{d|r}{\chi{(d)}}$ where $\chi (x)=sin(\frac{\pi x}{2})=\cases{ 1\text{ when }x\cong 1 \text{ mod }4 \\ -1 \text{ when }x\cong 3 \text{ mod }4 \\ 0 \text{ when } 2|x }$

Then $L_1=\{r: g(r)\neq 0\}$. So then to answer is "$r\in L_1$?" is at most as hard to answer as "what are the divisors of $r$?"

$\square$

What I would like to know is if this is true the other way around. Is it true that if I had a machine which could tell me in constant time whether $r\in L_1$ could I create a machine which could answer "is $(M,N)\in L_2$?" in polynomial time?

Motivations

This question came out of a discussion on this question.

Apologies
I am really just a math.se member who has gotten lost and wandered on to cs.se. Let me know if my question is clear and up to the standards of this site. I am happy to make corrections.

Here's the situation as far as I can tell:

The most efficient way known to test membership in $L_1$ is to factor $r$. No more efficient algorithm seems to be known.

However, there is no obvious reduction to prove $L_2 \le_P L_1$. In other words, if we had a machine to decide $L_1$, there's no easy way to use that to factorize. If we want to factor a number $N$, we can check whether $N \in L_1$, but this only gives us one bit of information about the factors of $N$. Testing multiples of $N$ (i.e., whether $cN \in L_1$ for some integer $c$) doesn't give us any additional information, as knowing whether $N \in L_1$ suffices to predict whether $cN \in L_1$ for all $c>0$. Testing other numbers doesn't seem to help in any obvious way, either. (Testing whether $N' \in L_1$ for some other number $N'$ doesn't seem to give any useful information, if $\gcd(N,N') =1$; and if we had a way to find another number $N'$ such that $\gcd(N,N')\ne 1$, we'd already know how to factor, but of course we don't know how to do that -- so any number we know how to generate is unlikely to give us any useful information on the factors of $N$.) This is not a proof; it is just handwavy intuition.

So it seems plausible that $L_1$ might be easier than $L_2$, and it also seems plausible that they might be of the same difficulty. I'm not aware of any further results on this subject.

StackExchange Computer Science Q#93203, answer score: 5