All Questions
13 questions
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
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
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
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
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
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
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
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
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
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
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
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
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