1
vote
0answers
37 views

Existence of a map $\phi:\mathbb{Z}_{N^2}^* \mapsto \mathbb{F} $

Is there a map between the group of $\mathbb{Z}_{N^2}^*$ where $N$ is a composite number , a product of two equal size secure prime numbers $p$ and $q$ and a finite field $\mathbb{F}$, such that for ...
2
votes
3answers
48 views

A hint on why if $c$ is not a square in $\mathbf{F}_p$, then $c^{(p - 1)/2} \equiv -1 \mod p$

Let $\mathbf{F}_p$ be a finite field and let $c \in (\mathbf{Z}/p)^\times$. If $x^2 = c$ does not have a solution in $\mathbf{F}_p$, then $c^\frac{p - 1}{2} \equiv -1 \mod p$. I will try to prove the ...
2
votes
2answers
66 views

Quadratic Polynomials over $\mathbb F_p$

I'd like to know a reason why (irreducible) quadratic polynomials over $\mathbb F_p$ do not reach all numbers in $\mathbb F_p$. Example: $f(x)=x^2+3x+1$ in $\mathbb F_7$ is irreducible, i.e has no ...
2
votes
3answers
57 views

Let $L = \mathbb F_2[X]/\langle X^4 + X + 1 \rangle$ is a field. Show $L^* = L / \{0\} = \langle X \rangle$ is cyclic.

Let $L = \mathbb F_2[X]/\langle X^4 + X + 1 \rangle$ is a field. Show $L^* = L / \{0\} = \langle X \rangle$ is cyclic. I've proven that $X^4 + X + 1$ is irreducible, so $L$ is a field. I also know ...
1
vote
0answers
41 views

Show that the field $L = \mathbb F_3[X]/\langle X^5 - X + 1\rangle$ consists of $243$ elements and that $[X][f] = [1]$ for some $[f] \in L$.

Show that the field $L = \mathbb F_3[X]/\langle X^5 - X + 1\rangle$ consists of $243$ elements and that $[X][f] = [1]$ for some $[f] \in L$. I know that $L$ is a ring, so it is also a group with ...
7
votes
1answer
155 views

Algorithm to find solution to $ax^2 + by^2 = 1$ in a finite field

Let $\mathbb{F}$ be a finite field, and let $a,b \in \mathbb{F}$ be given, subject to $a\ne 0, b \ne 0$. Consider the equation $$ax^2 + by^2 = 1.$$ It is guaranteed that there exists a solution to ...
4
votes
1answer
72 views

Weighted sum of squares, in a finite field

Let $\mathbb{F}$ be a finite field. Let $a_1,\dots,a_n \in \mathbb{F}$ be given. I want to know whether there exists $x_1,\dots,x_n \in \mathbb{F}$ such that $$a_1 x_1^2 + a_2 x_2^2 + \dots + a_n ...
5
votes
5answers
215 views

Whether the map $x\mapsto x^3$ in a finite field is bijective

Suppose $p\in\mathbb{Z}$ is prime and $\mathbb{F}_p:=\mathbb{Z}/p\mathbb{Z}$ is the finite field of size $p$. Now, consider the map: $$f:\mathbb{F}_p \to \mathbb{F}_p$$ given by $f(x)=x^3$. Then, (1) ...
3
votes
1answer
116 views

Factoring polynomials of the form $1+x+\cdots +x^{p-1}$ in finite field

Suppose $p$ and $q$ primes and $p$ is odd. Then, are there nice and clever ways to factorize polynomials of the form $$f(x)=1+x+\cdots +x^{p-1}$$ in the ring $\mathbb{F}_q[x]$ ? What about the case ...
3
votes
2answers
165 views

“Randomize” output of a Linear Feedback Shift Register for the same taps?

I'm using a (Galois) LFSR to sample a large array, ensuring that each entry is only visited once. I simply skip past the entries that exceed the array length. With the same taps then the array entry ...
-1
votes
1answer
90 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!
15
votes
2answers
461 views

Formula for number of solutions to $x^4+y^4=1$, from Ireland and Rosen #8.18.

There is a sequence of three exercise in Ireland and Rosen's Introduction to Modern Number Theory, Chapter 8, page 106. I can do the first two, but can't finish the third. I can include the proofs to ...
2
votes
1answer
222 views

Existence of an irreducible polynomial over $\mathbb F_p$. [duplicate]

Possible Duplicate: Lack of understanding of the proof of the existence of an irreducible polynomial of any degree $n \geq 2$ in $\mathbb{Z}_p[x]$ Existence of irreducible polynomials over ...
3
votes
4answers
74 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 ?).
3
votes
1answer
71 views

Why are generators of $Z^{*}_p, p=c \cdot 2^k + 1$ so small?

I was implementing NTT for long integer multiplication and thus searched for generators of several $Z^{*}_p$ groups where $p=c\cdot 2^k + 1$. I used the algorithm described in Wikipedia which uses ...
4
votes
1answer
211 views

Primitive root modulo $p$

I am currently trying to find a primitive element of the multiplicative group of field $GF(p)$. Since the numbers are relatively small, I know the factorization of $$\phi(p)=p-1 = {p_1}^{k_1} ...
2
votes
2answers
1k views

finding the LFSR and connection polynomial for binary sequence

I have written a C implementation of the Berlekamp-Massey algorithm to work on finite fields of size any prime. It works on most input, except for the following binary GF(2) sequence: 0110010101101 ...
3
votes
4answers
3k views

Finding inverse of polynomial in a field

I'm having trouble with the procedure to find an inverse of a polynomial in a field. For example, take: In $\frac{\mathbb{Z}_3[x]}{m(x)}$, where $m(x) = x^3 + 2x +1$, find the inverse of $x^2 + ...
0
votes
0answers
47 views

For any prime $p \equiv 1\pmod{5}$ what integers $\{a_0, \dots, a_4\}$ satisfy $(\sum_{i=0}^{4}{a_ig^i})(\sum_{i=0}^{4}{a_ig^{-i}})=p^2$?

For any prime $p \equiv 1 \pmod{5}$ do there exist 5 integers $\{a_0, \dots, a_4\}$, each of absolute value less than $p$, satisfying $\sum_{i=0}^{4}{a_i}=p$, ...