Yong Hao Ng
Reputation
1,819
Next privilege 2,000 Rep.
Edit questions and answers
 Apr 8 comment Primality testing vs sieve Decomposition of an integer into primes, which is your goal, is not the same as generating primes, which is the objective of the source you quoted. Sieve of Eratosthenes in factorization context may be to generate primes up to $\sqrt n$ so that it facilitates trial division. If so, they do not compete against each other. As for the claim, you can view them as two different problems: 1) what is the best way to find a large range of primes? 2) what is the best way to find just one prime? Presumable this would be primes of a certain size you fix. Mar 10 awarded Nice Question May 20 awarded Yearling Nov 28 awarded Popular Question Sep 24 awarded Autobiographer Jul 2 awarded Curious May 20 awarded Yearling Mar 19 comment Let $E:y^2 = x^3 + 1$ be an elliptic curve. For each prime $5 \leq p \leq 13$, describe the group $E(\mathbb{F}_p)$. I suppose the first question is whether you need to find all the points by bruteforcing $\mathbb F_p\times \mathbb F_p$. If not, you will need to know that you have indeed found all of them. If you do not have access to Hasse's theorem, this seems quite hard to do. If you do bruteforce, at that point you are basically reduced to a group theory problem and it seems natural to just continue with group theoretic computations. You might want to also note that if $(x,y)\in E(\mathbb F_p)$ then $(x, p-y)\in E(\mathbb F_p)$. Mar 19 comment How to show there exists no solution to a discrete logarithm problem on an Elliptic Curve? As for the comment from Álvaro, the idea: you can check if $(1,2)$ and $(4,5)$ are torsion points (Nagell-lutz theorem). If both are torsion, then there are only finitely many points to check. Otherwise, $(1,2)$ is non torsion and you can investigate $[k](1,2)= (x_k,y_k)$. The point is that for sufficiently large $k$, we have $$\max\{x_{k+1},y_{k+1}\}> \max\{x_k,y_k\}$$ so the coordinates is always growing. You can find a $k$ such that in addition $\max\{x_k,y_k\}> \max\{4,5\}=5$. Then for $i\geq k$ we cannot have $[i](1,2)=(4,5)$ by comparing the values. Finally, check for $1\leq i\leq k$. Mar 19 comment How to show there exists no solution to a discrete logarithm problem on an Elliptic Curve? In case it is still not clear: for $E/\mathbb Q$, we have discriminant $\Delta$. For each prime $p\nmid\; \Delta$, you have a reduction mod $p$ by reducing each point $P=(x,y)$ to $$\tilde P=(x,y)\pmod p=(\tilde x,\tilde y)$$ (and $E$ too). So if indeed $[k](1,2)= (4,5)$, you have $[k](\tilde 1,\tilde 2)=(\tilde 4,\tilde 5)$ in $\mathbb F_p$ (same addition formula). So it suffices to generate $\langle \tilde P\rangle$ over $\mathbb F_p$ and check if any element matches $(\tilde 4,\tilde 5)$. You can do this for infinitely many $p$ and chances are one of them works if $[k](1,2)\neq (4,5)$. Mar 17 awarded Critic Mar 12 revised How large do my $2$ primes need to be to “guarantee” a longevity of security for my RSA-encrypted plaintext? Included information for estimating difficulty. Mar 12 revised How large do my $2$ primes need to be to “guarantee” a longevity of security for my RSA-encrypted plaintext? Included information for estimating difficulty. Mar 12 answered How large do my $2$ primes need to be to “guarantee” a longevity of security for my RSA-encrypted plaintext? Mar 12 answered Is it possible to do elliptic curve cryptography over $\mathbb{Q}$ instead of a finite field? Mar 6 comment Four integers that satisfy $a+b+c+d\; =\; -3$ and $a^{3}+b^{3}+c^{3}+d^{3}\; =\; 3$ Regarding the insight part: generally integers in 3 variables (your case) means finding integer points on surfaces (Sometimes you can simplify the equations, which is what you should always try first). This is quite difficult if you want the full solution; you need to know some Arithmetic Geometry. For some examples and references you can look up on "rational points on cubic surfaces" (or integral points). If you just want to find some solutions, you can try solving in $\pmod p$ for many primes and combining solutions in Chinese remainder theorem. This helps to exhaust the small solutions. Mar 6 comment does this equation has an answer? You need to specify what type of values $a,b$ and $x$ are in. For example, can $a,b$ or $x$ be complex-valued? The tag (diophantine-equations) suggest that $a,b$ and $x$ are integers but you may want to state it clearly in your question. Mar 6 comment Why can't the Alpertron solve this Pell-like equation? You may want to also try this Pell equation solver, where the author gave a useful reference regarding the method. Feb 28 comment For which values of n does G have an eulerian trail No problems~ No worries, confidence will come with experience. =D Feb 28 comment For which values of n does G have an eulerian trail So you are done: Eulerian trail if and only if $n=4$.