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
2 votes
0 answers
78 views

Computing coefficients of theta functions associated to quadratic forms

If we take an integral positive definite quadratic form $Q$ and set $\Theta_Q(z) = \sum_{k\geq 0}R_Q(k)e^{2\pi ikz}$, what are the most efficient algorithms to compute the $R_Q(k)$? I am aware e.g. of ...
user avatar
  • 221
4 votes
1 answer
661 views

Is there a way to specify a special kind of reciprocals of natural numbers?

Any number with of a form $\frac{1}{n}$ has a decimal with a repetend of finite length that is never longer than $n$ (provable by Dirichlet principle). (Example: $\frac{92}{99}=0.929292\ldots$ in ...
user avatar
2 votes
0 answers
235 views

How soon can we represent a number as the sum of two primes?

Posting in MO since it was unanswered in MSE. Goldbach's conjecture says that every even number can be represented as the sum of two primes. But how soon can we find such a representation. Taking $20 =...
user avatar
0 votes
0 answers
62 views

Complexity of small near-reciprocals at $\frac34+\epsilon$ exponent - square free smooth number case

Let $q$ be large composite square free $O(\operatorname{polylog}(T))$-smooth number in $[T,2T]$ where $T$ is a parameter. According to the paper https://arxiv.org/abs/1103.2879 we can have many ...
user avatar
  • 12.8k
0 votes
0 answers
53 views

Complexity of small near-reciprocals at $\frac34+\epsilon$ exponent - prime power number case

Let $q=p^r$ be large prime power of prime $p$ with $q\in[T,2T]$ where $T$ is a parameter. According to the paper https://arxiv.org/abs/1103.2879 we can have many integer pairs $a,b$ satisfying $ab\...
user avatar
  • 12.8k
0 votes
0 answers
89 views

Complexity of small near-reciprocals at $\frac34+\epsilon$ exponent - prime number case

Let $p$ be large prime in $[T,2T]$ where $T$ is a parameter. According to the paper https://arxiv.org/abs/1103.2879 we can have many integer pairs $a,b$ satisfying $ab\equiv c\bmod p$ such that $|c|$ ...
user avatar
  • 12.8k
0 votes
1 answer
83 views

Constructing an integer with small residues for two distinct primes in polynomial time

Given two primes $p,q\in[T,2T]$, how many integers $m$ of size $O(T^{3/2+\epsilon})$ are there such that the residues $m\bmod p$ and $m\bmod q$ are both $O(polylog(T))$? Looking for an answer Is it ...
user avatar
  • 12.8k
2 votes
1 answer
155 views

On roots of irreducible quadratics modulo composites

Assume factorization of $N$ is unknown. What is the best complexity we know to find roots of the irreducible equation $$ax^2+bx+c\equiv0\bmod N?$$ Is this problem equivalent to any hardness results?
user avatar
  • 12.8k
4 votes
1 answer
118 views

Discrete logarithms and primitive elements in finite fields

The recent papers: R. Granger, T. Kleinjung, J. Zumbragel, "On the Discrete Logarithm Problem in Finite Fields of Fixed Characteristic," Trans. Amer. Math. Soc., 370(5) (2018), 3129–3145. T....
user avatar
  • 425
4 votes
1 answer
197 views

Reliability of ILP approach to number-theoretic optimization

This question is inspired by the recent answer, where @RobPratt proposed to use integer linear programming (ILP) for solving a number-theoretic optimization problem. I will consider a very similar ...
user avatar
2 votes
2 answers
178 views

Ask for a proof of an identity involving the product of two Bernoulli numbers

It is well known that the Bernoulli numbers $B_{k}$ for $k\in\{0,1,2,\dotsc\}$ can be generated by \begin{equation*} \frac{z}{\textrm{e}^z-1}=\sum_{k=0}^\infty B_k\frac{z^k}{k!}=1-\frac{z}2+\sum_{k=1}^...
user avatar
  • 390
1 vote
2 answers
185 views

Ask for a reference or a proof of an identity involving a finite sum and the Bernoulli numbers

Let $B_{n}$ for $n\ge0$ denote the Bernoulli number generated by \begin{equation*} \frac{z}{\textrm{e}^z-1}=\sum_{n=0}^\infty B_n\frac{z^n}{n!}=1-\frac{z}2+\sum_{n=1}^\infty B_{2n}\frac{z^{2n}}{(2n)!},...
user avatar
  • 390
1 vote
2 answers
194 views

Efficiently finding the largest divisor of N less than sqrt(N)

Suppose you have a number $$ N = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k} $$ and are looking for the largest divisor $d|N$ such that $d^2<N$ (that is, A060775$(N)$.) How can I efficiently find this $d$? ...
user avatar
  • 8,358
