The valuation maps to $\mathbb{F}_p^{n}$, where $n$ is the number of finite places in $S$, should reduce the problem to the case $S=\varnothing$. And then one can reduce modulo small primes of norm congruent to $1$ modulo $p$, though the discrete logarithm there could be harder to work with.

I assumed that was found with the method in the accepted answer by Wojowu. Or did you use something else?

I don't see how your $f$ is well-defined. It would be if you considered the category of non-singular Weierstrass equations. Using Riemann-Roch involves choosing $x$ and $y$, which amounts to choosing your equation. (And it should be $(\lambda^2x+r, \lambda^3 y + s\lambda^2x + t$).

@LaurentMoret-Bailly If $j(\mathcal{A})$ is in $\mathbb{Q}$ there is an elliptic curve $E/\mathbb{Q}$ such that $E \times \mathbb{Q}_p$ is a twist of $\mathcal{A}$. If $j\not \in \{0,1728\}$, there is a $D\in\mathbb{Q}_p^{\times}$ such that $\mathcal{A}$ is the quadratic twist $E^D$. Now approximate $D$ by a rational $D'$ such that $\mathbb{Q}(\sqrt{D}) = \mathbb{Q}(\sqrt{D'})$. Then $A=E^{D'}$ will do. Similar with sextic, cubic and quartic twists.

For an elliptic it is simply the question if $j(\mathcal{A})\in \mathbb{Q}$.

With a appropriate definition of gcd, this seems to have solution in $\mathbb{Z}_p$ for all prime $p$ and even $a=b=c=1/2$ is such a solution in $\mathbb{Z}[\tfrac{1}{2}]$. This may indicate why it is not an easy question.

You want to read up on the quadratic sieve.

But $\varphi(2^n-1)/n<2^n-1$, so this is complete. It is a prime example of why formulating things as in (1) is harder to work with than congruences and inequalities.

Essentially, yes. First the target group must be changed to $\mathbb{Z}/n\mathbb{Z}$. Then I would not use the index "div" for your subgroup. Traditionally, this is used for the group of infinitely divisible elements. Note that your "div" group is actually $n\, Ш [n^2]$. That is how this is presented usually and that is what I should have written in these lecture notes to be correct. (If an element in $Ш[n]$ is $n\xi$ for some $\xi\in Ш$ then $\xi \in Ш [n^2]$.)

hsm.stackexchange.com sounds more appropriate for this question.

If $\phi: E \to E'$ is an isogeny defined over $F$ between two curves defined over $K$, then $\phi$ is the composition of an isogeny of that degree defined over $K$ and an isomorphism from $E/E[\phi]$ to $E'$ defined over $F$.

The algorithms look for all isogenies $\phi$ leaving $E$ defined over a fixed number field $K$, which is equivalent to finding their kernels $C = E[\phi]$ as subgroup of $E$ defined over $K$. The codomain $E/C$ is defined over $K$.

(3) No, because of quadratic twists this isn't true even for isomorphic curves (degree 1 isogenies).

My answer to this question contains links to algorithms even over number fields. That should help for (1).

$E[4](\mathbb{F}_5) = \{O\}$ but $E[4]$ as a group scheme has $16$ points over $\mathbb{F}_{5^6}$. This is a basic question about isogenies, please read chapter III.4 in Silverman's "The arithmetic of elliptic curves".