# Questions tagged [computational-number-theory]

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

422
questions

0
votes

0
answers

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 ...

6
votes

0
answers

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

0
answers

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 ...

0
votes

0
answers

255
views

### Counting perfect powers using primes

Result
Let $n\in\mathbb{N}_{\geq1}$
$n$ is by definition a perfect power iff
$\,\ \exists m,k\in\mathbb{N}_{>1}:n=m^{\,k}$
Let $N(n)$ be the number of perfect powers $\leq n$
We define
$$\mathbb{...

0
votes

1
answer

102
views

### Residues distribution modulo an interval

Given a number $n$ and an Interval $I = [ \; \lfloor n^{1/4} \rfloor, \lfloor n^{(1/3) \rfloor \;} ]$, can we say anything about the distribution of $\{ n \mod b \;\;| \; b \in I \}$?
In particular, ...

6
votes

1
answer

562
views

### On a fast high precision numerical analysis C library

This is probably a $y=f(x)$ question, but I searched several times on the MathOverflow without success so I decided to explicitly ask for the help of other members: please feel free to ask me to ...

1
vote

0
answers

28
views

### Does $2$ variable linear Diophantine equation in $NC$ imply $2$ dimensional shortest vector is in $NC$?

Consider the Linear Diophantine in known $a,b,c\in\mathbb Z$
$$ax+by=c.$$
Above can be solve by Extended Euclidean which is not in $NC$ as far as we know. It is clear if Extended Euclidean is in $NC$ ...

0
votes

0
answers

144
views

### On distribution of prime pairs coming from certain polynomials

Consider the polynomials
$$g(x)=(2x)^4+((2x)^2+1)^2$$
$$h(x)=(2x)^4+((2x)^2-1)^2.$$
If $k$ odd integers $x_1,\dots,x_k$ are uniformly randomly chosen in $(t,2t)$ and the polynomials are evaluated at ...

13
votes

2
answers

587
views

### How many players are needed so that two evenly matched teams can be picked?

We have a pool of $n$ players of a game, each player is assigned a "skill" which is an integer $1\leq s\leq 100$. We are now going to pick teams of $5$ players, where the team's skill is ...

0
votes

0
answers

316
views

### Percent of rational coordinates that is a multiple of another point on the elliptic curve

Consider elliptic curves $E:= y^2=x^3+Ax+B $ (A, B are integers) which have points $P, Q$ with rational coordinates and satisfy $P=[n]Q, n>1$. Now consider the below problem:
Input: Rational ...

-2
votes

2
answers

144
views

### Calculate the great common factor between $2^{2n+1}-1$ and $2^{4m+2}+1$ [closed]

How to calculate the great common factor between $2^{2n+1}-1$ and $2^{4m+2}+1$, where $n$ and $m$ are positive numbers.
We guess that: the great common factor is $1$.

1
vote

0
answers

117
views

### Quadratic equations over Gaussian integers

Given an equation $x^2\equiv(a+ib)\bmod(c+id)$ where $a,b,c,d\in\mathbb Z$ holds, how to test if the equation has solutions and how to find the solutions in polynomial in $\log(|abcd|)$ time if $c+id$ ...

0
votes

0
answers

55
views

### Using coppersmith for bounded solution of a short linear Diophantine problem

I have a $3$-variable linear Diophantine equation
$$ax+by+cz=r$$ where $a,b,c,r\in\mathbb Z$ are known and can be as large in magnitude as needed and I know the equation has a solution $x,y,z\in\...

84
votes

2
answers

6k
views

### A little number theoretic game

I came up with this little two player game:
The players take turns naming a positive integer. When one player says the number n, the other player can only reply in two different ways: They can either ...

4
votes

4
answers

545
views

### What or where is the series expansion of the function $\ln\bigl(\frac{\tan x}{x}-1\bigr)$ or $\ln(\tan x-x)$ around $x=0$?

It is known that
\begin{equation*}
\tan x=\sum_{k=1}^{\infty}\frac{2^{2k}\bigl(2^{2k}-1\bigr)}{(2k)!}|B_{2k}|x^{2k-1}, \quad |x|<\frac{\pi}{2}
\end{equation*}
and
\begin{equation*}
\ln\tan x=\ln x+\...

2
votes

0
answers

192
views

### Modular inverse computation - avoiding Euclidean algorithm

Modular inverse is known to be computable by Extended Euclidean algorithm which is the reaping the rewards of computing the GCD of two numbers or proving two numbers are coprime.
If we already know ...

1
vote

0
answers

110
views

### Which real functions benefit from the Fundamental Theorem of Interval Analysis?

I'm reading Introduction to Interval Analysis, by Moore, Baker & Cloud and complementing it with Global Optimization using Interval Analysis, by Hansen & Walster.
Theorem 5.1 - Fundamental ...

5
votes

1
answer

293
views

### Parity of number of solutions to Diophantine equations

By $MRDP$ resolution of Hilbert's tenth, we infer, counting number of solutions to Diophantine equations is undecidable.
Is parity of number of solutions to Diophantine equations undecidable?

6
votes

0
answers

91
views

### Equivalence of primes based on the partition of their Pisano periods

The period of Fibonacci numbers modulo $m$ is called Pisano period and its length is denoted as $\pi(m)$. Define the Pisano partition of $m$ as the set partition of the indices $\{0,1,\dotsc,\pi(m)-1\}...

12
votes

1
answer

2k
views

### Primality of a number of more than 50k digits

With modern tecnology is it possible to prove the primality of a number of more than 50k digits?
Obviously not a prime for which specific methods for testing primality are known like Mersenne primes.

1
vote

1
answer

92
views

### Deduce kernel of isogeny from action on torsion points

I'm stuck with the following problem:
In Petit's work "Faster Algorithms for Isogeny Problems using Torsion Point Images", p. 8, he says that we can deduce $\ker \psi_{N_2}$ knowing the ...

3
votes

1
answer

148
views

### What is meant by a meet-in-the-middle approach?

I'm studing C. Petit's work "Faster algorithms for isogeny problems using torsion point images" (link) and he talks about meet-in-the-middle approach/strategy for solve some isogenies ...

5
votes

1
answer

417
views

### Discrete log problem modified

Suppose one is given an odd prime $p$, a generator $g$ of $(\mathbb Z/p \mathbb Z)^*$ and two integers $a$ and $b$. Is there an efficient method to determine whether $\log_g a < \log_g b$? (Here we ...

0
votes

0
answers

113
views

### Will an integer program to deterministically factor integers help derandomize $\mathbb F_q[x]$ factoring?

There are many analogies between the objects $\mathbb F_q[x]$ and $\mathbb Z$.
Supposing there is a fixed (say $10^9$) dimension linear integer program (describable without any objective function) in ...

2
votes

1
answer

210
views

### Modular square roots problem which is $NP$ hard

It is well known extracting modular square roots modulo a composite number factors the modulus.
On other hand given $u,v>0$ and an integer $n$, deciding if there is a factor of $n$ in $[u,v]$ is $...

1
vote

0
answers

62
views

### Is this factorization problem in EXP?

Factorization is not known to have a polynomial time algorithm. Traditionally the input length is number of bits in representation of the integer to be factored.
However now consider integers of form $...

4
votes

0
answers

142
views

### What are the modularity conjectures for Artin motives?

Classically, singular cohomology is an important tool for studying topological spaces, in particular, complex varieties. In the mid-twentieth century it was realized that there are many analogues of ...

4
votes

2
answers

196
views

### "Efficient" way to build a table of multiplicative orders modulo $p$ of a fixed integer $a$

Given an integer $a$, I would like to build a table of entries $(p, \text{ord}_p(a))$, where $p$ runs over the prime numbers not dividing $a$ and not exceeding a fixed parameter $P$, and $\text{ord}_p(...

3
votes

0
answers

249
views

### Ask for a generating function or an explicit expression of a triangle of positive integers

Preliminaries
I encountered the following triangle of positive integers:
$c_{n,k}$
$n=1$
$n=2$
$n=3$
$n=4$
$n=5$
$n=6$
$n=7$
$n=8$
$k=0$
$1$
$3$
$15$
$105$
$315$
$3465$
$45045$
$45045$
$k=1$
$5$
$...

3
votes

0
answers

112
views

### Ways to tell from residues modulo prime factors if $z$ is below half point

Let $N=\prod_{k=0}^{k=m}{ p_k }$ be a square-free odd integer where $p_k$ is a prime. If we are given any integer $g$ such that $0<g<N$, it is very easy to tell if $g < \frac{N}{2}$ or not. ...

2
votes

0
answers

113
views

### How to compute torsion subgroup $E[24]$ over $\overline{\mathbb{Q}}$

If I have an elliptic curve $E: y^2=x^3-15x+22$ over $\mathbb{Q}$ with CM from the imaginary quadratic field $\mathbb{Q}(\sqrt{-3})$ then how do I compute the $24$-torsion subgroup $E[24]$ over $\...

31
votes

8
answers

8k
views

### Why is integer factoring hard while determining whether an integer is prime easy?

In 2002, the discovery of the AKS algorithm proved that it is possible to determine whether an integer is prime in polynomial time deterministically. However, it is still not known whether there is an ...

2
votes

0
answers

83
views

### Integers solutions of products of truncated Riemann zeta functions

Let $n \in \mathbb{N}$ be a positive integer.
It is possible to prove that the equation $F_1(n)=m$ where $m \in \mathbb{Z}$ and
$$
F_1(n)=(1+2+\ldots+n)\cdot\left(\frac{1}{1}+\frac{1}{2}+\dots+\frac{1}...

0
votes

0
answers

45
views

### Does this approximate linear Diophantine Equation have bounded number of solutions?

Consider the linear diophantine equation
$$\alpha u+\beta v =r+ \delta$$
where $\alpha,\beta,r\in\mathbb Q$ are known and their binary expansion has $O(k)$ bits to exactly represent them and $\delta\...

15
votes

0
answers

318
views

### Do primes of the form $4k+1$ ever lead the greatest prime factor race?

Analogous to Chebyshev's race between primes, I examined the race between primes in the greatest prime factors, GPF, of natural numbers. Similar to the regular prime race, in the GPF race, the ...

6
votes

2
answers

272
views

### Does the $p$-adic regulator depend on Weierstrass model?

I am a little confused on the $p$-adic regulator on elliptic curves and what happens when you switch to different Weierstrass models. Restrict to ell. curves over $\mathbb Q$ for simplicity.
From my ...

13
votes

1
answer

544
views

### Can we compute the first $n$ digits of $\pi$ in $F(n)$ time?

I've seen various fast algorithms for computing the first few, or directly the $n$-th, digits of $\pi$.
However, it seems to me that all these algorithms assume (see last sentence here) that there are ...

0
votes

2
answers

235
views

### Counting powerful integers. Lower bounds

Remark: The upper bounds are perhaps still more interesting; I may address them in another post.
PROBLEM: Find simple (numerically efficient) lower bounds for the number of powerful integers (...

8
votes

1
answer

349
views

### Computational efficiency of character sums for counting finite field points on a curve

It is a well-known fact that one can compute the number of points on a curve over a finite field via character sums. For instance,
$$5+1+\sum_{x\in GF(5)}\varphi(x(1-x)(1-2x))$$
counts the number of ...

1
vote

1
answer

208
views

### Robin's inequality for odd numbers

In this article (Theorem 1.2) there is a proof for Robin's inequality for odd numbers,
$\sigma(n)/n< e^{\gamma}\log(\log(n))$ where $\gamma$ is the Euler-Mascheroni constant and $\sigma(n)$ is the ...

4
votes

2
answers

238
views

### Maximal entropy of integer partitions of $n$

Let $\operatorname{Part}(n)$ be the set of integer partitions of $n$.
A partition $p \in \operatorname{Part}(n)$ has $k$ summands and $d$ distinct summand $n_i$, with $d \leq k$ and $d$ frequencies $...

2
votes

0
answers

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 ...

4
votes

0
answers

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 ...

5
votes

1
answer

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 ...

4
votes

0
answers

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 ...

7
votes

1
answer

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 ...

0
votes

1
answer

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 ...

3
votes

0
answers

125
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 $<\...

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\...

1
vote

0
answers

44
views

### Algorithm to compute S-units in imaginary quadratic number field

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 ...