Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [prime-field]

The tag has no usage guidance.

-1
votes
1answer
46 views

Elliptic curve over prime field with high order roots of unity

Suppose I have an elliptic curve defined over a prime field $\operatorname{GF}(p)$ where $p$ is a large prime (e.g. 256-bit). Suppose also that $p = kn +1$, where $n$ is a relatively large power of $2$...
3
votes
1answer
72 views

Why is the strength of an Elliptic Curve Cryptography (ECC) half the size of the prime field size?

I've looked around and couldn't find a direct answer. As a general rule, I've read from various sources (here here, and here) that the strength of an elliptical curve key is half of the size of the ...
5
votes
2answers
101 views

Why does libSTARK use binary fields as opposed to prime fields for zk-SNARKs?

zk-STARKs make use of FRI for low degree testing of polynomials. The zk-STARKs paper states on page 11: we stress that ZK-STARK could also operate over prime fields but we have not realized this ...
3
votes
1answer
58 views

Randomizing Prime Field Elements

I need my code to generate random elements from $GF(p)$ ($F_p$ or $Z_p$, if you will). The Crypto API I have available provides one with random bit strings. To tailor that to my needs, I can think of ...
2
votes
1answer
172 views

Questions about the Curve25519-donna implementation

I'm trying to understand the implementation of the following function: Please note questions in comments. ...
2
votes
2answers
55 views

Secret sharing over $Z_n*$

Shamir's secret sharing protocol generates a polynomial over a prime field $F_p$. Is it possible to generates it over $Z_n^*$ as well? The reason is that I want to combine a secret shared value in ...
18
votes
5answers
2k views

Are there any (asymmetric) cryptographic primitives not relying on arithmetic over prime fields and/or finite fields?

Trying to figure out if any (asymmetric) cryptographic primitives exists, which do not rely on arithmetic over a prime field and/or arithmetic over a finite field, some people might get lost in ...
0
votes
1answer
197 views

Does this computation lead to solving DL?

Imagine we have $g^x$, $a$ and $g^b \in \mathbb{Z}_p$. Is it realistic to compute $g^{(a+x)b}$ without knowing $x$ and $b$? Or is it equivalent to solving the Discrete Logarithm problem?
-1
votes
1answer
97 views

Order of the curve and generator

Does the order of the curve and the order of generator should be coprime for an elliptic curve defined over a prime field?
3
votes
2answers
444 views

Is the prime P is fixed for an elliptic curve defined over a particular prime field F_p?

I have seen the NIST, SEC and Brainpool standards. They have used same prime for a particular bit curve (128,192,256,521). Is the prime value fixed for a particular security (field size)?
1
vote
2answers
663 views

Comparing elliptic curves over prime fields against EC over binary fields

In which scenarios we go for prime fields or binary fields? Please indicate why we would choose one over the other.
2
votes
2answers
260 views

How to determine proportion of quadratic residues in elliptic curve group?

I'm using a 'try and increment' method to hash to an Elliptic Curve point, explained below. With security parameter $k$, EC equation $y^2 = x^3 + ax + b \mbox{ mod } q$, we have: $ u = sha256(\mbox{...
1
vote
1answer
95 views

Subscript R notation for the finite fields

I'm trying to understand the notation used in the literature for Pairing-based cryptography. I know (and I hope I've understood it well) from Wikipedia that $\mathbb{Z}_p$ is the finite field of ...
0
votes
2answers
210 views

Is the complexity of Pollard rho for discrete logartihm really the modulus?

so I'm reading everywhere that the Pollard Rho for Dlog's complexity of $g^a \pmod{n}$ is $\mathcal O(\sqrt{n})$. Shouldn't it be $\mathcal{O}(\sqrt{q})$ with $q$ the order of $g$?