# Tagged Questions

40 views

### Operations in finite field $F_p$

If I have a finite field $F_p$, where $p$ is prime how can I define operations like $+, -, \times, /$? Can I just make: $$add: (a + b) \mod p$$ $$sub: (a-b) \mod p$$ $$mul: (a\times b) \mod p$$ ...
45 views

### The existence of primitive algebraic units modulo 3

Consider the problem of computing $$\sqrt{2} \mod 3$$ Whereas we seek a number $n$ such that $n^2 \equiv 2 \mod 3$ and furthermore it is known that both $n$ and $2n$ will satisfy this property, ...
66 views

### Solving the discrete logarithm using index calculus, finite fields and factor bases.

(a) Let $p$ be the prime 1073741827, with $\Bbb{F}_p$ the corresponding finite field. A primitive root in $\Bbb{F}_p$ is equal to $g=2$. Use a factor base of primes up to 13 to find the discrete ...
39 views

### How to give irreducible factorization in $\mathbb{Z}_5$?

I have this polynomial: $$f=x^5+2x^3+4x^2+x+4$$ How can i find the irreducible factorization(in $\mathbb{Z}_5$)?I can find the roots easily but thats not enough.
49 views

### Calculations in the field $\mathbb{F}_{13}$

The text i am reading claims that $\frac{246}{14}=1$ in the field $\mathbb{F}_{13}$. However, i cannot figure out why this is correct. Since $13 \cdot 18 = 234 \Rightarrow 246 = 12$ and $14 = 1$. How ...
63 views

### Is $\mathbb{Z}_p$ a Finite Field?

Denote the integers modulo $p$, $\mathbb{Z}$ mod $P$, as $\mathbb{Z}_P$. Denote the set of integers equivalent to $n$ mod $P$ - the equivalence class of $n$ as $\overline{n}$. We know that for any ...
459 views

### How can I solve system of linear equations over finite fields in WolframAlpha?

Is it possible to solve system of linear equations over finite fields using Wolfram Alpha? If yes, how can I do that? Let us take a system $x+y+z=0$, $2x+y+2z=0$, $x+3y+z=0$. If I want to solve this ...
41 views

### Manually computing a galois field element [duplicate]

$F = GF(2^6)$ modulo the primitive polynomial $h(x) = 1 + x^2 + x^3 + x^5 + x^6$ and $\alpha$ is the class of $x$: $GF(2^6) = \{0,1,\alpha, \alpha^2...\alpha^{62}\}$ How do I manually compute ...
90 views

### Number of points on $Y^2 = X^3 + A$ over $\mathbb{F}_p$

Let $p\equiv 2\pmod{3}$ be prime and let $A\in\mathbb{F}^{∗}_p$ . Show that the number of points (including the point at infinity) on the curve $Y^2 = X^ 3 + A$ over $\mathbb{F}_ p$ is exactly $p + 1$ ...
114 views

### Diophantine equation $x^2-dy^2=k$ in $\mathbb{Z}_n$

Does anyone know when $x^2-dy^2=k$ is resoluble in $\mathbb{Z}_n$ with $(n,k)=1$ and $(n,d)=1$ ? I'm interested in the case $n=p^t$
114 views

### Finding number of solutions to an equation in $\mathbb F_p$

$p=3 \pmod 4$ is a prime. Let $b\in \mathbb F_p^*$. Show that the equation $v^2=u^4-4b$ has $p-1$ solutions $(u,v)$ with $u, v \in \mathbb F_p$. If we write the given equation as $v+u^2=x$ and ...
49 views

### Representing an element mod $n$ as a product of two primes

Given a positive integer $n$ and $x \in (\mathbb{Z}/n\mathbb{Z})^*$ what is the most efficient way to find primes $q_1,q_2$ st $$q_1q_2 \equiv x \bmod n$$ when $n$ is large? One option is just to ...
91 views

### Prove that in $\mathbb{Z}_p$, $[a]^{-1} = [a]$ if and only if $[a]=[1]$ or $[a]=[p-1]$

Let $p$ be a prime and a an integer. Prove that in $\mathbb{Z}_p$, $[a]^{-1} = [a]$ if and only if $[a]=[1]$ or $[a]=[p-1]$. I greatly appreciate your help on this question!
114 views

### Is the modular multiplicative inverse of $a$ equal to that of $-a$?

In javascript, I am implementing Lagrange interpolation over a finite field $GF_p$ for some prime $p$. I only need to compute the value of the $y$-intercept of the Lagrange interpolation polynomial ...
121 views

### Prove that there are $p+1$ points on the elliptic curve $y^2 = x^3 + 1$ over $\mathbb{F}_p$, where $p > 3$ is a prime such that $p \equiv 2 \pmod 3$.

Let $p > 3$ be a prime such that $p \equiv 2 \pmod 3$. Define the elliptic curve $E$ over $\mathbb{F}_p$ by $y^2 = x^3 + 1$. Prove that $E(\mathbb{F}_p)$ consists of $p+1$ points. Using Fermat's ...
69 views

### Find the inverse of $\alpha^{38}$ in $\mathbb F = \mathbb Z_2[x]/\left<x^4+x+1\right>$

Let $\alpha$ be a root of $x^4+x+1$ and we are given some powers of $\alpha$ as linear combinations of $1,\alpha,\alpha^2$ and $\alpha^3$ $\alpha^4=\alpha+1$ $\alpha^5=\alpha^2+\alpha$ ... (the rest ...
75 views

### $Y^3$ congruent to $1 \pmod {p}$

How to get the condition on $p$ for which $y^3$ congruent to $1$ modulo $p$ has $3$ solutions ( $1$ solution $x= 1$ is always possible, right ?).
### $\mathbb{Z}/n\mathbb{Z}[T]$ and zero divisors
I read the following in wiki, but I can't understand what is meant by "divisor" there. Notice that $(\mathbb{Z}/2\mathbb{Z})[T]/(T^{2}+1)$ is not a field since it admits a zero divisor ...
In standard computer arithmetic, there are two sets of numbers. N-bit unsigned numbers. The elements are natural numbers in $(0, 2^N]$. Arithmetic operations is defined as for the natural numbers ...