Reputation
1,819
Next privilege 2,000 Rep.
Edit questions and answers
Badges
5 15
Impact
~18k people reached

  • 0 posts edited
  • 0 helpful flags
  • 234 votes cast
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$.