Questions tagged [computational-number-theory]

Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.

Filter by
Sorted by
Tagged with
3 votes
1 answer
271 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+\...
Right's user avatar
  • 187
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 ...
user avatar
-1 votes
1 answer
670 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 ...
Nick A. R.'s user avatar
3 votes
1 answer
103 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?
Turbo's user avatar
  • 13.7k
2 votes
0 answers
122 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\...
Turbo's user avatar
  • 13.7k
0 votes
1 answer
808 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 ...
Ahmad Jamil Ahmad Masad's user avatar
11 votes
2 answers
401 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 \...
Sebastien Palcoux's user avatar
2 votes
1 answer
170 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$...
Victor's user avatar
  • 655
4 votes
1 answer
284 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 ...
Turbo's user avatar
  • 13.7k
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 ...
Turbo's user avatar
  • 13.7k
18 votes
4 answers
994 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/...
Christine McMeekin's user avatar
1 vote
1 answer
451 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 ...
Turbo's user avatar
  • 13.7k
1 vote
1 answer
175 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 ...
aleksv's user avatar
  • 113
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 $...
Sebastien Palcoux's user avatar
12 votes
1 answer
292 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 ...
Gro-Tsen's user avatar
  • 29.8k
11 votes
1 answer
470 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. ...
Itai Bar-Natan's user avatar
17 votes
2 answers
941 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 ...
Timothy Chow's user avatar
  • 78.1k
0 votes
1 answer
157 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. ...
Turbo's user avatar
  • 13.7k
4 votes
1 answer
316 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 ...
Amal Duriseti's user avatar
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) = ...
H A Helfgott's user avatar
  • 19.3k
2 votes
0 answers
332 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 ...
mathstudent42's user avatar
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 ...
Turbo's user avatar
  • 13.7k
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 ...
Vadym Fedyukovych's user avatar
6 votes
4 answers
538 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 ...
Joseph O'Rourke's user avatar
1 vote
0 answers
343 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 ...
Peter Vojtas's user avatar
8 votes
2 answers
938 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 ...
Licheng Wang's user avatar
1 vote
1 answer
137 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_{...
Licheng Wang's user avatar
19 votes
1 answer
883 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 (...
Desiderius Severus's user avatar
4 votes
1 answer
747 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)...
Ahmad Jamil Ahmad Masad's user avatar
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)\...
Mayank Pandey's user avatar
5 votes
1 answer
601 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&...
Sebastien Palcoux's user avatar
11 votes
1 answer
470 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 ...
352506's user avatar
  • 991
3 votes
0 answers
96 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(...
Turbo's user avatar
  • 13.7k
8 votes
1 answer
479 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 \...
Ahmad Jamil Ahmad Masad's user avatar
6 votes
2 answers
308 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^+$ ...
Asvin's user avatar
  • 7,648
5 votes
1 answer
1k 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. ...
Watson Ladd's user avatar
  • 2,419
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 ...
Penelope Benenati's user avatar
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-...
Petro Kolosov's user avatar
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 ...
zbh2047's user avatar
  • 601
13 votes
2 answers
1k 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$ ...
José Hdz. Stgo.'s user avatar
6 votes
2 answers
381 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}^*$. ...
Sebastien Palcoux's user avatar
2 votes
1 answer
225 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^...
Safwane's user avatar
  • 963
5 votes
1 answer
330 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-...
Dan Brumleve's user avatar
  • 2,254
13 votes
2 answers
781 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 ...
FusRoDah's user avatar
  • 3,680
3 votes
1 answer
230 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 ...
student's user avatar
  • 149
0 votes
0 answers
255 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 ...
Dan Brumleve's user avatar
  • 2,254
12 votes
1 answer
539 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 ...
Dan Brumleve's user avatar
  • 2,254
4 votes
0 answers
118 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{...
François Brunault's user avatar
4 votes
0 answers
274 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 ...
Turbo's user avatar
  • 13.7k
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 ...
XL _At_Here_There's user avatar

1
3 4
5
6 7
9