8 votes
3 answers
521 views

Why is there an unexpected increase in the density of certain types of Goldbach primes?

Note: Posted in MO since it was unanswered in MSE. I was checking how quickly we can verify Goldbach's conjecture for a given even number $n$ and it was clear that searching backward starting from the ...
user avatar
1 vote
0 answers
76 views

How common are semiprimes with equally bitsized factors among semiprimes with equal bitsize?

I am curious about the following after having looked at the paper "Almost primes in almost all short intervals", theorem 3 says: Almost all intervals $[x, x + \log^{3.51}{(x)}]$ with $x ≤ X$...
user avatar
  • 11
2 votes
1 answer
217 views

Eisenstein polynomial of totally ramified extension over $p$-adic field

Let $p\geq 3$ be a prime number, $K$ be a finite extension of $\mathbb{Q}_p$ with no non-trivial unramified subextension, $f(x)$ be an irreducible monic polynomial in $\mathcal{O}_K[x]$, making $L=K[x]...
user avatar
1 vote
0 answers
49 views

On bounded discrete logarithm

Given $g^x=h\bmod p$ where x is known to size $p^{2/3}$ we need to find $x$. Is solving this in $P$ known?
user avatar
6 votes
1 answer
576 views

Are there highly composite prime gaps?

Definition: Highly composite prime gap The three composite numbers between the consecutive primes $643$ and $647$ each have at least three distinct prime factors. This is the first occurrence of prime ...
user avatar
4 votes
0 answers
168 views

Is there a polynomial time algorithm for finding primes?

I was wondering if, given $k$, there is a deterministic polynomial time algorithm (polynomial in $k$) which finds a prime number with $k$ digits. There is clearly a probabilistic one: just take random ...
user avatar
0 votes
1 answer
80 views

On polynomials associated to integers power sums [closed]

