# Questions tagged [computational-number-theory]

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

364
questions

2
votes

0
answers

78
views

### Computing coefficients of theta functions associated to quadratic forms

If we take an integral positive definite quadratic form $Q$ and set $\Theta_Q(z) = \sum_{k\geq 0}R_Q(k)e^{2\pi ikz}$, what are the most efficient algorithms to compute the $R_Q(k)$? I am aware e.g. of ...

4
votes

1
answer

661
views

### Is there a way to specify a special kind of reciprocals of natural numbers?

Any number with of a form $\frac{1}{n}$ has a decimal with a repetend of finite length that is never longer than $n$ (provable by Dirichlet principle). (Example: $\frac{92}{99}=0.929292\ldots$ in ...

2
votes

0
answers

235
views

### How soon can we represent a number as the sum of two primes?

Posting in MO since it was unanswered in MSE.
Goldbach's conjecture says that every even number can be represented as the sum of two primes. But how soon can we find such a representation. Taking $20 =...

0
votes

0
answers

62
views

### Complexity of small near-reciprocals at $\frac34+\epsilon$ exponent - square free smooth number case

Let $q$ be large composite square free $O(\operatorname{polylog}(T))$-smooth number in $[T,2T]$ where $T$ is a parameter.
According to the paper https://arxiv.org/abs/1103.2879 we can have many ...

0
votes

0
answers

53
views

### Complexity of small near-reciprocals at $\frac34+\epsilon$ exponent - prime power number case

Let $q=p^r$ be large prime power of prime $p$ with $q\in[T,2T]$ where $T$ is a parameter.
According to the paper https://arxiv.org/abs/1103.2879 we can have many integer pairs $a,b$ satisfying $ab\...

0
votes

0
answers

89
views

### Complexity of small near-reciprocals at $\frac34+\epsilon$ exponent - prime number case

Let $p$ be large prime in $[T,2T]$ where $T$ is a parameter.
According to the paper https://arxiv.org/abs/1103.2879 we can have many integer pairs $a,b$ satisfying $ab\equiv c\bmod p$ such that $|c|$ ...

0
votes

1
answer

83
views

### Constructing an integer with small residues for two distinct primes in polynomial time

Given two primes $p,q\in[T,2T]$, how many integers $m$ of size $O(T^{3/2+\epsilon})$ are there such that the residues $m\bmod p$ and $m\bmod q$ are both $O(polylog(T))$? Looking for an answer
Is it ...

2
votes

1
answer

155
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?

4
votes

1
answer

118
views

### Discrete logarithms and primitive elements in finite fields

The recent papers:
R. Granger, T. Kleinjung, J. Zumbragel, "On the Discrete Logarithm
Problem in Finite Fields of Fixed Characteristic," Trans. Amer. Math.
Soc., 370(5) (2018), 3129–3145.
T....

4
votes

1
answer

197
views

### Reliability of ILP approach to number-theoretic optimization

This question is inspired by the recent answer, where @RobPratt proposed to use integer linear programming (ILP) for solving a number-theoretic optimization problem. I will consider a very similar ...

2
votes

2
answers

178
views

### Ask for a proof of an identity involving the product of two Bernoulli numbers

It is well known that the Bernoulli numbers $B_{k}$ for $k\in\{0,1,2,\dotsc\}$ can be generated by
\begin{equation*}
\frac{z}{\textrm{e}^z-1}=\sum_{k=0}^\infty B_k\frac{z^k}{k!}=1-\frac{z}2+\sum_{k=1}^...

1
vote

2
answers

185
views

### Ask for a reference or a proof of an identity involving a finite sum and the Bernoulli numbers

Let $B_{n}$ for $n\ge0$ denote the Bernoulli number generated by
\begin{equation*}
\frac{z}{\textrm{e}^z-1}=\sum_{n=0}^\infty B_n\frac{z^n}{n!}=1-\frac{z}2+\sum_{n=1}^\infty B_{2n}\frac{z^{2n}}{(2n)!},...

1
vote

2
answers

194
views

### Efficiently finding the largest divisor of N less than sqrt(N)

Suppose you have a number
$$
N = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}
$$
and are looking for the largest divisor $d|N$ such that $d^2<N$ (that is, A060775$(N)$.) How can I efficiently find this $d$?
...

8
votes

3
answers

521
views

### Why is there an unexpected increase in the density of certain types of Goldbach primes?

Note: Posted in MO since it was unanswered in MSE.
I was checking how quickly we can verify Goldbach's conjecture for a given even number $n$ and it was clear that searching backward starting from the ...

1
vote

0
answers

76
views

### How common are semiprimes with equally bitsized factors among semiprimes with equal bitsize?

I am curious about the following after having looked at the paper "Almost primes in almost all short intervals", theorem 3 says:
Almost all intervals $[x, x + \log^{3.51}{(x)}]$ with $x ≤ X$...

2
votes

1
answer

217
views

### Eisenstein polynomial of totally ramified extension over $p$-adic field

