0
votes
0answers
22 views

What is rational point on elliptic curve over Galois field

It is clear what is a rational point on elliptic curve, when the curve is defined over real numbers. But if it is defined over Galois field, what is a rational point? If necessary, supply an example, ...
0
votes
1answer
82 views

How to find primitive point on an elliptic curve?

Reading about Elliptic curve cryptography, i came across primitive point's or generator point's but found nothing on how to generate such points any help would be appriciated.
4
votes
1answer
113 views

Lenstra's Elliptic Curve Algorithm

I am currently trying to understand Lenstra's Elliptic Curve Algorithm for factoring integers. As a source I use "Rational Points on Elliptic Curves" by Joseph H. Silverman and John Tate. They ...
1
vote
1answer
35 views

Find coordinate $y$ of an elliptic curve point

If I have an elliptic curve over a finite filed $F_p$ ($p$ is prime) defined as $$ y^2 \equiv x^3 + ax + b\pmod p,$$ such that $4a^2 + 27b^2 \neq 0$ and suppose I have only given the coordinate $x$, ...
0
votes
0answers
15 views

What is an embedding degree of elliptic curve?

I am dealing with MOV algorithm to transform ECDLP to DLP in $GF(p^k)$, but at the first step I have to determine embedding degree k. I have read the definitions of embedding degree, but still I am ...
0
votes
1answer
68 views

Public Key Scheme decryption. [closed]

You have been sent a message based on the following Public Key Scheme. 1) Bob chooses two large primes $\ p,q $ with $ p \equiv q \equiv 2 \pmod 3$ and computes $ n=pq. $ 2) Bob chooses integers $ e,d ...
1
vote
1answer
25 views

Computing fractions Weierstrass curves and DLP problem

I am preparing for a crypto exam by making an old practise exam. I got stuck on the following assignment. I got this weierstrass curve The curve $y^2 = x^3$ is not an elliptic curve over $F_{71}$ but ...
1
vote
1answer
40 views

Finding all Points on a Edwards curve

I need to find all affine points on the Edwards curve: $x^2 + y^2 = 1 - 5x^2y^2$ over $F_{13}$ I tackle this by transforming the equation to: $y^2 = \frac{1-x^2}{1+5x^2}$ I then go from x = 0 to ...
1
vote
1answer
136 views

Finding points on an elliptic curve

I have an elliptic curve $$x^3+17x+5 \mod 59$$ $P = (4,14)$ is given and I need to find point $8P$. to calculate $8P$, I first calculated $2P$ by using the equation sigma = 3x^2+a/2y = ...
4
votes
1answer
32 views

Part of verifying that the Weil pairing $e_m$ is well-defined.

As part of a homework problem, I need to show that the value of $e_m(P,Q)$ is independent of the choice of a point $S \in E[m] \setminus \{\mathcal{O},P,-Q,P-Q\}$, where $E[m]$ is the collection of ...
4
votes
2answers
68 views

Is it possible to do elliptic curve cryptography over $\mathbb{Q}$ instead of a finite field?

Whenever I read about elliptic curve cryptography (ECC), the writer always works over a finite field. But as I understand it there is no group-theoretic reason not to use $\mathbb{Q}$ as the ...
1
vote
1answer
80 views

E: $y^2+y=x^3$ an elliptic curve over $F_{2}$. How to prove the number of $E(F_{2^n})$ = $2^n+1$ if n is odd, …

Let E be the elliptic curve $y^2 + y = x^3$ over $F_2$. Prove $ $#E($F_{2^n})$$ = \left\{ \begin{array}{ll} 2^n+1 & \quad n=odd \\ 2^n+1-2(-2)^{n/2} & \quad ...
2
votes
1answer
36 views

Uniqueness of points in Elliptic Curve addition

When working on a curve E, is the point yielded by P + Q (some P and Q on E) completely unique? What I mean is there are no other points on E sharing the same x or y value. Thanks!
1
vote
2answers
83 views