For $0\leq k\leq n$ integers let $P_k(n):= n^k,\ S_k(n):= P_k(1)+\ldots P_k(n)= 1^k+\ldots n^k$. Then $P_k(0)=0$, $S_0(n)=n$. For calculate $S_1(n)$ i consider: $$P_2(n)-P_2(n-1)=2n+1$$ then $\begin{...
user avatar
1 vote
0 answers
107 views

Can PARI compute class numbers without factoring the discriminant?

When calculating properties of algebraic number fields, one of the hardest steps is factorizing the discriminant of a defining polynomial. This is necessary in the Pohst-Zassenhaus algorithm for ...
user avatar
  • 125
1 vote
0 answers
34 views

Is there an effective genus theory for indefinite quadratic forms?

For positive definite quadratic forms, there is a way to check if two forms are isomorphic by arithmetic equivalence over $GL_n(Z)$ by computing configurations of vector up to some norm and then ...
user avatar
8 votes
0 answers
210 views

Hilbert 10th problem for genus 2 equations

Hilbert 10th problem, while undecidable in general, remains open for 2-variable equations: we do not know if there is an algorithm that, for polynomial $P(x,y)$ with integer coefficients, decides ...
user avatar
0 votes
0 answers
127 views

On a deterministic primes search problem

I feel the following problem might be resolved already. But I could not find any related answers. If $p_1,p_2,\dots,p_t$ are primes where $2\leq t=o(\log n)$ is there a prime within $$\prod_{i=1}^...
user avatar
  • 12.8k
0 votes
1 answer
99 views

Computing Lucas sequence for large n

I've been trying to write a test function for Fibonacci pseudo-primes with large $n$. Fibonacci pseudoprimes are composite numbers such that $V_n(P,Q) \equiv P \mod n$ for $P>0$ and $Q =\pm 1$, ...
user avatar
0 votes
1 answer
134 views

Method to solve modular quadratic polynomial [duplicate]

If $q$ is a prime what is the best method to compute roots of a quadratic polynomial $f(x)\equiv0\bmod q^2$ which is of form $x^2+bx+c\equiv0\bmod q^2$ where $b^2-4c\equiv0\bmod q$ and $gcd(b,q)=1$ ...
user avatar
  • 12.8k
3 votes
1 answer
81 views

Can we construct composite Fermat pseudoprimes to integral algebraic bases?

Let $0\neq \beta\in\overline{\mathbb{Z}}$ and let $n$ be a positive integer coprime to $N_{\mathbb{Q}(\beta)/\mathbb{Q}}(\beta)$. Say that $n$ is a Fermat pseudoprime to base $\beta$ if $$\beta^{n^{[\...
user avatar
  • 358
1 vote
1 answer
124 views

Counting $\mathrm{mod}\:p$ solutions of Diophantine equation in two variables taking $O(p^2)$ time

Are there Diophantine equations in two variables such that counting solutions $\mathrm{mod}\:p$ requires $O(p^2)$ time? Geometrically this means we have to sort through a positive proportion of the ...
user avatar
  • 21
5 votes
0 answers
281 views

A question on infinite arithmetic progressions

I was working on a problem that consisted of deciding if the language a finite automaton (the alphabet of which is $\{0,1\}$ and the words accepted are binary encoded positive integers) contains an ...
user avatar
25 votes
3 answers
2k views

Sum of squares and divisibility

Consider an integer of the form $$N = 1 + \sum_{i=1}^r d_i^2$$ where $d_i \in \mathbb{N}_{\ge 3}$ and $d_i^2$ divides $N$. Question: Must $r$ be greater than or equal to $9$? Checking (with SageMath): ...
user avatar
0 votes
0 answers
110 views

what are all possible pairs (k,m) such that n=2k^2+ m^2

I am working on a problem in number theory and would like to count all possible ways to partition an integer $n\geq 1$ into pairs $(k,m)$ of positive integers such that $n=2k^2+m^2$ and $n=4k^2+m^2$. ...
user avatar
  • 11
3 votes
0 answers
84 views

Next smooth number

I want to find the next $n \in \mathbb{N}$ such that $$s < n = \prod_{p_i \in \mathbb{P}_B} {p_i}^{a_i}$$ Where $\mathbb{P}_B$ is the set of primes not greater than $B$ I know that we can generate ...
user avatar
  • 131
3 votes
1 answer
129 views

Is factorial computation known to be in a class smaller than $FEXP$?

Functional version of the counting hierarchy is $FCH$. It is an open problem whether there a sequence of $poly(log(n))$ number of $+,\times$ operations utilizing the assistance of $O(1)$ number of ...
user avatar
  • 12.8k
6 votes
1 answer
292 views

How large can the dimension of a 'Span of powers of a finite field basis' be?

Let $p$ be a prime. For finite field $\mathbb{F}_{p^k}$ and $d\in\mathbb{Z}^+$, I am considering the following quantity, where we interpret the field $\mathbb{F}_{p^k}$ also as a $\mathbb{F}_p$-vector ...
user avatar
  • 69
1 vote
3 answers
236 views

How do I find abelian cubic extension over $\mathbb{Q}$ with class number more than 1?

I am trying to see them as subfield $\mathbb{Q}(\zeta_n).$ I feel it is a tiring job by using SageMath. Moreover, I am ending up with the abelian cubic field with the class number $1.$ I appreciate ...
user avatar
1 vote
0 answers
445 views

Langlands program and complexity theory

Back when I was an undergraduate, I spent some time reading the about the modularity conjecture, but the details are fuzzy now. One of the motivations I imagined for the Langlands program was for ...
user avatar
34 votes
1 answer
924 views

Does any cubic polynomial become reducible through composition with some quadratic?

What I mean to ask is this: given an irreducible cubic polynomial $P(X)\in \mathbb{Z}[X]$ is there always a quadratic $Q(X)\in \mathbb{Z}[X]$ such that $P(Q)$ is reducible (as a polynomial, and then ...
user avatar
0 votes
1 answer
182 views

How to simulate Poisson point process

How to simulate a process $S_t=\sum_{0\leq s\leq t}\Delta_s,$ where $\Delta_s$ is a Poisson point process with values in $(0,\infty)$ and with characteristic measure $\Pi(dx)=\frac{\alpha}{\Gamma(1-\...
user avatar
6 votes
0 answers
137 views

Certificate for computation of ideal class group

Is there a known way of producing a certificate that can be used to more quickly verify that an ideal class group of a number field was computed correctly? More formally, I would like to know if there'...
user avatar
  • 1,756
3 votes
0 answers
76 views

Study of relative class number of 'non-abelian' CM field by using L-functions

I'm currently interested in finding good upper bounds for the relative class numbers of non-abelian CM-fields. So I'm looking for some references to learn the techniques that can be useful. So far, I ...
user avatar
  • 951
2 votes
0 answers
132 views

Sum of all primes below $n$ without listing all primes below $n$

Asymptotically there is around $\frac{n}{\ln n}$ primes below a given integer $n$. Thus $\frac{n}{\ln n}$ is a lower bound for the time complexity of any algorithm that at some point finds each prime ...
user avatar
  • 21
0 votes
0 answers
61 views

Time complexity of asymmetric sums of divisor function

Let $\sigma_0:\mathbb{Z}_{\geq 1}\to \mathbb{Z}_{\geq 1}$ be the divisor counting function. Naively it seems the time complexity of computing $\sum_{i=1}^n \sigma_0(i)$ is at least linear but it can ...
user avatar
  • 1
2 votes
2 answers
236 views

Coefficient field of a newform using Magma

It is well-known that, for a newform $f = \sum c_nq^n \in \Gamma_0(N)$, the coefficient field $K_f := \mathbb{Q}(a_1, a_2, a_3, \cdots )$ is a number field. I am introducing myself in Magma, and I was ...
user avatar
19 votes
1 answer
1k views

Possible contemporary improvement to bounded gaps between primes?

In his summary of his book Bounded gaps between primes: the epic breakthroughs of the early 21st century, Kevin Broughan writes Which brings me to my final remark: where to next in the bounded gaps ...
user avatar
4 votes
0 answers
111 views

Riemann-Siegel formula for Dirichlet characters

After unearthing and giving a proof of what is now known as the Riemann--Siegel formula for the Riemann zeta function enabling the computation of $\zeta(1/2+iT)$ in time $O(T^{1/2})$, in 1943 Siegel ...
user avatar
  • 8,928
-2 votes
1 answer
290 views

Why wolfram alpha gives integers solutions for some equations of the form $ x^3 +(k\times10^n)^3 + z^3=0 $?

I have tried to get representations of some integers as sum of three cubic of the form $x^3+(k*10^n)^3+z^3$ with $k$ is integer and $n$ is a postive integer, I took this example : $(48807585839879)^3-(...
user avatar
3 votes
1 answer
146 views

Connecting different ways of constructing cubic extensions of $\mathbb{Q}$

There are at least two ways to construct cyclic cubic extensions of $\mathbb{Q}$ as explained below. (A third one is given in the answer to an earlier question). Given $A, B, C$ integers with $A\neq ...
user avatar
  • 1,194
1 vote
0 answers
85 views

Smooth number pairs satisfying a congruence

Let $\mathcal P=\{p_1,\dots,p_{2t}\}$ be $2t$ primes between $2^\ell$ and $2^{\ell+1}$ and fix an exponent bound $a\in\mathbb Z_{\geq2}$. Fix $N\in\mathbb N$ whose prime factors $p$ satisfy $p>2^{\...
user avatar
  • 12.8k
0 votes
0 answers
82 views

How to determine if a unramifed prime split or not?

Let $K$ be the Number field and $L$ be finite extension where $\mathfrak{p}$ prime of K is unramified. Are there any conditions on $\mathfrak{p}$ so that I can say $\mathfrak{p}$ splits completely in ...
user avatar
4 votes
0 answers
182 views

Ramsey Numbers for Integers

Erdos defined $f(n)$ to be the minimum $r$ such that there is an $r$-coloring of the positive integers less than $n$, wherein $n$ cannot be written as the sum of distinct monochromatic integers. ...
user avatar

1
2 3 4 5
8