Let $p\geq 3$ be a prime number, $K$ be a finite extension of $\mathbb{Q}_p$ with no non-trivial unramified subextension, $f(x)$ be an irreducible monic polynomial in $\mathcal{O}_K[x]$, making $L=K[x]...

1
vote

0
answers

49
views

### On bounded discrete logarithm

Given $g^x=h\bmod p$ where x is known to size $p^{2/3}$ we need to find $x$.
Is solving this in $P$ known?

6
votes

1
answer

576
views

### Are there highly composite prime gaps?

Definition: Highly composite prime gap
The three composite numbers between the consecutive primes $643$ and $647$ each have at least three distinct prime factors. This is the first occurrence of prime ...

4
votes

0
answers

168
views

### Is there a polynomial time algorithm for finding primes?

I was wondering if, given $k$, there is a deterministic polynomial time algorithm (polynomial in $k$) which finds a prime number with $k$ digits.
There is clearly a probabilistic one: just take random ...

0
votes

1
answer

80
views

### On polynomials associated to integers power sums [closed]

For $0\leq k\leq n$ integers let $P_k(n):= n^k,\ S_k(n):= P_k(1)+\ldots P_k(n)= 1^k+\ldots n^k$.
Then $P_k(0)=0$, $S_0(n)=n$.
For calculate $S_1(n)$ i consider:
$$P_2(n)-P_2(n-1)=2n+1$$
then
$\begin{...

1
vote

0
answers

107
views

### Can PARI compute class numbers without factoring the discriminant?

When calculating properties of algebraic number fields, one of the hardest steps is factorizing the discriminant of a defining polynomial. This is necessary in the Pohst-Zassenhaus algorithm for ...

1
vote

0
answers

34
views

### Is there an effective genus theory for indefinite quadratic forms?

For positive definite quadratic forms, there is a way to check if two forms are isomorphic by arithmetic equivalence over $GL_n(Z)$ by computing configurations of vector up to some norm and then ...

8
votes

0
answers

210
views

### Hilbert 10th problem for genus 2 equations

Hilbert 10th problem, while undecidable in general, remains open for 2-variable equations: we do not know if there is an algorithm that, for polynomial $P(x,y)$ with integer coefficients, decides ...

0
votes

0
answers

127
views

### On a deterministic primes search problem

I feel the following problem might be resolved already. But I could not find any related answers.
If $p_1,p_2,\dots,p_t$ are primes where $2\leq t=o(\log n)$ is there a prime within $$\prod_{i=1}^...

0
votes

1
answer

99
views

### Computing Lucas sequence for large n

I've been trying to write a test function for Fibonacci pseudo-primes with large $n$. Fibonacci pseudoprimes are composite numbers such that $V_n(P,Q) \equiv P \mod n$ for $P>0$ and $Q =\pm 1$, ...

0
votes

1
answer

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

3
votes

1
answer

81
views

### Can we construct composite Fermat pseudoprimes to integral algebraic bases?

Let $0\neq \beta\in\overline{\mathbb{Z}}$ and let $n$ be a positive integer coprime to $N_{\mathbb{Q}(\beta)/\mathbb{Q}}(\beta)$. Say that $n$ is a Fermat pseudoprime to base $\beta$ if
$$\beta^{n^{[\...

1
vote

1
answer

124
views

### Counting $\mathrm{mod}\:p$ solutions of Diophantine equation in two variables taking $O(p^2)$ time

Are there Diophantine equations in two variables such that counting solutions $\mathrm{mod}\:p$ requires $O(p^2)$ time?
Geometrically this means we have to sort through a positive proportion of the ...

5
votes

0
answers

281
views

### A question on infinite arithmetic progressions

I was working on a problem that consisted of deciding if the language a finite automaton (the alphabet of which is $\{0,1\}$ and the words accepted are binary encoded positive integers) contains an ...

25
votes

3
answers

2k
views

### Sum of squares and divisibility

Consider an integer of the form $$N = 1 + \sum_{i=1}^r d_i^2$$ where $d_i \in \mathbb{N}_{\ge 3}$ and $d_i^2$ divides $N$.
Question: Must $r$ be greater than or equal to $9$?
Checking (with SageMath): ...

0
votes

0
answers

110
views

### what are all possible pairs (k,m) such that n=2k^2+ m^2

I am working on a problem in number theory and would like to count all possible ways to partition an integer $n\geq 1$ into pairs $(k,m)$ of positive integers such that $n=2k^2+m^2$ and $n=4k^2+m^2$. ...

3
votes

0
answers

84
views

### Next smooth number

I want to find the next $n \in \mathbb{N}$ such that
$$s < n = \prod_{p_i \in \mathbb{P}_B} {p_i}^{a_i}$$
Where $\mathbb{P}_B$ is the set of primes not greater than $B$
I know that we can generate ...

3
votes

1
answer

129
views

### Is factorial computation known to be in a class smaller than $FEXP$?

Functional version of the counting hierarchy is $FCH$. It is an open problem whether there a sequence of $poly(log(n))$ number of $+,\times$ operations utilizing the assistance of $O(1)$ number of ...

6
votes

1
answer

292
views

### How large can the dimension of a 'Span of powers of a finite field basis' be?

Let $p$ be a prime. For finite field $\mathbb{F}_{p^k}$ and $d\in\mathbb{Z}^+$, I am considering the following quantity, where we interpret the field $\mathbb{F}_{p^k}$ also as a $\mathbb{F}_p$-vector ...

1
vote

3
answers

236
views

### How do I find abelian cubic extension over $\mathbb{Q}$ with class number more than 1?

I am trying to see them as subfield $\mathbb{Q}(\zeta_n).$ I feel it is a tiring job by using SageMath. Moreover, I am ending up with the abelian cubic field with the class number $1.$
I appreciate ...

1
vote

0
answers

445
views

### Langlands program and complexity theory

Back when I was an undergraduate, I spent some time reading the about the modularity conjecture, but the details are fuzzy now.
One of the motivations I imagined for the Langlands program was for ...

34
votes

1
answer

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

0
votes

1
answer

182
views

### How to simulate Poisson point process

How to simulate a process $S_t=\sum_{0\leq s\leq t}\Delta_s,$ where $\Delta_s$ is a Poisson point process with values in $(0,\infty)$ and with characteristic measure $\Pi(dx)=\frac{\alpha}{\Gamma(1-\...

6
votes

0
answers

137
views

### Certificate for computation of ideal class group

Is there a known way of producing a certificate that can be used to more quickly verify that an ideal class group of a number field was computed correctly? More formally, I would like to know if there'...

3
votes

0
answers

76
views

### Study of relative class number of 'non-abelian' CM field by using L-functions

I'm currently interested in finding good upper bounds for the relative class numbers of non-abelian CM-fields.
So I'm looking for some references to learn the techniques that can be useful.
So far, I ...

2
votes

0
answers

132
views

### Sum of all primes below $n$ without listing all primes below $n$

Asymptotically there is around $\frac{n}{\ln n}$ primes below a given integer $n$. Thus $\frac{n}{\ln n}$ is a lower bound for the time complexity of any algorithm that at some point finds each prime ...

0
votes

0
answers

61
views

### Time complexity of asymmetric sums of divisor function

Let $\sigma_0:\mathbb{Z}_{\geq 1}\to \mathbb{Z}_{\geq 1}$ be the divisor counting function.
Naively it seems the time complexity of computing $\sum_{i=1}^n \sigma_0(i)$ is at least linear but it can ...

2
votes

2
answers

236
views

### Coefficient field of a newform using Magma

It is well-known that, for a newform $f = \sum c_nq^n \in \Gamma_0(N)$, the coefficient field $K_f := \mathbb{Q}(a_1, a_2, a_3, \cdots )$ is a number field.
I am introducing myself in Magma, and I was ...

19
votes

1
answer

1k
views

### Possible contemporary improvement to bounded gaps between primes?

In his summary of his book Bounded gaps between primes: the epic breakthroughs of the early 21st century, Kevin Broughan writes
Which brings me to my final remark: where to next in the bounded gaps ...

4
votes

0
answers

111
views

### Riemann-Siegel formula for Dirichlet characters

After unearthing and giving a proof of what is now known as the Riemann--Siegel formula for the Riemann zeta function enabling the computation of $\zeta(1/2+iT)$ in time $O(T^{1/2})$,
in 1943 Siegel ...

-2
votes

1
answer

290
views

### Why wolfram alpha gives integers solutions for some equations of the form $ x^3 +(k\times10^n)^3 + z^3=0 $?

I have tried to get representations of some integers as sum of three cubic of the form $x^3+(k*10^n)^3+z^3$ with $k$ is integer and $n$ is a postive integer, I took this example : $(48807585839879)^3-(...

3
votes

1
answer

146
views

### Connecting different ways of constructing cubic extensions of $\mathbb{Q}$

There are at least two ways to construct cyclic cubic extensions of $\mathbb{Q}$ as explained below. (A third one is given in the answer to an earlier question).
Given $A, B, C$ integers with $A\neq ...

1
vote

0
answers

85
views

### Smooth number pairs satisfying a congruence

Let $\mathcal P=\{p_1,\dots,p_{2t}\}$ be $2t$ primes between $2^\ell$ and $2^{\ell+1}$ and fix an exponent bound $a\in\mathbb Z_{\geq2}$.
Fix $N\in\mathbb N$ whose prime factors $p$ satisfy $p>2^{\...

0
votes

0
answers

82
views

### How to determine if a unramifed prime split or not?

Let $K$ be the Number field and $L$ be finite extension where $\mathfrak{p}$ prime of K is unramified. Are there any conditions on $\mathfrak{p}$ so that I can say $\mathfrak{p}$ splits completely in ...

4
votes

0
answers

182
views

### Ramsey Numbers for Integers

Erdos defined $f(n)$ to be the minimum $r$ such that there is an $r$-coloring of the positive integers less than $n$, wherein $n$ cannot be written as the sum of distinct monochromatic integers. ...