# Questions tagged [computational-number-theory]

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

364 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
235 views

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|$ ...
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 ...
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?
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....
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 ...
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
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
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$? ...
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
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$...
217 views

1 vote
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
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 ...
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 ...
127 views

1 vote
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 ...
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 ...
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): ...
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$. ...
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 ...
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 ...
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
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
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 ...
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 ...
182 views

146 views

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