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
1
answer
324
views
Higher roots modulo prime complexity best algorithm
Given integers $a,\ell$ and prime $p$ we need to find the roots of the algebraic equation $x^\ell\equiv a\bmod p$. We know there are at most $\ell$ such $x$.
What is the best method to find all such ...
3
votes
1
answer
77
views
Level sums, displacements: how to determine them efficiently?
Let $R =\mathbb{Z}/N \mathbb{Z}$. Let $f:R\to \mathbb{R}$,
$\rho:R\to \lbrack 0,1\rbrack$. We assume that it takes trivial time to compute any given value $f(m)$ or $\rho(m)$.
Define $$S(\delta,m) = ...
- 20.2k
2
votes
0
answers
403
views
lower bounding the absolute value of a determinant
In a problem that I'm working on currently, the following question came up and I feel this should be fairly elementary, but I couldn't prove it myself/couldn't find a reference. Any pointers or ...
- 305
3
votes
0
answers
186
views
Factoring problem similar to $RSA$ structure that is possibly not $NP$ complete and not $coNP$ also?
Standard factoring problem $\Pi_1$ is 'Given integers $N$ and $M$ is there a factor $d\in[1,M]$ of $N$?'. This is in $NP$ since such a factor is the witness and in $coNP$ since one can check all the ...
- 13.9k
2
votes
2
answers
2k
views
Efficient sum of squares decomposition
Sum of 4 squares decomposition is the well-known result. I'm interested only in negative/non-negative separation with focus on efficiency and large numbers. I'm looking for alternatives or extensions ...
6
votes
4
answers
552
views
(Non)uniqueness of the common-factor graph
Let $S=\{x_1,\ldots,x_k\}$ be a set of $k$ distinct natural numbers,
a subset of $\{1,\ldots,n\} = \mathbb{N}_{\le n}$.
Define the common-factor graph $G(S)$ as the (undirected) graph with
a node for ...
- 151k
1
vote
0
answers
346
views
approaching the border between absolute convergence and divergence of series
Let us consider absolute convergent series $\ell^{1^+}$ ordered under eventual dominance (mod finite) $<^*$. T. Bartoszynski proved that unbounded number ${\frak b}(\ell^{1^+}, <^*)$ equals ...
- 88
8
votes
2
answers
1k
views
How to compute Dedekind eta function efficiently?
According to wiki: https://en.wikipedia.org/wiki/Dedekind_eta_function, Dedekind eta function is defined in many equivalent forms. But none of them is an explicit description (say in algorithmic ...
- 475
1
vote
1
answer
138
views
How to compute the Müller modular polynomials?
According to R.A.Kazmi's dissertation "Isogenies and Cryptography" (Page 22), given an isogeny degree $l$, the Müller modular polynomials are defined as
$$G_l(x,y)=\sum_{r=0}^{l+1}\sum_{k=0}^{v}a_{...
- 475
19
votes
1
answer
913
views
What computer program for automorphic forms
This question has its origins in this entertaining discussion on MO.
There are many programs (CAS) and libraries that are able to handle algebraic expressions. These are both a verification tool for (...
- 5,424
4
votes
1
answer
756
views
Conjecture on palindromic numbers
The conjecture is as follows:
Let $n\in\mathbb{N}\setminus\{1\}$. Define $a(n)=2^n+1$ and the set:
$$S(n) = \{ (a(n)^m+1)/2\ :\ m\in \mathbb{N}_0\}.$$
Then for all $c\in\mathbb{N}$, the number $(a(n)...
2
votes
0
answers
132
views
Quick computation of a certain exponential sum
Is there a quick way to compute (somewhat accurately) for large $X$, the following exponential sum, where $\Lambda$ is the von Mangoldt function?
$$\int_0^1 \bigg|\sum_{n\le X} \Lambda(n)e(n\alpha)\...
- 1,890
5
votes
1
answer
610
views
Eulerian ordering of the integers modulo n
Let $n>1$ be an integer. Consider the set $C_n := \{0,1, \dots , n-1\}$.
An Eulerian ordering of $C_n$ is an ordering $r_1, \dots, r_n$ of its elements such that:
$$\forall i \le n \ \forall j&...
11
votes
1
answer
474
views
Representing field elements in a computer
I'm wondering if there is existing terminology to describe fields $F$ with the properties below. I don't have a completely precise description of the concept I have in mind, but hopefully this will be ...
- 1,021
3
votes
0
answers
98
views
Deterministic procedure to find irreducible polynomials
In $\Bbb F_q[x_1,\dots,x_n]$ given $d_1,\dots,d_n\in\Bbb N$ is there a deterministic $O(poly(nd\log q))$ algorithm to find an irreducible polynomial with $d=\max_{i\in\{1,\dots,n\}}d_i$ and $d_i=deg(...
- 13.9k
8
votes
1
answer
484
views
simple conjecture on palindromes in base 10 [closed]
The conjecture says that for any a, b belong to the the set of non-negative integers ($a$ and $b$ are not necessarily distinct), taking any natural value of $c$; we have always that $$(10^c-1) \cdot \...
6
votes
2
answers
323
views
Computing the relative class group (with Galois action) of relatively large cyclotomic groups
For a cyclotomic field $K = \mathbb Q(\zeta_n)$, let $K^+$ be its maximal totally real subfield. We know that $H^+ = Cl(K^+)$ injects into $H = Cl(K)$. I am interested in computing the group $H/H^+$ ...
- 7,746
5
votes
1
answer
2k
views
Solving a system of linear equations over the integers
I have a matrix with integral entries $A$ and integer vector $b$, and want to determine if there is exactly one vector $x$ such that $Ax=b$. $A$ is rectangular, and I know there always is a solution.
...
- 2,429
4
votes
1
answer
254
views
Combinatorial computational problem about 0-1 vectors and sampling algorithms
Let $M \in \{0,1\}^{m\times n}$, where $n\gg 1$ and $m\le n$. A procedure consisting of the following three steps is repeated $t\gg 1$ times:
A row $\require{amsmath} \boldsymbol{r}$ of $M$ picked in ...
- 1,677
0
votes
1
answer
186
views
Could the sequence A287326 be generalized in order to receive expansion of natural power n>3? [closed]
The sequence https://oeis.org/A287326 - is Binomial distributed triangular array, that shows us necessary items to expand perfect cube $n^3$. Summation of $n$-th row of Triangle A287326 from $0$ to $n-...
- 167
0
votes
1
answer
120
views
How many integers $x$ satisfy that $x*p(x) \leq n$, where $p(x)$ means the largest prime factor of $x$?
I guess that the number of integers $x$ which satisfy the condition $x*p(x) \leq n$ is $O(n^{2/3})$ or $O(n^{3/4} / \ln n$), but I cannot prove it. I just write a program to count the number. The ...
- 611
15
votes
2
answers
2k
views
Question on the 52nd (known) Mersenne prime number
In a footnote to the list of known Mersenne prime numbers which can be found here, we read that the "ranking" therein is a provisional one since not all possible exponents between $57 \, 885 ...
- 8,842
6
votes
2
answers
385
views
Is the nth-power-sum graph connected?
This post was inspired by the Square-Sum Problem presented in Numberphile by Matt Parker.
He asked about Hamiltonianness for $n=2$, and we ask about connectedness for all $n \in \mathbb{N}^*$.
...
2
votes
1
answer
228
views
A problem of divisibility
I came across the following problem. Find two integers, $u_{n}$ and $v_{n}$, such that
$$a_{n}=4u_{n}v_{n}+(6n-1)v_{n}+(6n-1)u_{n}+8n^{2}-4n$$
divides
$$b_{n}=-(2n-1)u_{n}v_{n}-(2n^{2}-3n)v_{n}-(2n^...
- 1,197
5
votes
1
answer
354
views
Fastest deterministic factoring algorithm in subexponential space?
Strassen's factoring algorithm shows that $\text{FACTORING} \in \text{DTIME}(N^{\frac{1}{4}+o(1)})$, but if I'm not mistaken in my analysis it also uses a similar amount of space. By making a trade-...
- 2,302
12
votes
2
answers
823
views
GRH and the rank of elliptic curves
I have been using the Magma calculator recently, and while calculating ranks of elliptic curves with very big coefficients, there is a possibility to assume GRH is true, which signaficantly speeds up ...
- 3,738
3
votes
1
answer
238
views
Norm of a Vector in a Number Field (or Order in a Number Field)
I am looking for a measurement, which gives a length of a vector in a number Field? Is there any way or definition for that.
For the Maximal order, What if, I tried to define a map from Maximal order ...
- 149
0
votes
0
answers
257
views
Hercules and the Hydra with time constraints
The game of Hercules vs. the Hydra can be put in terms of a single number in hereditarily-factorized form. For example, if the Hydra is $2^{19^3} \cdot 5^{11^7}$, Hercules must choose between two ...
- 2,302
12
votes
1
answer
547
views
Seeking references for finding primes infinitely often
I've been pondering this weakened version of the finding primes problem for a while:
Is there an algorithm which given $k$ outputs a prime $p > 2^k$ in time $F(\log_2(p))$?
This differs from ...
- 2,302
4
votes
0
answers
122
views
Finding short linear combinations in abelian groups
Let $M$ be a finitely generated abelian group. Assume we are given a presentation of $M$, that is
\begin{equation*}
M = \frac{\bigoplus_{i=1}^r \mathbf{Z}g_i}{\sum_{j=1}^s \mathbf{Z} r_j}
\end{...
- 20.8k
4
votes
0
answers
281
views
Parity of number of primes
In https://arxiv.org/abs/1009.3956 is it shown there is a $c>0$ such that $\pi(x)\bmod2$ can be computed in $o(x^{\frac12})$ time (more precisely number of primes $\bmod 2$ for an interval of ...
- 13.9k
0
votes
0
answers
74
views
Transformation or correspondence between language and real number
As we know, formal language can be regarded as a set of strings of alphabet, and real number can be regarded as sequence generated by set of integers, for example, denominators of the simple continued ...
- 3,104
2
votes
0
answers
147
views
Any proved connection between Roth theorem and hartmanis stearns conjecture?
Roth theorem classifies numbers into two classes, one is rational and transcendental, another is irrational algebraic numbers, by the number of solutions to the inequality (finite or infinite), and ...
- 3,104
3
votes
0
answers
131
views
Improving prime number generation probability?
Deterministic generation of primes in polynomial time is unknown.
Is there a way to probablistically in $O(n^c)$ time bound for some $c>0$ generate polynomially $\Omega(n^c)$ many integers in $[0,...
- 13.9k
3
votes
2
answers
332
views
On generating squarefree integers and primes?
Given an $\alpha\in(0,1)$ and $n\in\Bbb N$ what are some known deterministic algorithms to sample $O(n^\alpha)$ (not just get one) square free integers of $n$ bits? Is it $O(n^{\alpha})$ complexity?
...
- 13.9k
1
vote
1
answer
145
views
Estimate for de Bruijn function with small fixed smoothness bound
Let $\Psi(x,B)$ denote the number of $B$-smooth numbers less than $x$. Wikipedia gives the following "good estimate" for small, fixed $B$:
$$\Psi(x,B) \sim \frac{1}{\pi(B)!} \prod_{p\le B}\frac{\log ...
1
vote
0
answers
414
views
Norm to Principal Ideal
Over a number field, given the norm of an principal ideal, is there a way to find the principal ideal?
Also, Given ideals is there an algorithm to find principal ideals?
- 149
1
vote
0
answers
133
views
Finding Generators of an Ideal Over Number Field? [closed]
Is there any way or algorithm to find generators of an ideal over number field? (A algorithm that can be implemented and not expensive)
- 149
18
votes
1
answer
607
views
Complexity of a Fibonacci numbers discrete log variation
In my work I encountered the following
FIBMOD PROBLEM:
Given $k,m$ in binary, decide if there exists $n$ such that
$\, F_n = k \,$ (mod $m$). Here $F_n$ is a Fibonacci number.
This is a variation ...
- 17.1k
3
votes
0
answers
171
views
Scalar multiplication via the Kummer surface of a genus $2$ curve by $\sqrt{5}$
I hope this is a good question.
Recently I worked with genus two curves $H$ that have multiplication by $[\zeta_5]\in \text{Aut}(H)$, that is, multiplication by $e^{2\pi i/5}$. This automorphism is ...
7
votes
1
answer
382
views
Counting twin primes efficiently
This question, as well as its answers and comments, highlights a lot of unsettling numerical coincidences where certain sums over twin primes ostensibly converge to all kinds of weird values, however ...
- 5,590
48
votes
4
answers
3k
views
Twin primes conjecture and extrapolation method
Let $(p_1, p_2)$ be a twin prime pair, where we include $(2, 3)$. If $p_1 \equiv 1$ mod $4$ then we let $t_{(p_1, p_2)} := p_1 ^ 2 / p_2 ^ 2$ otherwise, we let $t_{(p_1, p_2)} := p_2 ^ 2 / p_1 ^ 2$.
...
- 1,305
1
vote
1
answer
153
views
Specializing non-trivial primality tests
Primes $p$ are integers with no factors (composite allowed) in $[1,p]$. There is a polynomial time test for them.
Given an interval $[a,b]$ what is the best way to test given integer $q$ has no ...
- 13.9k
1
vote
0
answers
94
views
How to encode a set of whole numbers $\{a_1,a_2,...,a_n\}$ such that given a number $x$ we can test if $x \in \{a_1,a_2,...,a_n\}$ [closed]
Suppose we have a set of whole numbers $\{a_1,a_2,...,a_n\}$. Is there a way to encode them into a new number $e$ such that we can use $e$ to test if a given number $x \in \{a_1,a_2,...,a_n\}$? So ...
- 111
2
votes
0
answers
120
views
Conjectures that can be tested with large numbers of Hecke eigenvalues of GSp(4) automorphic forms
As part of my thesis work I have proved Ibukiyama's conjecture implies something about $\mathrm{SO}(5)$ forms associated to certain lattices lifting to $\mathrm{GSp}(4)$ (This was originally a ...
11
votes
4
answers
3k
views
Computational complexity of finding the smallest number with n factors
Given $n \in \mathbb{N}$, suppose we seek the smallest number $f(n)$ with
at least $n$ distinct factors,
excluding $1$ and $n$.
For example, for $n=6$, $f(6)=24$,
because $24$ has the $6$ distinct ...
- 151k
11
votes
4
answers
944
views
How close can powers of coprime integers get?
Given coprime $a, b$, what is $$ \min_{x, y > 0} |a^x - b^y| $$
Here $x, y$ are integers. Obviously taking $x = y = 0$ gives an uninteresting answer; in general how close can these powers get? ...
- 1,703
1
vote
2
answers
347
views
Determining if a number is k-rough without factoring
A k-rough number is a natural number whose smallest prime factor is >= k, basically in opposition to the notion of a smooth number. Clearly, it's trivially easy to generate a k-rough composite number:...
- 379
2
votes
1
answer
416
views
How hard is it to compute these prime factor related problems?
We know that computing number of prime factors implies efficient factoring algorithm (How hard is it to compute the number of prime factors of a given integer?).
Let $\omega(n)$ be number of distinct ...
- 13.9k
-1
votes
1
answer
177
views
Solving quaternary quadratic forms modulo $q$ efficiently
Given a quaternary quadratic equation of form $$Q(a,b,c,d)=m$$ in $\Bbb Z[a,b,c,d]$ with coefficient sizes and $|m|$ bounded in magnitude by $B\in\Bbb N$ where $m\neq0$ if we are looking for solutions ...
- 13.9k