3
votes
Accepted
A property of the convergents of the continued fraction expansion of a rational number
As you noted, the claim also holds for irrational numbers. I will give a proof that works for all real numbers, i.e. I will prove:
Let $x\in\mathbb R$ and $c,d\in\mathbb Z$ coprime such that $$\left|...
- 1,195
2
votes
Accepted
Time complexity to compute f(k).
By Horner's method, at most $O(n)$ multiplications need to be performed. Based on the recent breakthrough, each multiplication takes time at most $O(\log q\log\log q)$ (under some plausible number ...
- 8,716
2
votes
Accepted
Point on elliptic curve that is torsion over algebraic closure
The $x$-coordinate $x_0$ of any nontrivial $7$-torsion point over $\overline{\mathbb{F}}_7$ is a zero of the $7$th division polynomial $\psi_7$ which is in your case equal to $5\cdot(x^3-2)^7$. Thus ...
- 3,271
1
vote
Finding 1 solution of $(x^3 + ax + b) \bmod p = 0$
Mathematica does not find any solutions to the equation $x^3-3x+b=0$ in the field $\Bbb{F}_p$. This is just as well because the order of this curve $n$, see page 16 of the linked document, is an odd ...
- 124k
1
vote
Accepted
Justifying a randomization technique for efficiently checking equalities in a prime-order group
Suppose $G$ is a group of order $p$, where $p$ is prime, and suppose we are given $g_0,g_1,h_0,h_1\in G$. If we want to check whether $g_0=h_0$ and $g_1=h_1$, we pick $x\in\mathbb{F}_p^*$ uniformly at ...
- 6,626
1
vote
Is Elliptic Curve Cryptography (ECC) used for key exchanges or encryption?
The problem with ECC encryption is the encoding of the messages into points. Look at the Koblits encoding or its variants and you will see that there is a probability that a point will fail to be ...
- 1,469
Only top scored, non community-wiki answers of a minimum length are eligible