# Questions tagged [computational-number-theory]

Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.

422 questions
Filter by
Sorted by
Tagged with
164 views

### Efficiently count the number of primitive roots in all moduli up to $n$

Let's define $f(n)$ as the number of primitive roots modulo $n$. That is, $f(n) = \begin{cases}\varphi(\varphi(n))&n=1,2,4,p^k,2p^k\\0&\text{otherwise}\end{cases}$. We want to efficiently ...
135 views

### Newton type method for finite fields?

I have a polynomial $p(x)$ in $\mathbb{Z}/q\mathbb{Z}$ that is easy to compute for any $x$ but has an absurdly large degree $d > 2^{256}$. I know for a fact that it has a zero and I would like to ...
1 vote
46 views

### Condition on the minimality of Minkowski units

I am interested in to undrestand when the Minkowski units in real biquadratic number fields are minimal in the log unit lattices. I have read some pieces of literature online which are investigating ...
255 views

45 views

136 views

### On GCD and lattice reduction

$LLL$ algorithm is vectorized version of Euclidean algorithm for $GCD$. Even the $m=2$ case known to Lagrange and Gauss does not have an $NC$ algorithm for shortest vector. If $GCD$ is in $NC$ and in ...
107 views

### Lattice reduction of basis with non-integer coefficients

Suppose I have an ordered basis $\{b_1, \dots, b_n\}$ of a lattice in $\mathbb{R}^n$, but I do not assume that $b_i \in \mathbb{Z}^n$ for all $1 \leq i \leq n$. I would like to perform lattice ...
218 views

### What are the solutions in numbers of $xyz \mid x^n + y^n + z^n$, $x,y,z$ globally coprime

What are globally coprime integers $x,y,z\in \mathbb Z^*$ such that $xyz$ divide $x^n + y^n + z^n$? I have no other motivation for that problem but its inherent beauty and interest. Note that it can ...
100 views

### Questions in number theory related to $NC$ and $P$-completeness

Given $a,b\in\mathbb N$ find $\operatorname{GCD}(a,b)$. Given $a,b,c\in\mathbb N$ find $x,y\in\mathbb Z$ such that $ax+by=c$. Euclidean algorithm solves both. My question is if either 1 or 2 is in ...
347 views

### About the complexity of some operation involving integers

There are two integers: $A, B$. Given the below four allowed operations (and only them): $A+1$, $A-1$, $\sqrt{A}$, $A^2$ Also, it is only allowed to take the square root of $A$ when this square root ...
119 views

### Examples of real-time transcendental number and superlinear-time trancsendental number

Computation model is defined as Hartmanis and Stearns 4, it is well known that Liouvilles constant $$C_L=\sum_{i=1}^{\infty} 10^{-i!}$$ is computable in real time or linear time 1, 5 especially ...
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 $<\... 2 votes 0 answers 41 views ### Reordering entries of integer symmetric matrix via linear combinations into a symmetric matrix with all its eigenvalues positive with det condition Suppose we have a symmetric matrix$M\in\operatorname{Sym}{M}_{n}(\mathbb{Z})$having some negative eigenvalues. Are there algorithms filling the entries of a (possibly) bigger symmetric matrix$M'\in\...
What efficient algorithms are there to compute the $S$-units of a given imaginary quadratic field $K$, where $S$ is a finite set of non-archimedean primes? Computing $S$-units are implemented in ...