Elliptic Curve Crypto

I had just read a primer about ECC, I see how it can be complicated. Something I haven't been able to determine is what information does the client machine get to help decrypt the data? The whole ...
3
votes
1answer
79 views

Probability of an ECM factor

Suppose I have a composite number $N$ divisible by some prime $p\le x.$ What is the probability that one iteration of ECM finds $p$, given parameters B1 and B2? Usually people look for factors in ...
0
votes
0answers
59 views

Addition a point on an elliptic curve with an integer value

Suppose $Q$ is a point in an elliptic curve such that $Q=dP$ and $d$ is an integer value, and $P$ is base point of that elliptic curve. Note $Q = dP$ means that $P+\cdots+P$ for $d$ times** and since ...
1
vote
1answer
85 views

Diffie-Hellman key exchange for three user.

Assume that there are three users that have their own secret key $d_i$ and corresponding public key $Q_i = d_i G$ such that $Q_i$ is a point in an elliptic curve. Now I'm looking for a solution to ...
3
votes
1answer
326 views

Adding points of an elliptic curve over a finite field

I'm a bit confused with how fractions are handled with adding points of elliptic curves over finite fields. Below is an example from the text which I am trying to understand: The part that ...
0
votes
0answers
82 views

Is Hash(bG) equal to b(Hash(G))?

Assume b is an integer, G is a basepoint in an elliptic curve, and Hash is a one-way hash function. Is Hash(bG) equal to b(Hash(G)) ? or not? Note: A hash function is any algorithm or subroutine ...
2
votes
2answers
243 views

How do you determine if an elliptic curve over a finite field is cyclic?

I know the group order and the points of the elliptic curve $y^2 = x^3 + Ax + B$, but I am confused on how to determine if they from a cyclic group The curve $y^2 = x^3 + 2x +2$ in $\Bbb F_{11}$ ...
2
votes
2answers
249 views

order of elliptic curve $y^2 = x^3 - x$ defined over $F_p$, where $p \equiv 3 \mod{4}$

It is said that the elliptic curve $y^2 = x^3 - x$ defined over a prime field $\mathbb{F}_p$, where $p \equiv 3 \mod{4}$ has an order $p + 1$. When I tried to get the elements of $E = \{(x,y) \in ...
0
votes
1answer
63 views

Find lift($E_{p^2}$) of an elliptic curve $E_p$ defined in field $F_p$ where $p$ is a prime

How to find $E_{p^2}$ of an elliptic curve $E_p$ defined over finite field $F_p$ where $p$ is a prime number?
3
votes
2answers
299 views

Elliptic curves over a finite field $\mathbb{F}_p$ where $p$ is prime.

Let $Y^2=f(X)$ be an Elliptic curve over a finite field $\mathbb{F}_p$ where $f(X)=X^3+aX+b$ In an undergraduate coursebook on an Applied Algebra course it states that "It is plausible to suggest ...
4
votes
1answer
583 views

Intersection of a line with an Elliptic Curve

I am trying to show that if a line given by $y = mx + b$ intersects an Elliptic Curve given by $E(\mathbb{K}): y^2 = x^3 + Ax + B$ in three points then the line is not tangent to the curve. Given ...
3
votes
1answer
165 views

Groups where discrete logarithm is hard

What are examples of groups, where DLP (discrete logarithm problem) is hard? Two obvious ones are: integers modulo $p$ ($p$ being prime) and elliptic curves over finite fields. What are the others?
1
vote
1answer
162 views

How to nicely extend finite field?

I'm working on an implementation of Miller's algorithm that computes the Weil pairing (elliptic curves, cryptography). In order to do that, I have to implement finite fields. So far I have managed to ...
26
votes
3answers
977 views

What is an elliptic curve, and how are they used in cryptography?

I hear a lot about Elliptic Curve Cryptography these days, but I'm still not quite sure what they are or how they relate to crypto...