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 ...
- 221
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 =...
- 4,144
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 ...
- 12.8k
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\...
- 12.8k
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|$ ...
- 12.8k
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 ...
- 12.8k
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?
- 12.8k
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....
- 425
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 ...
- 25.3k
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}^...
- 390
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)!},...
- 390
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,358
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 ...
- 4,144
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$...
- 11
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]...
- 417
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?
- 11
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,144
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 ...
- 1,161
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{...
- 3,935
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 ...
- 125
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 ...
- 2,389
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}^...
- 12.8k
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$ ...
- 12.8k
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^{[\...
- 358
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 ...
- 21
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 ...
- 51
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): ...
- 22.9k
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$. ...
- 11
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 ...
- 131
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 ...
- 12.8k
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 ...
- 69
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 ...
- 653
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 ...
- 59
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 ...
- 4,205
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-\...
- 165
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'...
- 1,756
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 ...
- 951
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 ...
- 21
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 ...
- 1
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 ...
- 29
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 ...
- 31k
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 ...
- 8,928
-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-(...
- 2,123
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,194
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^{\...
- 12.8k
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 ...
- 653
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. ...
- 71