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|...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 1,469

Only top scored, non community-wiki answers of a minimum length are eligible