Questions tagged [computational-number-theory]
Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.
476 questions
18
votes
2
answers
6k
views
Efficient computation of integer representation as a sum of three squares
Recently I've been studying the problem of integer representation as sum of three squares. Most of the articles that I've found study the function $r_m(n)$ which counts the number of representations ...
- 4,713
3
votes
1
answer
510
views
Yet another question on sums of the reciprocals of the primes
I recall reading once that the sum $$\sum_{p \,\, \small{\mbox{is a known prime}}} \frac{1}{p}$$
is less than $4$.
Does anybody here know what the ultimate source of this claim is?
Please, let me ...
- 8,842
2
votes
1
answer
235
views
How to get asymptotic expansion of the sum of modified Bessel function $\sum_{n=1}^\infty K_0(s\, n)$ as $s\to 0^+$?
I guess for the modified Bessel funcion $K_0(z)$,
$$\sum_{n=1}^\infty K_0(s\, n)
\sim
\frac{-2\log 2 - \log \pi + \gamma}{2} + \frac{\log s}{2} + \frac{\pi}{2\, s}, \quad s\to 0^+,$$
if taking
$$\...
- 7,193
1
vote
0
answers
123
views
Testing polynomials irreducible over the integers
Let $f\in\operatorname{int}(\mathbb Z)$, the ring of integer-valued rational polynomials. Define $\operatorname{P}^+(f)$ as the number of primes $>0$ that $f$ assumes at distinct integral arguments....
- 862
2
votes
1
answer
913
views
Numbers that are the sum of 2 distinct nonzero squares in exactly 1 way [closed]
I need to emulate this sequence for a program: http://oeis.org/A025302
Stuff that I've taken into account:
After finding the prime divisors of a number. I take any divisor as p and apply the ...
- 7,746
1
vote
1
answer
144
views
Factoring with partial information on gaps
If $N=PQ$ is a semi-prime with $P=N^{\frac12 +\delta}$ and $Q=N^{\frac12-\delta}$ then if we know $\delta\in(0,\frac12)$ to a reasonable precision we can factor $N$ quickly. What precision (number of ...
CommunityBot
- 1
0
votes
0
answers
58
views
Quadrics over the univariate function field with discriminant of minimal degree
Consider a non-degenerate quadric $Q(x,y,z) \subset \mathrm{P}^2$ over the univariate function field $\mathbb{F}_p(t)$, where $\mathbb{F}_p$ is a prime finite field, $p > 2$. For simplicity assume ...
- 1,833
0
votes
1
answer
809
views
Conjecture that relates matrix systems with some specific functions as solution sets
what is written below is a conjecture that I posed , and I ask for a proof or a disproof of it .I have checked the conjecture from $n$=$1$ up to $n$=$10$ using Matlab, and all results were in ...
CommunityBot
- 1
3
votes
1
answer
293
views
Number of lattice points on spheres with center not at the origin
Let $k\ge1$. It is known that the number of lattice points on the $k$-sphere $S^k(0)$ (center at the origin, radius $R$), namely the size of $\mathbb{Z}^{k+1}\cap S^k(0)$, is bounded by $R^{k-1+\...
- 9,720
2
votes
1
answer
415
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 ...
- 191
5
votes
0
answers
195
views
Is there some computational evidence of the $pq$ analog of Serre's conjecture?
The $pq$ analog of Serre's conjecture (see "Mod pq Galois representations and Serre's Conjecture"- Khare, Kiming) states that if $\bar{\rho}_1:G_{\mathbb{Q}}\rightarrow \text{GL}_2(\mathbb{F}_p)$ is a ...
CommunityBot
- 1
-1
votes
1
answer
722
views
summation of Euler totient function
Let $\phi(n)$ be the Euler totient function and let $2\leq k\in\mathbb{N}$. For $m\in\mathbb{N}$, are there any known results, upper bounds (tighter than just removing the coprimality) or ...
- 13k
3
votes
1
answer
108
views
Is coprimality in $NC$?
Following reference https://pdfs.semanticscholar.org/e86e/8d7a267a29b9ad4ca112828109adfec55e8b.pdf claims integer coprimality is in $NC$ and it also has one citation. Is this claim valid?
- 1,602
2
votes
0
answers
127
views
Coppersmith's method to quadrivariate degree $2$ polynomials that behave as bivariate?
We have a polynomial $f(x_1,x_2,x_3,x_4)\in\mathbb Z[x_1,x_2,x_3,x_4]$ where the only monomials are either from set $$\{x_1,x_1x_2,x_2,x_3,x_3x_4,x_4\}$$ and we seek solutions $(x_1,x_2,x_3,x_4)\in\...
- 13.9k
11
votes
2
answers
410
views
Extension of Dickson's theorem on integers of the form $a^2+b^2+2c^2$
Theorems V in this paper of L.E. Dickson states that the following two sets are equal. $$E=\{a^2+b^2+2c^2 \ | \ a,b,c \in \mathbb{Z}\} \ \text{ and } \ F=\mathbb{N} \setminus \{4^k(16n+14) \ | \ k,n \...
2
votes
1
answer
199
views
Decide if a system of arithmetic sequences is an $m$-cover of $\mathbb{N}$
Let $A = \{ a_i + b_i \mathbb{N} \}_{i=1}^{k}$, where $a_1, \ldots, a_k \in \mathbb{N} \cup \{0\}$ and $b_1, \ldots, b_k \in \mathbb{N}$ be a system of arithmetic sequences.
For a positive integer $m$...
- 15.6k
4
votes
1
answer
288
views
Is total degree version and $x,y$ degree version of Coppersmith's theorem correct?
The notes here https://web.eecs.umich.edu/~cpeikert/lic13/lec04.pdf have the note 'Small decryption exponent $d$: so far the best known attack recovers $d$ if it is less than $N^{.292}$. This uses a ...
- 218
18
votes
4
answers
1k
views
In which cyclic cubic number fields does there exist this type of unit?
Let $K$ be a cyclic cubic number field with conductor $f$ and ring of integers $\mathcal{O}_K$.
Define $K$ to be blue if and only if $$\operatorname{Norm}_{K/\mathbb{Q}}(w) = \operatorname{Norm}_{K/...
- 2,391
12
votes
0
answers
1k
views
Euler's totient function and Riemann hypothesis
I am looking for an upper-bound of the Euler's totient function $\varphi$ which would be equivalent to the Riemann hypothesis (RH). There is the following Nicolas' criterion about primorial numbers $...
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 ...
CommunityBot
- 1
1
vote
0
answers
26
views
Uncertainty in semiprime factors
What is maximum $p\in(0,\frac12)$ such that if we know $2p\in(0,1)$ fraction of bits of $PQ$ with $P,Q$ primes it is possible to identify $p$ fraction of bits in each of $P,Q$ with certainty in ...
- 13.9k
1
vote
1
answer
465
views
Taking pairwise coprime integers from prescribed sets
Given $m$ and $n$ in $\mathbb Z_{>0}$ what is the computational complexity of picking $n$ pairwise coprime integers each of $m$ bits when they exist?
Given $m$ and $n$ in $\mathbb Z_{>0}$ what ...
- 4,713
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) = ...
CommunityBot
- 1
1
vote
1
answer
182
views
How many iterations the best biprime factoring method has to factor a number [closed]
I'm researching method of biprime number factoring. I have a biprime number 1012322327 * 1115382761 (19 decimal digits= 1129126872111204847). I'd like to know how many iterations (or trials) the best ...
- 10.4k
12
votes
1
answer
308
views
Factoring polynomials over the abelian closure of the rationals
What algorithms are known to perform the following task?
Input: a univariate polynomial over the rationals $f \in \mathbb{Q}[t]$.
Output: the factorization of $f$ into irreducible factors over the ...
- 20.8k
11
votes
1
answer
496
views
$p$-adic sums of $p$ terms
My question is inspired by this riddle: Let $p \geq 5$ be prime, and let
$$ 1 + \frac 1 2 + \frac 1 3 + \dots + \frac 1 {p-1} = \frac a b $$
where $a/b$ is the fraction expressed in lowest terms. ...
- 9,061
17
votes
2
answers
1k
views
Analogues of the Riemann zeta function that are more computationally tractable?
Many years ago, I was surprised to learn that Andrew Odlyzko does not consider the existing computational evidence for the Riemann hypothesis to be overwhelming. As I understand it, one reason is as ...
CommunityBot
- 1
0
votes
1
answer
159
views
Parity and number of squares taken by polynomials in a range?
I have a polynomial $f(x)=a^2x^2+bx+c\in\mathbb Z[x]$ with $f(x)$ not a constant times a square and $abc\neq0$ and I want to know how many $x$ between $-a$ and $a$ the polynomial is a perfect square. ...
- 91
2
votes
0
answers
402
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
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^+$ ...
- 5,670
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 ...
- 16.6k
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_{...
- 5,407
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 (...
- 37k
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 ...
- 4,727
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
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.
...
- 96.4k
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 ...
- 109k
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}^*$.
...
- 105k
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^...
- 34.3k
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,576
18
votes
3
answers
561
views
How to construct a small coprime?
Given an integer $n$, is there a deterministic algorithm to find in poly$(\log n)$ time an integer $q$, $n < q< n^{c}$, such that $gcd(q,n!)=1$? Here $c>1$ is some fixed constant.
...
- 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 ...
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
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 ...
- 47.4k
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