Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

10
votes
0answers
99 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 ...
10
votes
1answer
286 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. ...
1
vote
0answers
108 views

Bounds for integer roots in trivariate Coppersmith

Coppersmith's theorem $2$ in Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities says that: "`Let $p(x, y)$ be an irreducible polynomial in two variables over $\Bbb Z$, of ...
15
votes
2answers
481 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
48 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
176 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
82 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
141 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. ...
3
votes
1answer
121 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 ...
0
votes
0answers
56 views

Solving a quadratic diophantine - writing sum of four squares with three parameters

Take the quadratic diophantine equation in variables $x,y,z$ $$(u_1'x+u_1'')^2+(u_2'x+u_2'')^2+(v_1'y+v_1'')^2+(v_2'y+v_2'')^2=t+ z p(p+1)$$ where $p,u_1',u_1'',v_1',v_1'',u_2',u_2'',v_2',v_2'',t$ are ...
2
votes
1answer
53 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
113 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 ...
2
votes
0answers
147 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 ...
2
votes
1answer
281 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
364 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
253 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 ...
6
votes
2answers
468 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
93 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
577 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
488 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
112 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
512 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
71 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
378 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
151 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
108 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
228 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
168 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
98 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
73 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
682 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
303 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
190 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-...
11
votes
2answers
539 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
votes
1answer
206 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 ...
0
votes
0answers
205 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 ...
11
votes
1answer
418 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 ...
4
votes
0answers
88 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{...
4
votes
0answers
235 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 ...
0
votes
0answers
64 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 ...
2
votes
0answers
78 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
votes
0answers
118 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,...
3
votes
2answers
186 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? ...
1
vote
1answer
68 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
0answers
140 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?
1
vote
0answers
109 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)
15
votes
0answers
306 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 ...
3
votes
0answers
120 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 ...