All Questions
Tagged with computational-number-theory polynomials
21 questions
34
votes
1
answer
1k
views
Does any cubic polynomial become reducible through composition with some quadratic?
What I mean to ask is this:
given an irreducible cubic polynomial $P(X)\in \mathbb{Z}[X]$ is there always a quadratic $Q(X)\in \mathbb{Z}[X]$ such that $P(Q)$ is reducible (as a polynomial, and then ...
- 5,103
15
votes
4
answers
2k
views
Computing minimal polynomials using LLL
I would like to use the Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL algorithm) to compute the minimal polynomial of a (real) algebraic number $\alpha$ from a decimal approximation $a$...
- 3,165
11
votes
1
answer
646
views
Non-trivial solutions for $-(c^2-d^2)(a^2-b^2)=2(ad-bc)(bd+ac)$?
Consider the quartic system in four variables $a,b,c,d\in\mathbb R$:
$$-(c^2-d^2)(a^2-b^2)=2(ad-bc)(bd+ac).$$
Does this system admit rational solution with $$abcd(c^2-d^2)(a^2-b^2)(a^2-c^2)(b^2-d^2)\...
- 13.9k
11
votes
1
answer
565
views
When adding a constant makes a multivariate polynomial reducible?
Given a multivariate polynomial $f(x_1,\dots,x_n)$ with integer coefficients, how to find an integer $m$ (if it exists) such that $f(x_1,\dots,x_n) + m$ factors into polynomials of smaller degrees?
...
- 34.3k
8
votes
1
answer
335
views
Existence of Randomized polynomial time algorithm and some arithmetic analog of $ACC^0$ circuits for Factoring of primitive polynomials before LLL?
Before LLL came along in $1982$ there was no deterministic polynomial (in degree and number of bits in coefficients) way to factor square free primitive polynomials in $\Bbb Z[x]$.
However was there ...
user94040
5
votes
0
answers
153
views
On factorization algorithms for $\mathcal{O}[x]$
We know that $\mathsf{LLL}$ algorithm provides factorization procedure that runs in poly time for polynomials in $\Bbb Z[x]$ that are primitive.
What other rings $\mathcal{O}$ can we use instead of $\...
user76479
3
votes
1
answer
1k
views
Coppersmith bivariate polynomial roots implementation
Given $f(x,y)\in\mathbb Z[x,y]$ Coppersmith in https://link.springer.com/chapter/10.1007%2F3-540-68339-9_16 provides a provable method to find integer roots in polynomial time and this method was also ...
- 13.9k
3
votes
0
answers
135
views
Recover cyclotomic integer with bounded coefficients from its known associate
Recall that two cyclotomic integers are called associated if their ratio is a unit in the corresponding ring of cyclotomic integers.
We will view cyclotomic integers as polynomials (of degree $<\...
- 34.3k
3
votes
0
answers
98
views
Deterministic procedure to find irreducible polynomials
In $\Bbb F_q[x_1,\dots,x_n]$ given $d_1,\dots,d_n\in\Bbb N$ is there a deterministic $O(poly(nd\log q))$ algorithm to find an irreducible polynomial with $d=\max_{i\in\{1,\dots,n\}}d_i$ and $d_i=deg(...
- 13.9k
2
votes
1
answer
171
views
On roots of irreducible quadratics modulo composites
Assume factorization of $N$ is unknown. What is the best complexity we know to find roots of the irreducible equation $$ax^2+bx+c\equiv0\bmod N?$$
Is this problem equivalent to any hardness results?
- 13.9k
1
vote
1
answer
1k
views
Computation for composition of polynomials
Let $R$ be a ring, $f(X)$ be a polynomial with coefficients in $R$ of degree $n$. It's known that for any $\alpha \in R$, one can evaluate $f$ at $\alpha$, i.e compute $f( \alpha) $ in $O(n)$ ...
- 1,109
1
vote
1
answer
218
views
On a quadratic diophantine equation
Given a quadratic diophantine equation in $\mathbb Z[x,y,z]$ of form
$$ax^2+by^2+cx+dy+ez+f=0$$ are there standard methods to solve for it when $$\|(x^2,y^2,z)\|_\infty\leq e^{1/2}$$
$$\|(a,b,c,d,e,f)...
- 1,826
1
vote
2
answers
337
views
Transformation of a bivariate polynomial into a homogeneous one
For a given a bivariate polynomial $P(x,y)$ with rational coefficients:
Q1. How compute such (invertible) substitutions of its variables that would transform the polynomial into a homogeneous one? In ...
- 34.3k
1
vote
1
answer
189
views
Explicit bivariate quadratic polynomials where Coppersmith is better than standard solver?
http://www.numbertheory.org/pdfs/general_quadratic_solution.pdf gives a general method to solve quadratic bivariate diophantine equation while Coppersmith introduced a method to solve bivariate ...
- 13.9k
1
vote
0
answers
123
views
Testing polynomials irreducible over the integers
Let $f\in\operatorname{int}(\mathbb Z)$, the ring of integer-valued rational polynomials. Define $\operatorname{P}^+(f)$ as the number of primes $>0$ that $f$ assumes at distinct integral arguments....
- 862
1
vote
0
answers
415
views
Rings of algebraic integers as quotients of polynomial rings
The ring of integers $\mathcal{O}_K$ of a number field $K$ is always isomorphic to some ring of the form $\mathbb{Z}[x_1, ..., x_r]/\mathfrak{p}$, where $\mathfrak{p} \subset \mathbb{Z}[x_1, ..., x_r]$...
- 704
0
votes
2
answers
754
views
On reducible polynomials with positive coefficients, $1$ as constant coefficient and certain bounds on coefficients
Given $a \in \mathbb{Z}$ with $a > 1$. Let $g(x) \in \mathbb{Z}[x]$ be a polynomial with $g(a)=\pm 1$. Let $h(x) \in \mathbb{Z}[x]$ be a polynomial with $h(a)= p$, a prime. Let $g(x)$ and $h(x)$ ...
0
votes
1
answer
63
views
Changing base field for sum of polynomials
Let $L/\mathbb{Q}$ be a finite extension and $f_{1},\dotsc,f_{n}\in L[x_{1},\dotsc,x_{k}]$ be degree $d$ homogeneous polynomials. Is there a way to find homogenous degree $d’$ polynomials $g_{1},\...
- 3
0
votes
1
answer
250
views
If the coefficient of the polynomial positive
I want to know what is following sum coefficient looks like. We sum over all integers $p$, $q$ also we put the condition that $q$ is even. Also, it should depend on the parity of $k$
$$\bar{S}(k)=\...
- 685
0
votes
1
answer
159
views
Parity and number of squares taken by polynomials in a range?
I have a polynomial $f(x)=a^2x^2+bx+c\in\mathbb Z[x]$ with $f(x)$ not a constant times a square and $abc\neq0$ and I want to know how many $x$ between $-a$ and $a$ the polynomial is a perfect square. ...
- 13.9k
0
votes
1
answer
604
views
Method to solve modular quadratic polynomial [duplicate]
If $q$ is a prime what is the best method to compute roots of a quadratic polynomial $f(x)\equiv0\bmod q^2$ which is of form $x^2+bx+c\equiv0\bmod q^2$ where $b^2-4c\equiv0\bmod q$ and $gcd(b,q)=1$ ...
- 13.9k