Questions tagged [computational-number-theory]
Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.
477 questions
4
votes
0
answers
104
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 ...
- 13.9k
7
votes
1
answer
352
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 ...
- 71
0
votes
1
answer
125
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,104
3
votes
0
answers
135
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 $<\...
- 34.4k
2
votes
0
answers
45
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\...
- 573
1
vote
0
answers
50
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 ...
- 577
4
votes
1
answer
377
views
Find $\mathbb{Z}$-basis of module over Dedekind domain provided its pseudobasis
Let $K$ be number field of degree $d$. Suppose we are given module $
\mathcal{M}$ in form:
\begin{equation}\label{key}
\mathcal{M} = v_1 \cdot \mathfrak{a}_1 \oplus v_2 \cdot \mathfrak{a}_2 \...
11
votes
2
answers
1k
views
Do consecutive integers have a big prime factor?
Let us say that three consecutive positive integers $(m-1,m,m+1)$ have a big prime factor if the largest prime factor $p$ of $N=(m-1)m(m+1)$ satisfies $e^p>N$.
I ckecked that it is true for all $m&...
7
votes
1
answer
623
views
Algorithm for computing whether a cubic field is monogenic?
I am interested in existing algorithms to compute whether a given non-cyclic, non-pure cubic extension $K/\mathbb{Q}$ is monogenic or not, and if so, to give me a defining polynomial for the integral ...
- 565
4
votes
0
answers
102
views
Reconstructing coefficients of an elliptic curve L-series from the modular form divisor
Let $E$ be an unknown elliptic curve over $\mathbb{Q}$.
Let $L(E, s) = \sum_{n=1}^{\infty} \frac{a_n}{n^s}$ be the L-function of $E$ and write $f(q) = \sum_{n=1}^{\infty} a_n q^n$.
I'm in a setting ...
- 5,637
9
votes
1
answer
738
views
Square root in number field
I'm trying implement an algorithm that, for an element $b$ of a number field $\mathbb{Q}(\alpha)$, if it is a square in $\mathbb{Q}(\alpha)$ (i.e., $\exists x\in\mathbb{Q}(\alpha):x^2=b$), computes ...
- 153
0
votes
0
answers
172
views
An application of Koike's Trace Formula
Koike's Trace Formula states that
\begin{equation}
\mbox{Tr}((U_p^{\kappa})^n) = - \sum_{0 \leq u < \sqrt{p^n}\\
(u,p)=1}H(u^2-4p^n)\frac{\gamma(u)^\kappa}{\gamma(u)^2 - p^n}-1,
\end{equation}
...
1
vote
1
answer
241
views
Software tools to find square root modulo $2^t$
Are there any software tools to find modular square roots of $y$ in $$x^2\equiv y\bmod p^t$$ where $p$ is a prime $\geq2$?
Are there any special techniques which can speed up at $p=2$?
- 13.9k
6
votes
1
answer
647
views
How can I efficiently find the "simplest" rational in an interval?
For a hobby software project I am working with exact rational arithmetic, as it happens this produces numbers $\frac{n}{k}$ of huge size even after reducing them, I am searching for an efficient ...
- 163
0
votes
1
answer
63
views
Changing base field for sum of polynomials
Let $L/\mathbb{Q}$ be a finite extension and $f_{1},\dotsc,f_{n}\in L[x_{1},\dotsc,x_{k}]$ be degree $d$ homogeneous polynomials. Is there a way to find homogenous degree $d’$ polynomials $g_{1},\...
- 3
3
votes
1
answer
128
views
Computational Theory problem
Is it possible to have a Turing machine that can compute an ODE equation (ordinary differential equation)?. If there is, then can you explain how can it compute.
- 31
11
votes
1
answer
646
views
Non-trivial solutions for $-(c^2-d^2)(a^2-b^2)=2(ad-bc)(bd+ac)$?
Consider the quartic system in four variables $a,b,c,d\in\mathbb R$:
$$-(c^2-d^2)(a^2-b^2)=2(ad-bc)(bd+ac).$$
Does this system admit rational solution with $$abcd(c^2-d^2)(a^2-b^2)(a^2-c^2)(b^2-d^2)\...
- 13.9k
2
votes
0
answers
118
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 ...
- 323
4
votes
1
answer
995
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 ...
- 211
2
votes
0
answers
300
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 =...
- 5,470
0
votes
1
answer
87
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 ...
- 13.9k
2
votes
1
answer
172
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?
- 13.9k
4
votes
1
answer
309
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....
- 503
5
votes
2
answers
377
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 ...
- 34.4k
2
votes
2
answers
283
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,101
1
vote
2
answers
272
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,101
3
votes
2
answers
902
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$?
...
- 9,114
9
votes
3
answers
584
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 ...
- 5,470
1
vote
0
answers
84
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
515
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]...
- 549
8
votes
1
answer
834
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 ...
- 5,470
9
votes
1
answer
720
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,251
0
votes
1
answer
97
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{...
- 4,165
1
vote
0
answers
136
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
115
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
245
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 ...
- 7,182
0
votes
0
answers
135
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}^...
- 13.9k
1
vote
1
answer
217
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$, ...
- 11
0
votes
1
answer
607
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$ ...
- 13.9k
3
votes
1
answer
116
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^{[\...
- 458
1
vote
1
answer
150
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
313
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
26
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
118
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
113
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
167
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 ...
- 13.9k
8
votes
1
answer
531
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 ...
- 89
1
vote
3
answers
302
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 ...
- 743
1
vote
0
answers
583
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
1k
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 ...
- 5,103