Questions tagged [computational-number-theory]
Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.
1
vote
1answer
97 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 ...
3
votes
1answer
143 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+\...
4
votes
0answers
152 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 ...
-1
votes
1answer
123 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 ...
3
votes
1answer
86 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?
2
votes
0answers
86 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\...
0
votes
0answers
35 views
Computing with a vector subspace equipped with a prescribed basis over finite fields
Let $U$ be a subspace of the finite dimensional vector space $V$ over a field $\mathbb{k}$. Let $B_V$ and $B_U$ be fixed bases for $V$ and $U$ respectively. Let $u \in U$ and let's give ourselves $[u]...
0
votes
1answer
253 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 ...
0
votes
0answers
53 views
Can a rational symmetric matrix $A$ be diagonalized as $A = P \Lambda S$ for some $P, S $ in the general linear group?
Let $A$ be a $3 \times 3$ symmetric matrix with rational entries. Does there exists a unique pair of matrices $P, S \in \text{GL}_3(\mathbb{Z} )$ depending on $A$ such that $A = P \Lambda S$, where $\...
11
votes
2answers
366 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
1answer
137 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$...
4
votes
1answer
219 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 ...
1
vote
0answers
21 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 ...
17
votes
4answers
485 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/...
1
vote
1answer
113 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 ...
1
vote
1answer
81 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
votes
0answers
723 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 $...
12
votes
1answer
187 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 ...
11
votes
1answer
304 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. ...
15
votes
2answers
526 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 ...
0
votes
0answers
56 views
Best method to compute sum of divisors of bounded evaluation of a bivariate quadratic?
Given a bivariate quadratic polynomial $g(u,v)\in\mathbb Z[u,v]$ and an integer $n$. How fast can we compute $\sum_{i=-\ell}^{\ell}\sum_{j=-\ell'}^{\ell'}\sigma_0(g(i,j))\bmod2$ where $\sigma_0$ is ...
0
votes
0answers
180 views
On number of squares by a quadratic
Given a bivariate degree $2$ polynomial $$m^2+(ax−by)^2−2x(ma+2br′)−2y(mb+2br)−4rr'\in\mathbb Z[x,y]$$ where $0<r,r'<\max(a,b)<rr'<m<ab$ with $\gcd(a,b)=1$ holds with max coefficient ...
0
votes
0answers
90 views
How to prove a Mersenne number is not pseudoprime to the base 3?
I start think in finding a small divisor $p$ of $M_n$ then I obtain that $p\mid (3^{M_{n}-1}-1)$ hence $ord_{p}(3)\mid M_{n}-1$
Now can I prove p is the same as $M_{n}$ so that $M_{n}$ is not ...
0
votes
1answer
146 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. ...
4
votes
1answer
190 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
1answer
73 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) = ...
2
votes
0answers
122 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 ...
3
votes
0answers
172 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 ...
1
vote
1answer
434 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
4answers
368 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 ...
1
vote
0answers
258 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 ...
7
votes
2answers
531 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 ...
1
vote
1answer
102 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_{...
18
votes
1answer
589 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 (...
4
votes
1answer
508 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
0answers
117 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)\...
5
votes
1answer
535 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&...
10
votes
1answer
428 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 ...
3
votes
0answers
76 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(...
8
votes
1answer
387 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
2answers
164 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^+$ ...
4
votes
1answer
114 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.
...
4
votes
1answer
232 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 ...
0
votes
1answer
172 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-...
1
vote
1answer
99 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 ...
0
votes
0answers
75 views
Shape Basis Generator of an Ideal
Let $R=K[x_1,...,x_n]$, for a field $K$, and $I$ is radical zero dimensional ideal of $R$. We define $s=\Sigma_{i=1}^{n}a_ix_i$, with $c_i\in K$, a shape basis generator of $I$, if $(s+I)$ generates ...
10
votes
2answers
695 views
Question on the 50th (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 $37 \, 156 \, 667$ ...
6
votes
2answers
308 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
1answer
207 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^...
4
votes
1answer
203 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-...
